Problem #55 involves an obscure type of number called a Lychrel number. The question reads:
Project Euler Problem 55: Lychrel numbers
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
You can probably guess how a brute force solution to this problem would look. Here is my solution:
Solution #1: Brute Force Approach
We know that all numbers less than 10,000 either produce a palindrome within 50 iterations or are considered Lychrel numbers. Thus, it suffices to perform 50 iterations on all numbers less than 10,000 until a palindrome is found and add the numbers which do not produce a palindrome. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #55
'''
import time
def isPalindrome(x):
a = str(x)
return a == a[::-1]
def projectEulerProblemFiftyFive(n,m):
final = 0
for x in range(1,n+1):
total = x
found = False
for a in range(m):
total = total+int(str(total)[::-1])
if(isPalindrome(total)):
found = True
break
if not found:
final+=1
return final
start = time.time()
print projectEulerProblemFiftyFive(10000, 50)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
249
--- 0.0513601303101 seconds ---
for input of n = 10000, m = 50
'''
As shown above, brute force can be quite effective at determining whether integers fall into certain classes of numbers.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 