3 ms·
You can speed up brute force search by starting somewhere before where log10(x^y) * 4.5 is roughly equal to x. For example 2222^140 is 2110 which is close to 22
by Aardwolf 8y ago
You can speed up brute force search by starting somewhere before where log10(x^y) * 4.5 is roughly equal to x. For example 2222^140 is 2110 which is close to 2222. Then brute force search from there and you get:
2222 ^ 145
- klodolph 8y agoHow much does this speed up brute force search, though? You have to actually compute the exponent and digit sums. If I iterate over the powers of N from N^I to N^J, I do something like O((J-I)^2*log N) work doing multiplications the naive way.