Problem 55 of Project Euler has a rather long 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?

As a side note this algorithm of reversing and adding is also known as the 196 algorithm according to Wolfram. This led me to use the image which Chrisinplymouth has made available under the Creative Commons license. The image is shared under the same conditions as the original.

So the question gives us bounds for the search space. We need to search numbers less than 10.000 and we need to make a maximum of 50 iterations. Since we already have a method to reverse a number and check if it is palindromic, it should be pretty straight forward to create a brute force solution. Besides the brute force solution I will present a method with cache such that we don’t need to search the same number multiple times.

## Brute force solution

I have changed the implementation to check if a number is palindromic to use strings to reverse it, since it is faster when we work on BigInteger. The code for reversing and checking if it is palindromic looks like

private BigInteger ReverseNumber(BigInteger number) { char[] k = number.ToString().ToCharArray(); Array.Reverse(k); return BigInteger.Parse(new string(k)); } private bool IsPalindrome(BigInteger number) { return number == ReverseNumber(number); }

I have implemented it as two methods, the main method to loop over all numbers and a method to check if a number is a lychrel number.

The Lychrel function looks like

private bool IsLychrel(int number) { BigInteger testNumber = number; for (int i = 0; i < 50; i++) { testNumber += ReverseNumber(testNumber); if (IsPalindrome(testNumber)) return false; } return true; }

The main loop is really simple and looks like

const int start = 10; const int limit = 10000; int result = 0; for (int i = start; i < limit; i++) { if (IsLychrel(i)) result++; }

The only thing to note here is that we need to use BigInteger as the numbers get really huge when we get to the later iterations.

The only problem is the execution time. When I execute the code I get the result

The sum of Lychrel numbers less than 10000: 249 Solution took 201 ms

Which I consider a rather slow solution.

## Solution with caching

The other solution approach I have attempted is to cache the result.

Take the number 197 which gives us the following sequence

197 + 791 = 988

988 + 889 = 1877

1877 + 7781 = 9658

9658 + 8569 = 18227

18227 + 72281 = 90508

90508 + 80509 = 171017

171017 + 710171 = 881188

In the first solution we would run the same sequence when we reached 791, and almost again when we reached 889 and 988. However, the information we get here is that we know that 8 numbers less than 10000 is not lychrel numbers. Let us cache that to avoid having to test them again.

An equal result is created for 196 which is a Lychrel Number. Once we have that result we know that 961 must also be a Lychrel number. However, the later parts of that sequence we don’t know anything about.

I have implemented the cache as a Dictionary. The main loop for this method is the same apart from the initialization of the cache. The difference is the isLychrel method, which I have chanced to a recursive method.

private bool IsLychrelCache(BigInteger number, int ite) { bool isLyc = false; if (cache.TryGetValue(number, out isLyc)) return isLyc; if (ite >= 50) return true; BigInteger reverse = ReverseNumber(number); BigInteger testNumber = number + reverse; bool isPalindromic = IsPalindrome(testNumber); if (!isPalindromic) isLyc = IsLychrelCache(testNumber, ++ite); if (!isLyc || (isLyc && ite == 1)) { if (!cache.ContainsKey(number)) cache.Add(number, isLyc); if (!cache.ContainsKey(reverse)) cache.Add(reverse, isLyc); } return isLyc; }

For a somewhat more complicated code we get a bit of speed up. The result is

The sum of Lychrel numbers less than 10000: 249 Solution took 126 ms

Which means a speed up of 37% or so, pretty decent but I still think the solution is slow.

## Wrapping up

Experiments tells us that we could indeed stop the search after 25 iterations and get the same result much faster. However, I haven’t found a way to prove that ahead of time.

The source code is here.

Have you found a better way for solving this problem, or do you have questions or comments to the solution don’t hesitate to post them in the comment section.

Wow… 196 has been iterated up to 300 million digits (or more) and still no palindrome has been found. Now that’s amazing.

Sorry for the long reply time, I just got back from vacation and being offline for a few days.

300 million digits is indeed a very very large number. Speaking of large numbers. One of the larger numbers I encountered recently was when Littlewood proved that at some point around 10^304 the logarithmic integral will become larger than the prime counting function.

This upper bound has later been tightened. These are treated in the wikipedia article on Skewes’ number

Hi Kristian…

You are doing a great work at this blog…

Thanks for all the explanations… 🙂

You are welcome.

Table 1

Evolution in the quantity of Lychrel number candidates produced

as the sequence of natural numbers (base 10) is increasing

from 100 to 100 000.[Maximum iterations: 50].

[Re: Project Euler 55]

http://img11.hostingpics.net/pics/310144pe55tableone.jpg

Fig. 1

Evolution in the quantity of Lychrel number candidates produced

as the sequence of natural numbers (base 10) is increasing

from 0 to 100 000.[Maximum iterations: 50].

[Re: Project Euler 55]

http://img11.hostingpics.net/pics/928446pe55figone.jpg

Results in Table 1 show for the first 16 entries :

Range vs Lychrel candidates: (100 – 7 000) vs (0 – 124)

100 – 600 –> first simple linear relation

600 – 1 000 –> second simple linear relation

1 000 – 4 000 –> third simple linear relation

4 000 – 7 000 –> fourth simple linear relation

___

Sources:

1) Project Euler 55

Kristian’s algorithm

http://www.mathblog.dk/files/euler/Problem55.cs

2) Microsoft Visual C# 2010 Express

(Reference added : System.Numerics)

3) Microsoft Office Excel (2007)

Do we have a list of these numbers somewhere?

@ baur

Lychrel numbers

https://oeis.org/A023108

import java.util.*;

public class lychrel

{

public static long palin(long n)

{

long m,p=0;

while(n>0)

{

m=n%10;

p=(p*10)+m;

n=n/10;

}

return p;

}

public static void main(String ar[])

{

long a,l,i,j=0,t,it=0;

Scanner v=new Scanner(System.in);

a=v.nextInt();

l=a+palin(a);

t=palin(l);

for(i=1;i<=10;i++)

{

it++;

if(l==t)

break;

else

{

l=l+palin(l);

t=palin(l);

}

if(i==4)

j=l;

}

if(l!=t)

{

System.out.println(a+" is a Lychrel Number");

System.out.println("5th iteration of number "+a+" is "+j);

}

else

System.out.println(it);

}

}

I’m way late to the game, but my program in C++ took under 3 ms for brute force, using char arrays and homegrown string “bignum” math. Instead of explicitly reversing a number, I index from front to back and back to front, adding digits and propagating carry as I go. I found that caching the results either way (set of Lychrel or set of non-Lychrel numbers) just slowed down the process.

Carl

I have been checking this blog after every problem I solve since #20 or so.

This is the first time ever that I come with a faster solution, and not just that,

My solution took only 4 milliseconds !!!

The main optimizations are:

1- I used the long type; it’s enough for this problem.

2- reversing the same number twice wastes time (once in the check and the other to add the reverse to the original number)

instead, I store the reverse before leaving the isPalindrome()