Lychrel number
Encyclopedia
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.
e.g. 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 examples of non-Lychrel numbers:
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.
It is conjecture
d 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 are:
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. Wade VanLandingham's site lists the total number of found suspected Lychrel seed numbers for each digit length.
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. But so far no algorithm
has been developed to circumvent the reversal and addition iterative process.
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.
(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:
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 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.
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
which cannot form a palindrome
Palindrome
A palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers....
through the iterative
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
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
Anagram
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse, A decimal point = I'm a dot in place, Tom Marvolo Riddle = I am Lord Voldemort. Someone who...
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.e.g. 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 examples of 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 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
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
that does not apparently form a palindrome is a three digit number, 196
196 (number)
196 is the natural number following 195 and preceding 197.-In mathematics:* 196 is an even number* 196 is an abundant number, as 203 is greater than 196* 196 is a composite number...
. 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, but no such proof has been found for 196 and other base 10 numbers.It is conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
d 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 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
Ian Peters
Ian Peters was a New Zealand politician of the National Party.He represented the Tongariro electorate in Parliament from 1990 to 1993, when he was defeated by Mark Burton...
and Benjamin Despres have found other Lychrel candidates. Indeed, Benjamin Despres' program has identified all suspected Lychrel seed numbers of less than 17 digits. Wade VanLandingham's site lists the total number of found suspected Lychrel seed numbers for each digit length.
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. But so far no algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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 sequenceSequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in 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
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
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 196196 (number)
196 is the natural number following 195 and preceding 197.-In mathematics:* 196 is an even number* 196 is an abundant number, as 203 is greater than 196* 196 is a composite number...
(base-10) is the lowest candidate Lychrel number it has received the most attention.
John Walker
John Walker (programmer)
John Walker is a computer programmer and a co-founder of the computer-aided design software company Autodesk, and a co-author of early versions of AutoCAD, a product Autodesk originally acquired from programmer Michael Riddle...
began the 196 Palindrome Quest on 12 August 1987 on a Sun
Sun Microsystems
Sun Microsystems, Inc. was a company that sold :computers, computer components, :computer software, and :information technology services. Sun was founded on February 24, 1982...
3/260 workstation. He wrote a C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
program to perform the reversal and addition iterations and to check for a palindrome after each step. The program ran in the background
Background (computer software)
A background process is a computer process that runs "behind the scenes" and without user intervention. Typical tasks for these processes include logging, system monitoring, scheduling, and user notification....
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 used a supercomputer
Supercomputer
A supercomputer is a computer at the frontline of current processing capacity, particularly speed of calculation.Supercomputers are used for highly calculation-intensive tasks such as problems including quantum physics, weather forecasting, climate research, molecular modeling A supercomputer is a...
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 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.
External links
- John Walker - Three years of computing
- Tim Irvin - About two months of computing
- Jason Doucette - World records - 196 Palindrome Quest, Most Delayed Palindromic Number
- Benjamin Despres
- 196 and Other Lychrel Numbers by Wade VanLandingham
- MathPages - Digit Reversal Sums Leading to Palindromes