Project Euler Problem 55 Solution

Project Euler Problem 55 Solution

Lychrel numbers

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 55 Statement

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.

Solution

“Lychrel” is pronounced La’shrell and rhymes with bell. These number are for amusement and serve little practicable purpose.

The script takes a number N as input and examines each number from 10 up to N. For each number, it follows a process called "reverse and add": it takes the number, reverses its digits, adds it to the original number, and repeats this process up to 17 times for each starting number. If at any point the result becomes a palindrome (reads the same forwards and backwards), it records this starting number in a dictionary 'd', keeping count of how many starting numbers led to that palindrome. Finally, it finds and prints the palindrome that was reached most frequently along with its frequency.

For example, if we start with 28, the process would go: 28 + 82 = 110, 110 + 011 = 121, and stop there since 121 is a palindrome. The script would increment the count for 121 in the dictionary. After checking all numbers up to N, it reveals which palindrome was most commonly reached.

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 55

HackerRank Project Euler 55 asks: given N, find the palindrome [1,N] to which maximum numbers converge.

Python Source Code

N = int(input())
d = {}
for i in range(10, N):
    n = i
    for _ in range(17):
        str_n = str(n)
        if str_n == str_n[::-1]:
            d[n] = d.get(n, 0) + 1
            break
        n += int(str_n[::-1])

mx = max(d.items(), key=lambda x: x[1])
print(*mx)

Last Word