I did Project Euler's problem 63 last night, and it was a good one:
The 5-digit number, 16807 = 7^5, is also a fifth power. Similarly, the 9-digit number, 134217728 = 8^9, is a ninth power.
How many n-digit positive integers exist which are also an nth power?
I love this sort of problem. The algorithm for a brute force solution should be quite obvious: loop over bases and exponents, do the exponentiation, and see how many results' lengths match the exponent in question. But the question is what the loop constraints are. For this particular problem you can just write the loops, have them spit out answers, and then hit CTRL-C to terminate when the search stops finding results. But that's cheating.
Once you get the constraints, writing the code is trivial. What I couldn't figure out is how to compute the answer without the loops, though it seemed like that would be possible. After getting the right answer with the scan/check method I read down the forum thread and someone had done it. The proper loop constraints get you about 50% of the way, and I'd gotten another 30% of the way there, but couldn't quite get all the way. I still have trouble applying logarithms correctly when stuff gets complicated.
Comments are closed.