I've been stuck on Project Euler problem 29 and thus asked a friend who solved it how to do it.

What he basically did was for each power was: $\left(\frac{\log_{10}(a)}{\log_{10}(2)}\right)\cdot b$ and adding this to a set (as sets' values are distinct the duplicates are automatically removed).

Now he could not remember why this formula works, I've tried to find it out myself but I'm not that good in maths.. If you remove the devision of $\log_{10}(2)$ the answer is also incorrect.

Can someone explain me why this formule works, how it works and why you must include the dividing by $\log_{10}(2)$.


  • $\begingroup$ @JavaMan That's is probably what he needs to figure out ;) Write that as a hint... BTW given the restrictions on $a,b$ the hint is probably easier to prove than the standard approach... $\endgroup$ – N. S. May 7 '13 at 16:10
  • $\begingroup$ @Javaman It doesn't need to be $a^b=b^a$, but $a^b=c^d$. For example $9^2$ duplicates $3^4$. $\endgroup$ – Scott H. May 7 '13 at 16:44
  • $\begingroup$ @ScottH.: Thanks! I knew it wouldn't be this easy, but I wasn't sure what I was overlooking. $\endgroup$ – JavaMan May 7 '13 at 17:26

You have $\log_{10} a^b=b \cdot \log_{10} a$. Your friend's expression is just dividing this by the constant $\log_{10} 2$, which is not needed.

It is better to do integer problems with integers. As the logs are not exact, you can get fooled when testing for equality of floating point numbers. You can overcome this by analyzing how different the logs of different answers can be, making sure the logs are accurate enough, and checking for almost equality of the floats.

  • $\begingroup$ If I run without the division the result is 9241, however if I run with the division I end up with 9183. $\endgroup$ – Gooey May 7 '13 at 16:39
  • $\begingroup$ @Gooey: then I would ask the program where they disagree. Make two sets, one each way, and after trying to add each element ask for the size of the two. If one increments and the other does not, print out $a,b$ and figure out what is happening. $\endgroup$ – Ross Millikan May 7 '13 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.