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 179-algorithm, after the most famous number associated with the process. In dozenal, no Lychrel numbers have been yet proved to exist, but many, including 179, 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, 67 + 76 = 121. As another example, 135 + 531 = 666.
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 X0% of all numbers under 10,000 resolve into a palindrome in 4 or fewer steps; about E0% of those resolve in 8 or fewer steps. Here are a few examples of non-Lychrel numbers:
- 67 becomes palindromic after one iteration: 67 + 76 = 121
- 68 becomes palindromic after two iterations: 68 + 86 = 132, 132 + 231 = 363
- 6E becomes a palindrome after 3 iterations: 6E + E6 = 165, 165 + 561 = 706, 706 + 607 = 1111
- XE becomes a palindrome after 12 iterations: XE + EX = 1X9, 1X9 + 9X1 = E8X, E8X + X8E = 1X59, 1X59 + 95X1 = E43X, E43X + X34E = 19789, 19789 + 98791 = E635X, E635X + X536E = 19E709, 19E709 + 907E91 = XX769X, XX769X + X967XX = 1982288, 1982288 + 8822891 = X5X4E59, X5X4E59 + 95E4X5X = 17E999E7, 17E999E7 + 7E999E71 = 97977968, 97977968 + 86977979 = 162733725, 162733725 + 527337261 = 689X6X986
The smallest known number that is not known to form a palindrome is 179. 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.
Formal definition of the process[]
Let be a natural number. We define the Lychrel function for a number base to be the following:
where is the number of digits in the number in base , and
is the value of each digit of the number. A number is a Lychrel number if there does not exist a natural number such that , where is the -th iteration of
Proof not found[]
In other bases (these bases are power of 2, such as base 2, base 4, base 8, and base 14), certain numbers can be proven to never form a palindrome after repeated reversal and addition, but no such proof has been found for 179 and other base 10 numbers.
It is conjectured that 179 and other numbers that have not yet yielded a palindrome are Lychrel numbers, but no number in dozenal has yet been proven to be Lychrel. Numbers which have not been demonstrated to be non-Lychrel are informally called "candidate Lychrel" numbers. The candidate Lychrel numbers up to 10000 are
- 179, 1E9, 278, 2E8, 377, 3E7, 476, 4E6, 575, 5E5, 674, 6E4, 773, 7E3, 872, 8E2, 971, 9E1, X2E, X3E, X5E, X70, XXE, XE0, E2X, E3X, E5X, EXX, 13E9, 14X9, 1599, 15E9, 1689, 16X9, 1779, 1799, 1869, 1889, 18E9, 1959, 1979, 19X9, 19E9, 1X49, 1X69, 1X99, 1XX9, 1E39, 1E59, 1E89, 1E99, 1EE9, 23E8, 24X8, 2598, 25E8, 2688, 26X8, 2778, 2798, 2868, 2888, 28E8, 2958, 2978, 29X8, 29E8, 2X48, 2X68, 2X98, 2XX8, 2E38, 2E58, 2E88, 2E98, 2EE8, 2EEE, 33E7, 34X7, 3597, 35E7, 3687, 36X7, 3777, 3797, 3867, 3887, 38E7, 3957, 3977, 39X7, 39E7, 3X47, 3X67, 3X97, 3XX7, 3E37, 3E57, 3E87, 3E97, 3EE7, 3EEX, 43E6, 44X6, 4596, 45E6, 4686, 46X6, 4776, 4796, 4866, 4886, 48E6, 4956, 4976, 49X6, 49E6, 4X46, 4X66, 4X96, 4XX6, 4E36, 4E56, 4E86, 4E96, 4EE6, 4EE9, 53E5, 54X5, 5595, 55E5, 5685, 56X5, 5775, 5795, 5865, 5885, 58E5, 5955, 5975, 59X5, 59E5, 5X45, 5X65, 5X95, 5XX5, 5E35, 5E55, 5E85, 5E95, 5EE5, 5EE8, 63E4, 64X4, 6594, 65E4, 6684, 66X4, 6774, 6794, 6864, 6884, 68E4, 6954, 6974, 69X4, 69E4, 6X44, 6X64, 6X94, 6XX4, 6E34, 6E54, 6E84, 6E94, 6EE4, 6EE7, 73E3, 74X3, 7593, 75E3, 7683, 76X3, 7773, 7793, 7863, 7883, 78E3, 7953, 7973, 79X3, 79E3, 7X43, 7X63, 7X93, 7XX3, 7E33, 7E53, 7E83, 7E93, 7EE3, 7EE6, 83E2, 84X2, 8592, 85E2, 8682, 86X2, 8772, 8792, 8862, 8882, 88E2, 8952, 8972, 89X2, 89E2, 8X42, 8X62, 8X92, 8XX2, 8E32, 8E52, 8E82, 8E92, 8EE2, 8EE5, 93E1, 94X1, 9591, 95E1, 9681, 96X1, 9771, 9791, 9861, 9881, 98E1, 9951, 9971, 99X1, 99E1, 9X41, 9X61, 9X91, 9XX1, 9E31, 9E51, 9E81, 9E91, 9EE1, 9EE4, X04E, X05E, X06E, X09E, X0XE, X13E, X14E, X15E, X18E, X19E, X22E, X23E, X24E, X27E, X28E, X31E, X32E, X33E, X36E, X37E, X3E0, X40E, X41E, X42E, X45E, X46E, X4X0, X4EE, X50E, X51E, X54E, X55E, X590, X5XE, X5E0, X5EE, X60E, X63E, X64E, X680, X69E, X6X0, X6XE, X6EE, X72E, X73E, X770, X78E, X790, X79E, X7XE, X81E, X82E, X860, X87E, X880, X88E, X89E, X8E0, X90E, X91E, X950, X96E, X970, X97E, X98E, X9X0, X9E0, X9EE, XX0E, XX40, XX5E, XX60, XX6E, XX7E, XX90, XXX0, XXXE, XXEE, XE30, XE4E, XE50, XE5E, XE6E, XE80, XE90, XE9E, XEXE, XEE0, XEE3, E04X, E05X, E06X, E07E, E09X, E0XX, E0XE, E13X, E14X, E15X, E16E, E18X, E19X, E19E, E22X, E23X, E24X, E25E, E27X, E28X, E28E, E31X, E32X, E33X, E34E, E36X, E37X, E37E, E40X, E41X, E42X, E43E, E45X, E46X, E46E, E4EX, E50X, E51X, E52E, E54X, E55X, E55E, E5XX, E5EX, E60X, E61E, E63X, E64X, E64E, E69X, E6XX, E6EX, E70E, E72X, E73X, E73E, E78X, E79X, E7XX, E7EE, E81X, E82X, E82E, E87X, E88X, E89X, E8XE, E90X, E91X, E91E, E96X, E97X, E98X, E99E, E9EX, EX0X, EX0E, EX5X, EX6X, EX7X, EX8E, EXXX, EXEX, EXEE, EE4X, EE5X, EE6X, EE7E, EE9X, EEXX, EEXE, EEE2, EEEE
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 or equal to 10 digits.
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.
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 11X5.
Other bases[]
In base 2, 10110 (1X in dozenal) has been proven to be a Lychrel number, since after 4 steps it reaches 10110100, after 8 steps it reaches 1011101000, after 10 steps it reaches 101111010000, and in general after 4n steps it reaches a number consisting of 10, followed by n+1 ones, followed by 01, followed by n+1 zeros. This number obviously cannot be a palindrome, and none of the other numbers in the sequence are palindromes.
Lychrel numbers have been proven to exist in the following bases: E, 15, 18, 22 and all powers of 2.
The smallest number in each base which could possibly be a Lychrel number are:
b | Smallest possible Lychrel number in base b written in base b (base 10) |
---|---|
2 | 10110 (1X) |
3 | 10201 (84) |
4 | 3333 (193) |
5 | 10313 (4E0) |
6 | 4555 (75E) |
7 | 10513 (1654) |
8 | 1775 (711) |
9 | 728 (415) |
X | 196 (144) |
E | 83X (703) |
10 | 179 (179) |
11 | 1:2:10:X (1691) |
12 | 1:E:E (261) |
13 | 1:12:10 (313) |
14 | 1:9:11 (2X5) |
15 | E:6:14 (1XX9) |
16 | 1:X:13 (373) |
17 | 15:16 (245) |
18 | 16:17 (277) |
19 | 1:10:16 (4E3) |
1X | 18:19 (325) |
1E | 19:1X (361) |
20 | 1X:1E (39E) |