Quote:
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?