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.
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) HackerRank version
HackerRank Project Euler 55: given $N$, $100≤ N ≤ 10^5$, find the palindrome to which maximum numbers ∈ [1,N] converge. Print the palindrome and the count.
Solution
“Lychrel” is pronounced La’shrell and rhymes with bell. These numbers are for amusement and serve little practicable purpose.
We're identifying the most frequently occurring palindromic number generated through the reverse-and-add process for all integers below a specified limit $N$. For example:
[19,28,29,37,38,46,47,56,64,65,73,74,82,83,91,92,110,121]
all converge to 121, a total of 18 numbers.
Our Method
The script begins by iterating through each number from 10 up to $N-1$. For each number, it attempts to form a palindrome by repeatedly reversing its digits and adding the reversed number to the original. This process is capped at 17 iterations to prevent excessive computation and to account for numbers that may not form palindromes easily, aligning with the characteristics of potential Lychrel numbers.
As the script performs these operations, it maintains a dictionary d to record each palindrome encountered and the number of times it is achieved. If a palindrome is found within the 17 iterations, the script increments the count for that palindrome in the dictionary and moves to the next number. After processing all relevant numbers, the script identifies the palindrome with the highest occurrence by selecting the maximum value in the dictionary based on the count. This is achieved using the expression:
mx = max(d.items(), key=lambda x: x[1])
Finally, it prints this palindrome alongside its frequency, highlighting the most common palindromic result of the reverse-and-add process within the given range.
Last Word
For 196, billions of iterations have yet to force its abdication from the throne of possible Lychrel numbers.