// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (11 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


Problem Description

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

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 zero (false) result. This process is repeated up to 49 (depth) times and returns one (true) only if it passes all iterations.

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.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|249|

Afterthoughts

    No afterthoughts yet.

Function is_palindromic is listed in Common Functions and Routines for Project Euler
for N<100,000 and up to 500 iterations produces 6091 Lychrel numbers. [/comments]
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