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)

## Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

Guest Message by DevFuse

# Lychrel

Started by BMAD, Aug 08 2013 01:45 AM

2 replies to this topic

### #1

Posted 08 August 2013 - 01:45 AM

### #2

Posted 09 August 2013 - 07:46 AM

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, 09 August 2013 - 07:52 AM.**

### #3

Posted 09 August 2013 - 07:55 AM

Spoiler for code

Spoiler for result

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

**Edited by Anza Power, 09 August 2013 - 07:57 AM.**

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users