Power number
Given a natural number N is there a fast way to test if the number is of the form k*b^n+c where b^n contributes to 99% size of N; c<m*n where m is small.
Brute force could be one way: calculating N%b, N%b^2 ... and checking if they are all same. Anything faster? Would taking log of N help? 
[QUOTE=Citrix;552199]Brute force could be one way: calculating N%b, N%b^2 ... and checking if they are all same.[/QUOTE]
You have to start with b^k > c and check both N%b^k and N%b^(k+1) are the same. Of course, without any size limits on b or c, this is going to take forever to rule out all potential b's. If b & c can be reasonably limited (say both < 1e9), you can use sieving techniques to quickly figure out valid (b,c) combinations that can potentially equal N. 
[QUOTE=axn;552207]You have to start with b^k > c and check both N%b^k and N%b^(k+1) are the same. Of course, without any size limits on b or c, this is going to take forever to rule out all potential b's.
If b & c can be reasonably limited (say both < 1e9), you can use sieving techniques to quickly figure out valid (b,c) combinations that can potentially equal N.[/QUOTE] Thanks. A faster way might be to to : calculate max_n = log(N)/log(2) then for all n from 2 to max_n you calculate corresponding b value (use log to solve) int(N^(1/n))=b Since this is approximate we want to check b1, b and b+1 Then sieve over these values to see if there is a solution. This would still be under brute force. Anything faster than this? 
[QUOTE=Citrix;552210]Thanks.
A faster way might be to to : calculate max_n = log(N)/log(2) then for all n from 2 to max_n you calculate corresponding b value (use log to solve) int(N^(1/n))=b Since this is approximate we want to check b1, b and b+1 Then sieve over these values to see if there is a solution. This would still be under brute force. Anything faster than this?[/QUOTE] That will not probably work. Due to the presence of k, a large range of b's will be perfectly plausible for any given n. I think we can slightly optimize the previous bbased approach to only look at prime b's. 
[QUOTE=Citrix;552199]Given a natural number N is there a fast way to test if the number is of the form k*b^n+c where b^n contributes to 99% size of N; c<m*n where m is small.[/QUOTE]Yes.
The first number to match the criteria is 100 = 1*99^1+1 Then 200 = 1*198^1+2 Then x*100 = 1*(99x)^1+x etc. So all you have to do is check that the number is divisible by 100. 
[QUOTE=axn;552246]
I think we can slightly optimize the previous bbased approach to only look at prime b's.[/QUOTE] Why? b can be composite. eg. 7*6^100+11 
[QUOTE=Citrix;552262]eg. 7*6^100+11[/QUOTE]Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%

[QUOTE=Citrix;552262]Why? b can be composite.
eg. 7*6^100+11[/QUOTE] Sure, b can be composite. But a composite b [B]must[/B] also pass a prime b check as a [B]necessary[/B] condition. For example, consider N=7*6^100+11. It [B]will[/B] pass the b=2 check. [CODE]? N=7*6^100+11; ? N%(2^64) %2 = 11 ? N%(2^65) %3 = 11[/CODE] I will also pass b=3 check. [CODE]? N%(3^64) %4 = 11 ? N%(3^65) %5 = 11 [/CODE] If it didn't pass b=2 check, then no need to check any other even b. If it didn't pass b=3 check, then no need to check any composite base which is multiple of 3, and so on. So we can limit ourselves to prime bases, as a first pass. In second pass, we subtract the potential c from N (i.e. N  N%(b^k) ) and then trial divide it to see if it factorises into small factors. If so, we get the actual representation as well. 
[QUOTE=retina;552263]Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%[/QUOTE]
"Size of N" is the digit length of N, which is basically O(log(N)) 
[QUOTE=axn;552246]That will not probably work. Due to the presence of k, a large range of b's will be perfectly plausible for any given n.
[/QUOTE] Your point for prime b makes sense. Thanks. For small k values and large n values only 12 b values will be possible. For small n a large number of b values will be possible. I am more interested in the first case. To refine the question I am looking for k<m*n c<m*n n*m>b with m small 
[QUOTE=axn;552269]"Size of N" is the digit length of N, which is basically O(log(N))[/QUOTE]Okay. But it still doesn't meet the criterion 99%.
log(6¹⁰⁰)/log(7×6¹⁰⁰+11) = 98.92...% Indeed for any integer N I can't see how you ever get 99%. The only way would be something like e×e⁹⁹+0 = 99%. So k=e, b=e, n=99, c=0. And other multiples of those values. 
[QUOTE=Citrix;552271]To refine the question I am looking for
k<m*n c<m*n n*m>b with m small[/QUOTE] That still leaves surprisingly large search space. How big is N? Less than 1000 bits? More than million bits? How small is m? Less than 1000? More than million? 
[QUOTE=retina;552272]Okay. But it still doesn't meet the criterion 99%.
log(6¹⁰⁰)/log(7×6¹⁰⁰+11) = 98.92...% Indeed for any integer N I can't see how you ever get 99%. The only way would be something like e×e⁹⁹+0 = 99%. So k=e, b=e, n=99, c=0. And other multiples of those values.[/QUOTE] Ah! You're thinking 99% as an exact number, whereas I'm pretty sure OP intended to give the general flavor of the structure of the number. Meaning, b^n part is the dominant term. 
[QUOTE=axn;552273]That still leaves surprisingly large search space.
How big is N? Less than 1000 bits? More than million bits? How small is m? Less than 1000? More than million?[/QUOTE] N~ 100,000 bits + m <1000 We could also define k and c to be less than 2^64. 
[QUOTE=Citrix;552271]To refine the question I am looking for
k<m*n c<m*n n*m>b with m small[/QUOTE] [QUOTE=Citrix;552281]N~ 100,000 bits + m <1000 We could also define k and c to be less than 2^64.[/QUOTE] Let's take m=1000 so we have the largest search space. When N is about 1e5 bits, the first n that satisfies m*n > b is n_min~=4500, and b_max ~=4.5 million When N is about 1e6 bits, it is n_min ~= 39600 and b_max ~=39.6 million. For the above numbers, it should be feasible to brute force all prime b's < b_max. Basic outline of the algorithm would be to do c = N % (b^k), (prime b from 2 to b_max) where b^k is about 256 bits (>> our target c with is < 64 bits). If c < 2^64, we may have a potential solution, so trial factor Nc upto b_max and see if we get a complete factorization. 
All times are UTC. The time now is 10:38. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.