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 b-1, 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 b-1, 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 b-based 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 b-based 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 1-2 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.