Lychrel number

List of unsolved problems in mathematics
Do any base-10 Lychrel numbers exist?

A Lychrel number is a natural number that cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. This process is sometimes called the 196-algorithm, after the most famous number associated with the process. In base ten, no Lychrel numbers have been yet proved to exist, but many, including 196, are suspected on heuristic[1] and statistical grounds. The name "Lychrel" was coined by Wade VanLandingham as a rough anagram of Cheryl, his girlfriend's first name.

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. For example, 56 + 65 = 121. As another example, 125 + 521 = 646.

Some numbers become palindromes quickly after repeated reversal and addition, and are therefore not Lychrel numbers. All one-digit and two-digit numbers eventually become palindromes after repeated reversal and addition.

About 80% of all numbers under 10,000 resolve into a palindrome in four or fewer steps. About 90% resolve in seven steps or fewer. Here are a few examples of non-Lychrel numbers:

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

The number resulting from the reversal of the digits of a Lychrel number is also a Lychrel number.

Proof not found

In other bases (these bases are power of 2, like binary and hexadecimal), certain numbers can be proven to never form a palindrome after repeated reversal and addition,[2][3] but no such proof has been found for 196 and other base 10 numbers.

It is conjectured that 196 and other numbers that have not yet yielded a palindrome are Lychrel numbers, but no number in base ten has yet been proven to be Lychrel. Numbers which have not been demonstrated to be non-Lychrel are informally called "candidate Lychrel" numbers. The first few candidate Lychrel numbers (sequence A023108 in OEIS) 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 suspected Lychrel seed numbers (see below). Computer programs by Jason Doucette, Ian Peters and Benjamin Despres have found other Lychrel candidates. Indeed, Benjamin Despres' program has identified all suspected Lychrel seed numbers of less than 17 digits.[4] Wade VanLandingham's site lists the total number of found suspected Lychrel seed numbers for each digit length.[5]

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.[6] However, so far no algorithm has been developed to circumvent the reversal and addition iterative process.

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.

196 palindrome quest

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

In the 1980s the 196 palindrome problem attracted the attention of microcomputer hobbyists, with search programs by Jim Butterfield and others appearing in several mass-market computing magazines.[7][8][9] In 1985 a program by James Killman ran unsuccessfully for over 28 days, cycling through 12,954 passes and reaching a 5366-digit number.[9]

John Walker began his 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 shut down, 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 24 May 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 used a supercomputer and 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 1 May 2006, VanLandingham had reached the 300 million digit mark (at a rate of one million digits every 5 to 7 days). Using distributed processing,[10] in 2011 Romain Dolbeau completed a billion iterations to produce a number with 413,930,770 digits, and in July 2012 his calculations reached a number with 600 million digits.[11] 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.[12]

References

  1. ↑ http://mathoverflow.net/questions/117104/status-of-the-196-conjecture/117277#117277
  2. ↑ http://www.math.niu.edu/~rusin/known-math/96/palindrome
  3. ↑ http://www.mathpages.com/home/kmath004/kmath004.htm
  4. ↑ http://www.p196.org/lychrel_records.html
  5. ↑ http://www.p196.org/lychrel_seeds.html
  6. ↑ http://home.cfl.rr.com/p196/math%20solutions.html
  7. ↑ "Bits and Pieces". The Transactor (Transactor Publishing) 4 (6): 16–23. 1984. Retrieved 26 December 2014.
  8. ↑ Rupert, Dale (October 1984). "Commodares: Programming Challenges". Ahoy! (Ion International) (10): 23,97–98.
  9. ↑ 9.0 9.1 Rupert, Dale (June 1985). "Commodares: Programming Challenges". Ahoy! (Ion International) (18): 81–84,114.
  10. ↑ http://www.isc-events.com/isc14_ap/presentationdetails.htm?t=presentation&o=264&a=select&ra=sessiondetails
  11. ↑ http://www.dolbeau.name/dolbeau/p196/p196.html
  12. ↑ Lychrel Records at the Wayback Machine (archived October 21, 2006)

External links