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. Being said, however, it is a curiosity that deserves to be explored if for no better reason than to develop an algorithm to disprove their existence. 196-Algorithm is the official name given to programs that investigate Lychrel numbers, and to date, brute force testing has not proven that Lychrel numbers don’t exist as is the case with 196 – the algorithm’s namesake.

Our bounds are specified by the problem’s description; specifically to search a range from 10 to 9999 and only check a depth to 49 iterations.

The function is_lychrel() takes the candidate and adds itself to its reverse. If this sum is a palindrome then it’s not a Lychrel number and we return a false (zero) result. This process is repeated up to 49 (depth) times and returns true (one) only if it passes all iterations without producing a palindrome. This does not confirm with irrefutability the number to be a Lychrel number as deeper iterations could disprove the number’s Lychrel status. However, for 196, billions of iterations have yet to force its abdication from the throne of possible Lychrel numbers.

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

s = 2; N = 2000000; primeSum = [0]*(N+1)
primeSum[2] = s
for i in range(3, N, 2):
	if primeSum[i]==0:
		s+= i
		primeSum[i::i] = [-1]*(N//i)
	primeSum[i] = s; primeSum[i+1] = s   #each odd index and the following even index
L = int(input("Sum of primes not greater than? "))
print ("is", primeSum[L])

Last Word