Jump to content
BrainDen.com - Brain Teasers
  • 0

Lychrel

BMAD

Asked by BMAD,

 Share

Question

BMAD Grand Master

BMAD

Posted
Posted

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)

Link to comment
Share on other sites

3 answers to this question

Recommended Posts

  • 0
Anza Power Enthusiast

Anza Power

Posted
Posted (edited)

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
  • Upvote 1
Link to comment
Share on other sites
  • 0
Anza Power Enthusiast

Anza Power

Posted
Posted (edited)

  Reveal hidden contents

  Reveal hidden contents

http://ideone.com/PdM8rF

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

Edited by Anza Power
  • Upvote 1
Link to comment
Share on other sites
  • 0
Priyaa Newbie

Priyaa

Posted
Posted

import java.util.*;
public class lychrel
{
    public static long palin(long n)
    {
        long m,p=0;
        while(n>0)
        {
            m=n%10;
            p=(p*10)+m;
            n=n/10;
        }
        return p;
    }
    public static void main(String ar[])
    {
        long a,l,i,j=0,t,it=0;
        Scanner v=new Scanner(System.in);
        a=v.nextInt();
        l=a+palin(a);
        t=palin(l);
        for(i=1;i<=10;i++)
        {
            it++;
            if(l==t)
            break;
            else
            {
            l=l+palin(l);
            t=palin(l);
            }
            if(i==4)
                j=l;
        }
        if(l!=t)
        {
            System.out.println(a+" is a Lychrel Number");
            System.out.println("5th iteration of number "+a+" is "+j);
        }
        else
            System.out.println(it);
    }
}

  • Upvote 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
 Share
Go to question listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...