Thread: Power number
View Single Post
Old 2020-08-01, 18:35   #3
Citrix's Avatar
Jun 2003

1,579 Posts

Originally Posted by axn View Post
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.
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)
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?
Citrix is online now   Reply With Quote