// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (16 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 55 Solution

Project Euler 55 Solution

Project Euler 55: Find how many Lychrel numbers are there below ten-thousand


Project Euler 55 Problem Description

Project Euler 55: 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.

Analysis

“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.

Project Euler 55 Solution

Runs < 0.050 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 55 Solution Python 2.7 source.

Afterthoughts

Project Euler 55 Solution last updated

Discussion

2 Responses to “Project Euler 55 Solution”

  1. print sum(1 for n in range(10, 10000) if is_lychrel(n))

    can be written as

    print sum(is_lychrel(n) for n in range(10, 10000))

    Posted by bob | February 13, 2011, 1:42 PM

Post a comment