Project Euler 55: How many Lychrel numbers are there below ten-thousand?

Project Euler 55: How many Lychrel numbers are there below ten-thousand?

Written by on 6 August 2011

Topics: Project Euler

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.

7 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

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

  2. Kristian says:

    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

  3. anand says:

    Hi Kristian…

    You are doing a great work at this blog…
    Thanks for all the explanations… 🙂

  4. Kristian says:

    You are welcome.

  5. Jean-Marie Hachey says:

    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)

  6. baur says:

    Do we have a list of these numbers somewhere?

  7. Jean-Marie Hachey says:

    @ baur

    Lychrel numbers
    https://oeis.org/A023108

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.