Lychrel numbers (project Euler 55 problem)

I'm supposed to find all supposed Lychrel numbers. If in 50 iterations number doesn't become palindromic then it's Lychrel number. I can't seem to get the right answer; I figured out that it may a problem of data types, because when I changed all ints to unsigned long long, the total number of Lychrel numbers decreased.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  #include <iostream>
using namespace std;

bool is_palindromic(unsigned long long number, int length) //checks if number is palindromic
{
    int digit1;
    int digit2;
    int i=0;

    while (number>9) {
        digit1=number%10;
            int temp=1, temp1=0;
            while (temp1<length-1) {temp=temp*10; temp1++;}
        digit2=number/temp;
        if (digit1!=digit2) return false;
        number=number/10;
        number=number%(temp/10);
        length=length-2; }

    return true;
}

int length(unsigned long long number) // calculates numbers length
{
    int i=0;
    while (number>0) {number=number/10; i++;}
    return i;
}

unsigned long long reverser(unsigned long long number, int length) // reverses number
{
    unsigned long long number1=0;
    unsigned long long multiplier=1;

    while (length>0) {multiplier=multiplier*10; length--;}

    while (number>0) {number1=number1+multiplier*(number%10);
    multiplier=multiplier/10;
    number=number/10; }

    return number1/10;
}

int main()
{
    unsigned long long cycle, howmany=0;
for (int i=1; i<=10000; i++) {int counter=0; cycle=i;
    while (counter<50) {cycle=cycle+reverser(cycle, length(cycle));
    if (is_palindromic(cycle, length(cycle))==true) {howmany++; break;}
    counter++;}

}
cout << (10000-howmany)/2;
}
Last edited on
I am currently doing the Project Euler problems too. I haven't done this one yet but I'm pretty sure the problem lies with the fact that some of the numbers generated are too large for the unsigned long long type. In the question it says that 10677 requires over 50 iterations before reaching a palindrome (4668731596684224866951378664), which is 28 digits long. I know you are looking for the number of lychrel numbers below 10,000 but the size of that 28 digit palindrome shows that you will be dealing with some very large numbers. You will need to download and install a library to deal with very large numbers such as:

http://gmplib.org/

or

https://mattmccutchen.net/bigint/

I tried and failed to install these btw, but the first one is what everyone recommends for dealing with extremely large numbers.

Also, in your question you say "If in 15 iterations number doesn't become palindromic then it's Lychrel number" but in the PE question it says that you should assume it is not a lychrel number if it doesn't become palindromic in 50 iterations, so you may be making a mistake there.

Last edited on
Yes machinafour, I noticed that I've mixed up 15 with 50. And thanks, I'll try out one of these libraries.
Last edited on
boost can deal with multiprecision numbers as well: http://www.boost.org/doc/libs/release/libs/multiprecision/doc/html/index.html
Topic archived. No new replies allowed.