Lychrel number

Lychrel number

A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its base 10 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. No Lychrel numbers are known, though many numbers are suspected Lychrels, the smallest being 196.

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 [http://www.jasondoucette.com/pal/89 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 [http://www.jasondoucette.com/pal/10911 55 steps] .
*1,186,060,307,891,929,990 takes [http://www.jasondoucette.com/pal/1186060307891929990 261 iterations] to reach the 119 digit palindrome
"44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544",
which is the currently known world record for the [http://www.jasondoucette.com/worldrecords.html#Most 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.

Proof not found

In other bases, certain numbers can be proven to never form a palindrome after repeated reversal and addition, [http://www.math.niu.edu/~rusin/known-math/96/palindrome] [http://www.mathpages.com/home/kmath004.htm] but no such proof has been found for 196 and other base 10 numbers.

It is conjectured that 196 and other numbers which have not yet yielded a palindrome are Lychrel numbers, but no number 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, from [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A023108 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 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. [http://www.p196.org/lychrel%20records.html] Wade VanLandingham's site lists the total number of found suspected Lychrel seed numbers for each digit length. [http://www.p196.org/lychrel%20seeds.html]

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 [http://home.cfl.rr.com/p196/math%20solutions.html] . But 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.

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 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 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. [http://web.archive.org/web/20061021025636/http://home.cfl.rr.com/p196/lychrel+records.html]

External links

* [http://www.fourmilab.ch/documents/threeyears/threeyears.html John Walker] - Three years of computing
* [http://www.fourmilab.ch/documents/threeyears/two_months_more.html Tim Irvin] - About two months of computing
* [http://www.jasondoucette.com/worldrecords.html Jason Doucette - World records] - 196 Palindrome Quest, Most Delayed Palindromic Number
* [http://users.tmok.com/~pla/Lychrel/Lychrel.shtml Benjamin Despres]
* [http://www.p196.org/ 196 and Other Lychrel Numbers] by Wade VanLandingham
*MathWorld|urlname=196-Algorithm|title=196-Algorithm
* [http://www.mathpages.com/home/kmath004.htm MathPages - Digit Reversal Sums Leading to Palindromes]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Lychrel-Zahl — Bei den Lychrel Zahlen handelt es sich um bestimmte natürliche Zahlen, die sich der Palindrombildung durch einen bestimmten Algorithmus, dem 196 Algorithmus widersetzen. Der Name Lychrel stammt von Wade VanLandingham und hat keine besondere… …   Deutsch Wikipedia

  • Palindromic number — A palindromic number or numeral palindrome is a symmetrical number like 16461, that remains the same when its digits are reversed. The term palindromic is derived from palindrome, which refers to a word like rotor that remains unchanged under… …   Wikipedia

  • Nombre de Lychrel — Un nombre de Lychrel est un nombre naturel qui ne peut pas former de nombre palindrome lorsqu il est soumis au processus itératif qui consiste à l additionner au nombre formé de l inversion de ses chiffres en base 10. Le nom « Lychrel » …   Wikipédia en Français

  • 89 (number) — 89 (eighty nine) is the natural number following 88 and preceding 90. ← 88 90 → 89 ← 80 …   Wikipedia

  • 196 (number) — 196 is a natural number following 195 and preceding 197. It is the square of 14. In addition to being a square number, it is also an 11 gonal number, a 34 gonal number, a heptagonal pyramidal number, and a pentagonal pyramidal number.196 is also… …   Wikipedia

  • Проблема 196 — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии. Проблема 196  условное название нерешённой математической задачи: неизвестно, приведёт ли о …   Википедия

  • Numerical digit — The ten digits of the Arabic numerals, in order of value. A digit is a symbol (a numeral symbol such as 3 or 7 ) used in combinations (such as 37 ) to represent numbers in positional numeral systems. The name digit comes from the fact that the 10 …   Wikipedia

  • Unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Millennium Prize Problems Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, the six ones yet to be solved are:… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Palindrom-Zahlen — Zahlenpalindrome bzw. Palindromzahlen sind natürliche Zahlen, deren Zahlensystemdarstellung von vorne und hinten gelesen den gleichen Wert hat, z. B. 1331 oder 742247, aber auch 21 zur Basis 2 (=10101). Manchmal wird auch die allgemeine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”