Prob 0004 ‐ Largest Palindrome Product - maccergit/Euler GitHub Wiki

Typical approaches here involve converting between strings and numbers, taking substrings, and reversing strings. It is possible to deal with the digits directly as numbers, but being able to convert the number to a string of digits makes it much easier to determine if it is a palindrome by simply seeing if the string and its reversal are equivalent.

Research into palindromic numbers on the web turns up a detailed wikipedia page that states that all palindromic numbers with an even number of digits are divisible by 11. Since the problem states the palindrome should be the product of two numbers with the same number of digits, the resulting product will have an even number of digits (he product of two 3-digit numbers will be either 5 or 6 digits, and we are looking for the largest palindrome, which we can expect to be in the partition with 6 digits). The PDF of notes provides a quick proof of why the resulting number will be a multiple of 11.

With multiplication being commutative ($ab=ba$), we can cut the number of tests in half by avoiding duplicates : if we have tested $ab$, then we don't need to test $ba$.

01

This is a direct implementation that uses the optimizations listed above. Again, Python's generator comprehension and string slice syntax make this easy to implement, even with the optimizations. This approach scales so poorly with larger limits that it's not feasible to build a graph with many data points, so we just include the tabular output :

limit	time (msec)
2	0.8716074000000074
3	75.1177406
4	7658.885900200001

With each additional digit adding 2 orders of magnitude to the time, I would expect 5 digits to take more than 10 minutes.