Power number

[Citrix]

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?

[axn]

Originally Posted by Citrix

Brute force could be one way:- calculating N%b, N%b^2 ... and checking if they are all same.

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.

[Citrix]

Originally Posted by axn

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.

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?

[axn]

Originally Posted by Citrix

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?

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.

[retina]

Originally Posted by Citrix

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.

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.

[Citrix]

Originally Posted by axn

I think we can slightly optimize the previous b-based approach to only look at prime b's.

Why? b can be composite.

eg. 7*6^100+11

[retina]

Originally Posted by Citrix

eg. 7*6^100+11

Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%

[axn]

Originally Posted by Citrix

Why? b can be composite.

eg. 7*6^100+11

Sure, b can be composite. But a composite b must also pass a prime b check as a necessary condition.

For example, consider N=7*6^100+11. It will pass the b=2 check.

? N=7*6^100+11;
? N%(2^64)
%2 = 11
? N%(2^65)
%3 = 11

I will also pass b=3 check.

? N%(3^64)
%4 = 11
? N%(3^65)
%5 = 11

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.

[axn]

Originally Posted by retina

Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%

"Size of N" is the digit length of N, which is basically O(log(N))

[Citrix]

Originally Posted by axn

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.

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

[retina]

Originally Posted by axn

"Size of N" is the digit length of N, which is basically O(log(N))

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.