[C++/Python] Project Euler #55 - Lychrel Numbers

This problem is also a difficulty level 5% problem.

A Lychrel number is a positive integer that, when expressed in base 10 and added to its reverse, does not form a palindrome. If the result is not a palindrome, the process is repeated by reversing the number and adding again.

Theoretically, since the numbers increase gradually, it is assumed that eventually a palindrome (a number that reads the same forwards and backwards) will be formed.

However, although it hasn’t been proven, there are numbers that are believed never to produce a palindrome no matter how many times this process is repeated. These numbers are called Lychrel numbers. The smallest known such number is 196.

---

reverse sum

The problem is that depending on how many iterations are allowed, a number thought to be a Lychrel number might not actually be one.

In this problem, we define a Lychrel number as one that does not produce a palindrome within 50 iterations. (There are examples that create a palindrome on the 53rd iteration.)

What makes this problem interesting is that some Lychrel numbers are palindromes themselves. The question in this problem is: How many such palindromic Lychrel numbers exist below 10,000?

You can’t just solve this easily with C/C++ because adding the reversed number essentially means doubling it on average. That means you may need to do calculations up to 2^{50}, which isn’t feasible with standard 32-bit or 64-bit integer types. It might be possible with a 128-bit integer type.

---

So, to make this easier, it’s better to use a language like Python.

I’ve written two versions of the solution.

Here is the C/C++ version of the code.

//------------------------------------------------
//    Project Euler #55 - Lychrel Numbers
//        - by Aubrey Choi
//        - created at 2015-03-31
//------------------------------------------------
#include <stdio.h>
#include <string.h>

struct BigInt
{
    BigInt(int n)
    {
        len = 0;
        while(n)
        {
            v[len++] = n%10;
            n /= 10;
        }
    }
    int len;
    char v[100];
};

BigInt ReverseSum(BigInt &n)
{
    BigInt s = 0;
    int c = 0;
    for(int i = 0; i < n.len; i++)
    {
        c += n.v[i] + n.v[n.len-i-1];
        s.v[s.len++] = c%10;
        c /= 10;
    }
    if(c) s.v[s.len++] = c;
    return s;
}

bool IsPalindrome(BigInt &n)
{
    for(int i = 0; i < n.len/2; i++)
    {
        if(n.v[i] != n.v[n.len-i-1]) return false;
    }
    return true;
}

bool IsLychrel(int n)
{
    BigInt s = n;
    for( int i = 1 ; i < 50 ; i++ )
    {
        s = ReverseSum(s);
        if(IsPalindrome(s)) return false;
    }
    return true;
}

int main()
{
    int count = 0;
    for( int k = 1 ; k < 10000 ; k++ )
        if( IsLychrel(k) ) count++;
    printf("ans = %d\n", count);
}

And this is the Python version that directly implements the above algorithm.

#------------------------------------------------------------
#    Project Euler #55 - Lychrel Numbers
#    Author: Aubrey Choi
#    Date:    2015.03.31.
#------------------------------------------------------------
def Reverse(n):
    return int(str(n)[::-1])

def IsLychrel(n):
    n = n + Reverse(n)
    for i in range(1, 50):
        r = Reverse(n)
        if( r == n ): return False
        n += r
    return True

count = 0
for k in range(1, 10000):
    if( IsLychrel(k) ): count = count+1
print(count)

The runtime in Python is about 6 times slower. That’s probably inevitable since it’s a scripting language. But Python wins when it comes to code clarity.