Lychrel number

From Wikipedia, the free encyclopedia

A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. This process is called the 196-algorithm. The name "Lychrel" was coined by Wade VanLandingham – a rough anagram of his girlfriend's name Cheryl.

1 Reverse and add process
2 Proof not found
3 Threads, seed and kin numbers
4 196 palindrome quest
5 External links

[edit] Reverse and add process

The reverse and add process produces the sum of a number and the number formed by reversing the order of its digits. eg. 56 + 65 = 121, 125 + 521 = 646.

Some numbers become palindromes quickly after repeated reversal and addition, and are therefore not Lychrel numbers. All 1 digit and 2 digit numbers eventually become palindromes after repeated reversal and addition. About 80% of all numbers under 10,000 resolve into a palindrome in 4 or fewer steps. About 90% solve in 7 steps or less. Here are a few example non-Lychrel numbers:

56 becomes palindromic after one iteration: 56+65 = 121.
57 becomes palindromic after two iterations: 57+75 = 132, 132+231 = 363.
59 is not a Lychrel number since it becomes a palindrome after 3 iterations: 59+95 = 154, 154+451 = 605, 605+506 = 1111
89 takes an unusually large 24 iterations (the most of any number under 10,000 that is known to resolve into a palindrome) to reach the palindrome 8813200023188.
10,911 reaches the palindrome 4668731596684224866951378664 after 55 steps.
1,186,060,307,891,929,990 takes 261 iterations to reach the 119 digit palindrome
44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544,
which is the currently known world record for the Most Delayed Palindromic Number. It was solved by Jason Doucette's algorithm and program (using Benjamin Despres' reversal-addition code) on November 30, 2005.

The first known number starting from 0 that does not apparently form a palindrome is a three digit number, 196. It is the smallest Lychrel number candidate.

[edit] Proof not found

In other bases, certain numbers can be proven to never form a palindrome after repeated reversal and addition, [1] [2] but no such proof has been found for 196 and other base 10 numbers.

It is therefore conjectured (rather than proven) that 196 and other numbers which have not yet yielded a palindrome are Lychrel numbers, since it is not currently possible to prove that a number will never form a palindrome: only the converse can be proven - that it converges to a palindrome and is therefore not a Lychrel.

196 is therefore the first candidate Lychrel number. The first few candidate Lychrel numbers, from OEIS:A023108, are:

196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997.

The numbers in bold are Lychrel seed numbers (below). Computer programs by Jason Doucette, Ian Peters and Benjamin Despres have found other Lychrels. Indeed, Benjamin Despres' program has identified all Lychrel seeds numbers of each digit length starting with 1-digit numbers up to and including all 16-digit numbers have been tested so far. [3] Wade VanLandingham's site lists the total number of found Lychrel seed numbers for each digit length. [4]

The brute-force method originally deployed by John Walker has been refined to take advantage of iteration behaviours. For example, Vaughn Suite devised a program that only saves the first and last few digits of each iteration, enabling testing of the digit patterns in millions of iterations to be performed without having to save each entire iteration to a file [5]. But so far no algorithm has been developed to circumvent the reversal and addition iterative process.

[edit] Threads, seed and kin numbers

The term thread, coined by Jason Doucette, refers to the sequence of numbers that may or may not lead to a palindrome through the reverse and add process. Any given seed and its associated kin numbers will converge on the same thread. The thread does not include the original seed or kin number, but only the numbers that are common to both, after they converge.

Seed numbers are a subset of Lychrel numbers, that is the smallest number of each non palindrome producing thread. A seed number may be a palindrome itself. The first three examples are shown in bold in the list above.

Kin numbers are a subset of Lychrel numbers, that include all numbers of a thread, except the seed, or any number that will converge on a given thread after a single iteration. This term was introduced by Koji Yamashita in 1997.

[edit] 196 palindrome quest

Because 196 (base-10) is the lowest candidate Lychrel number it has received the most attention.

John Walker began the 196 Palindrome Quest on 12 August 1987 on a Sun 3/260 workstation. He wrote a C program to perform the reversal and addition iterations and to check for a palindrome after each step. The program ran in the background with a low priority and produced a checkpoint to a file every two hours and when the system was shutdown, recording the number reached so far and the number of iterations. It restarted itself automatically from the last checkpoint after every shutdown. It ran for almost three years, then terminated (as instructed) on May 24, 1990 with the message:

Stop point reached on pass 2,415,836.

Number contains 1,000,000 digits.

196 had grown to a number of one million digits after 2,415,836 iterations without reaching a palindrome. Walker published his findings on the Internet along with the last checkpoint, inviting others to resume the quest using the number reached so far.

In 1995, Tim Irvin took up the challenge and using a supercomputer reached the two million digit mark in only three months without finding a palindrome. Jason Doucette then followed suit and reached 12.5 million digits in May 2000. Wade VanLandingham used Jason Doucette's program to reach 13 million digits, a record published in Yes Mag: Canada's Science Magazine for Kids. Since June 2000, Wade VanLandingham has been carrying the flag using programs written by various enthusiasts. By May 1, 2006, VanLandingham had reached the 300 million digit mark (at a rate of one million digits every 5 to 7 days). A palindrome has yet to be found.

Other potential Lychrel numbers which have also been subjected to the same brute force method of repeated reversal addition include 879, 1997 and 7059: they have been taken to several million iterations with no palindrome being found. [6]