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