• 0

Lychrel

Question

Posted · Report post

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?

(Here's a problem for my programmers)

0

Share this post


Link to post
Share on other sites

2 answers to this question

  • 0

Posted (edited) · Report post

Code:

#include <iostream>
#define BUF_SIZE 100
using namespace std;
 
void putInArray(int num, int* buf){
    for(int i=0;i<BUF_SIZE;i++){
        buf[i] = num % 10;
        num = num / 10;
    }
}
 
bool isPalindrom(int* buf){
    int i=0, j=BUF_SIZE-1;
    while(buf[j]==0 && j>0){
        j--;
    }
    while(i<j){
        if(buf[i] != buf[j]){
            return false;
        }
        i++;
        j--;
    }
    return true;
}
 
void applyIteration(int* buf){
    int i=0, j=BUF_SIZE-1;
    while(buf[j]==0 && j>0){
        j--;
    }
    while(i<=j){
        int temp = buf[i] + buf[j];
        buf[i++] = temp;
        buf[j--] = temp;
    }
    
    for(int i=0;i<BUF_SIZE-1;i++){
        buf[i+1] += buf[i] / 10;
        buf[i] = buf[i] % 10;
    }
}
 
bool isLychrel(int* buf){
    for(int i=1;i<50;i++){
        applyIteration(buf);
        if(isPalindrom(buf)){
            return false;
        }
    }
    return true;
}
 
int main() {
    int buf[BUF_SIZE];
    
    for(int num=0;num<10000;num++){
        putInArray(num,buf);
        if(isLychrel(buf)){
            cout << num << " is Lychrel " << endl;
        }
    }
}
Edited by Anza Power
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

#include <iostream>
#define BUF_SIZE 100
using namespace std;
 
void putInArray(int num, int* buf){
    for(int i=0;i<BUF_SIZE;i++){
        buf[i] = num % 10;
        num = num / 10;
    }
}
 
bool isPalindrom(int* buf){
    int i=0, j=BUF_SIZE-1;
    while(buf[j]==0 && j>0){
        j--;
    }
    while(i<j){
        if(buf[i] != buf[j]){
            return false;
        }
        i++;
        j--;
    }
    return true;
}
 
void applyIteration(int* buf){
    int i=0, j=BUF_SIZE-1;
    while(buf[j]==0 && j>0){
        j--;
    }
    while(i<=j){
        int temp = buf[i] + buf[j];
        buf[i++] = temp;
        buf[j--] = temp;
    }
    
    for(int i=0;i<BUF_SIZE-1;i++){
        buf[i+1] += buf[i] / 10;
        buf[i] = buf[i] % 10;
    }
}
 
bool isLychrel(int* buf){
    for(int i=1;i<50;i++){
        applyIteration(buf);
        if(isPalindrom(buf)){
            return false;
        }
    }
    return true;
}
 
int main() {
    int buf[BUF_SIZE];
    
    for(int num=0;num<10000;num++){
        putInArray(num,buf);
        if(isLychrel(buf)){
            cout << num << " is Lychrel " << endl;
        }
    }
}

http://ideone.com/PdM8rF

196 is Lychrel
295 is Lychrel
394 is Lychrel
493 is Lychrel
592 is Lychrel
689 is Lychrel
691 is Lychrel
788 is Lychrel
790 is Lychrel
879 is Lychrel
887 is Lychrel
978 is Lychrel
986 is Lychrel
1495 is Lychrel
1497 is Lychrel
1585 is Lychrel
1587 is Lychrel
1675 is Lychrel
1677 is Lychrel
1765 is Lychrel
1767 is Lychrel
1855 is Lychrel
1857 is Lychrel
1945 is Lychrel
1947 is Lychrel
1997 is Lychrel
2494 is Lychrel
2496 is Lychrel
2584 is Lychrel
2586 is Lychrel
2674 is Lychrel
2676 is Lychrel
2764 is Lychrel
2766 is Lychrel
2854 is Lychrel
2856 is Lychrel
2944 is Lychrel
2946 is Lychrel
2996 is Lychrel
3493 is Lychrel
3495 is Lychrel
3583 is Lychrel
3585 is Lychrel
3673 is Lychrel
3675 is Lychrel
3763 is Lychrel
3765 is Lychrel
3853 is Lychrel
3855 is Lychrel
3943 is Lychrel
3945 is Lychrel
3995 is Lychrel
4079 is Lychrel
4169 is Lychrel
4259 is Lychrel
4349 is Lychrel
4439 is Lychrel
4492 is Lychrel
4494 is Lychrel
4529 is Lychrel
4582 is Lychrel
4584 is Lychrel
4619 is Lychrel
4672 is Lychrel
4674 is Lychrel
4709 is Lychrel
4762 is Lychrel
4764 is Lychrel
4799 is Lychrel
4852 is Lychrel
4854 is Lychrel
4889 is Lychrel
4942 is Lychrel
4944 is Lychrel
4979 is Lychrel
4994 is Lychrel
5078 is Lychrel
5168 is Lychrel
5258 is Lychrel
5348 is Lychrel
5438 is Lychrel
5491 is Lychrel
5493 is Lychrel
5528 is Lychrel
5581 is Lychrel
5583 is Lychrel
5618 is Lychrel
5671 is Lychrel
5673 is Lychrel
5708 is Lychrel
5761 is Lychrel
5763 is Lychrel
5798 is Lychrel
5851 is Lychrel
5853 is Lychrel
5888 is Lychrel
5941 is Lychrel
5943 is Lychrel
5978 is Lychrel
5993 is Lychrel
6077 is Lychrel
6167 is Lychrel
6257 is Lychrel
6347 is Lychrel
6437 is Lychrel
6490 is Lychrel
6492 is Lychrel
6527 is Lychrel
6580 is Lychrel
6582 is Lychrel
6617 is Lychrel
6670 is Lychrel
6672 is Lychrel
6707 is Lychrel
6760 is Lychrel
6762 is Lychrel
6797 is Lychrel
6850 is Lychrel
6852 is Lychrel
6887 is Lychrel
6940 is Lychrel
6942 is Lychrel
6977 is Lychrel
6992 is Lychrel
7059 is Lychrel
7076 is Lychrel
7149 is Lychrel
7166 is Lychrel
7239 is Lychrel
7256 is Lychrel
7329 is Lychrel
7346 is Lychrel
7419 is Lychrel
7436 is Lychrel
7491 is Lychrel
7509 is Lychrel
7526 is Lychrel
7581 is Lychrel
7599 is Lychrel
7616 is Lychrel
7671 is Lychrel
7689 is Lychrel
7706 is Lychrel
7761 is Lychrel
7779 is Lychrel
7796 is Lychrel
7851 is Lychrel
7869 is Lychrel
7886 is Lychrel
7941 is Lychrel
7959 is Lychrel
7976 is Lychrel
7991 is Lychrel
8058 is Lychrel
8075 is Lychrel
8079 is Lychrel
8089 is Lychrel
8148 is Lychrel
8165 is Lychrel
8169 is Lychrel
8179 is Lychrel
8238 is Lychrel
8255 is Lychrel
8259 is Lychrel
8269 is Lychrel
8328 is Lychrel
8345 is Lychrel
8349 is Lychrel
8359 is Lychrel
8418 is Lychrel
8435 is Lychrel
8439 is Lychrel
8449 is Lychrel
8490 is Lychrel
8508 is Lychrel
8525 is Lychrel
8529 is Lychrel
8539 is Lychrel
8580 is Lychrel
8598 is Lychrel
8615 is Lychrel
8619 is Lychrel
8629 is Lychrel
8670 is Lychrel
8688 is Lychrel
8705 is Lychrel
8709 is Lychrel
8719 is Lychrel
8760 is Lychrel
8778 is Lychrel
8795 is Lychrel
8799 is Lychrel
8809 is Lychrel
8850 is Lychrel
8868 is Lychrel
8885 is Lychrel
8889 is Lychrel
8899 is Lychrel
8940 is Lychrel
8958 is Lychrel
8975 is Lychrel
8979 is Lychrel
8989 is Lychrel
8990 is Lychrel
9057 is Lychrel
9074 is Lychrel
9078 is Lychrel
9088 is Lychrel
9147 is Lychrel
9164 is Lychrel
9168 is Lychrel
9178 is Lychrel
9237 is Lychrel
9254 is Lychrel
9258 is Lychrel
9268 is Lychrel
9327 is Lychrel
9344 is Lychrel
9348 is Lychrel
9358 is Lychrel
9417 is Lychrel
9434 is Lychrel
9438 is Lychrel
9448 is Lychrel
9507 is Lychrel
9524 is Lychrel
9528 is Lychrel
9538 is Lychrel
9597 is Lychrel
9614 is Lychrel
9618 is Lychrel
9628 is Lychrel
9687 is Lychrel
9704 is Lychrel
9708 is Lychrel
9718 is Lychrel
9777 is Lychrel
9794 is Lychrel
9798 is Lychrel
9808 is Lychrel
9867 is Lychrel
9884 is Lychrel
9888 is Lychrel
9898 is Lychrel
9957 is Lychrel
9974 is Lychrel
9978 is Lychrel
9988 is Lychrel
9999 is Lychrel

Also: http://projecteuler.net/problem=55

Edited by Anza Power
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.