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 proven to exist, but many, including 196, are suspected on heuristic and statistical grounds. The name "Lychrel" was coined by Wade Van Landingham 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% of those resolve in seven steps or fewer. 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 three 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. The smallest number that is not known to form a palindrome is 196. It is therefore the smallest Lychrel number candidate. The number resulting from the reversal of the digits of a Lychrel number not ending in zero is also a Lychrel number.
Formal definition of the process Let n {\displaystyle n} be a natural number. We define the Lychrel function for a number base b > 1, F b : N → N {\displaystyle F_{b}:\mathbb {N} \rightarrow \mathbb {N} } , to be the following:
F b ( n ) = n + ∑ i = 0 k − 1 d i b k − i − 1 {\displaystyle F_{b}(n)=n+\sum _{i=0}^{k-1}d_{i}b^{k-i-1}}
where k = ⌊ log b n ⌋ + 1 {\displaystyle k=\lfloor \log _{b}n\rfloor +1} is the number of digits in the number in base b {\displaystyle b} , and
d i = n mod b i + 1 − n mod b i b i {\displaystyle d_{i}={\frac {n{\bmod {b^{i+1}}}-n{\bmod {b}}^{i}}{b^{i}}}}
is the value of each digit of the number. A number is a Lychrel number if there does not exist a natural number i {\displaystyle i} such that F b i + 1 ( n ) = 2 F b i ( n ) {\displaystyle F_{b}^{i+1}(n)=2F_{b}^{i}(n)} , where F i {\displaystyle F^{i}} is the i {\displaystyle i} -th iteration of F {\displaystyle F}
Proof not found In other bases (these bases are powers of 2, like binary and hexadecimal), 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 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 absolutely demonstrated to be non-Lychrel are informally called "candidate Lychrel" numbers. The first few candidate Lychrel numbers (sequence A023108 in the 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. Wade Van Landingham'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. However, so far no algorithm has been developed to circumvent the reversal and addition iterative process.
… excerpt ends here. Continue reading the full article.
