Project euler 55

Question

I was solving this problem (https://projecteuler.net/problem=55) and I couldn't get it right. The answer was 249 and my code was giving 136. I don't know what is wrong with my code. Here is my code:

#include <stdio.h>
long long reverse(long long n)
{
    long long a=0, t=n, temp;
    while (t)
    {
        temp=t%10;
        a=a*10+temp;
        t=t/10;
    }
    return a;
}
bool palindromic(long long n)
{
    return reverse(n)==n;
}
bool lychrel(long long n)
{
    long long k=n;
    for (int i=0; i<50; i++)
    {
        k+=reverse(k);
        if (palindromic(k)) return false;
    }
    return true;
}
int main()
{
    int i, count=0;
    for (i=1; i<10000; i++)
        if (lychrel(i)) count++;
    printf("%d", count);
    return 0;
}

Thanks in advance!

using a debugger will not magically fix your bugs, but it will give you a chance to step through the code line by line and see where it starts to diverge from your expectations. What did you observe when using a debugger? — 463035818_is_not_an_ai, Nov 25 '19 at 12:54
Using `unsigned long long` instead of `long long` will give you 249 instead of 136. `long long` overflows at ~9 quintillion, `unsigned long long` at ~18 quintillion, though I expect neither is capturing *every* Lychrel number between 1 and 10,000 since 10677 requires 28 digits. — William Miller, Nov 25 '19 at 23:03

Jorge Galvão · Answer 1 · 2019-11-25T13:12:42.377

When you apply the k+=reverse(k); it is overflowing for many of the Lychrel numbers. For example 196 overflows after 40 iterations.

To be able to test if some number is a Lychrel you need more than the 64 bits the long long provides (63 bits to be more precise). You need to either use big integers or string manipulation if you want to do the "add" manually for 2 strings.

Check this answer for big integers: C++ Big Integer

If you want a quick and dirty fix, you can just test for overflow and consider that if it overflows, it needs "too many" iterations. This will not be a correct program (because it will not test for 50 iterations), but will still give you a correct result (because you will be able to find all the non Lychrel numbers below ten thousand before they overflow). It will for sure fail if you increase the limit from ten thousand to some bigger numbers.

To test for overflow you can just check if k + reverse(k) < k for example.

Project euler 55

1 Answers1