Lychrel numbers are natural numbers that do not (theoretically) ever become palindromes when you repeatedly reverse their digits and add it to the original. For example, the number 25 is clearly not a Lychrel number, as 25+52 = 77, and 77 is a palindrome. A large percentage of numbers are easily ruled out as Lychrel numbers, as they become palindromes in 1-2 steps. Some numbers, like 79, take a little more effort: 79+97 = 176, 176+671 = 847, 847+748 = 1595, 1595+5951 = 7546, 7546+6457 = 14003, 14003+30041 = 44044, finally a palindrome after 6 steps!
While I don’t believe that we have proved that any given number is indeed a Lychrel number, there are some numbers that after intensive calculation (i.e., trying 1,000s of iterations or more) simply don’t make a palindrome. These numbers are technically “Lychrel candidates,” and 196 is the smallest of them identified to date. (For those of you familiar with OEIS, the Lychrel candidates are A023108.)
In any case, there are some interesting number of steps that numbers require to be proven as “non-Lychrel.” For example, the numbers 60, 61, 62, and 63 all require just one iteration to become palindromes, and both 91 and 92 resolve to the same palindrome (91+19 = 110, 110+11 = 121 and 92+29 = 121.)
This week’s GeekDad Puzzle of the Week centers around the patterns that these steps counts make for consecutive counting numbers. What is the biggest run of consecutive steps counts (i.e., there are four numbers in a row from 60 to 63 that all take exactly one step) under 100,000? What is the biggest run of equivalent palindromes made (i.e., there are two numbers is a row that make “121” as their first palindrome) under 100,000? What is the longest sequence of steps (i.e., 5, 4, 3, 2, 1 or 1, 2, 3, 4, 5, etc.) found for consecutive counting numbers under 100,000 to make their first palindrome?
A quick note: For purposes of this puzzle, each number requires at least one step to reach a palindrome, even it starts as one. For example, 11+11 = 22, done! There are palindromes that are Lychrel candidates, i.e., 4994.
Normally, when we set up these puzzles, there are astounding, interesting and unusual “runs” or patterns in the data that are both easily found and relatively unique (or at least rare) across the range of values given. This week was a little different in that there was a large number of correct answers available, but they were not necessarily astounding.
If you were to traverse the set of numbers from 1 to 100,000, and determine the number of reasonable steps to disprove each number as “non-Lychrel” (if possible), the largest constant run of values was a set of 9 numbers in a row that all took the same number of steps. The smallest such run goes from 10 to 18, each value requiring just one step (10 + 01 = 11, 11 + 11 = 22, 12 + 21 = 33, … , 18 + 81 = 99) to become a palindrome. Overall, within the dataset, there were a whopping 341 such runs of 9 numbers in a row requiring just one step, with the last ranging from 22,099 to 22,107.
Additionally, there were some 69 sets of 9 consecutive numbers that resolved to palindromes in exactly two steps. The first such set ranged from 9,091 to 9,099 (9091 + 1909 = 11000, 11000 + 00011 = 11011, 9092 + 2909 = 12001, 12001 + 10021 = 22022 … 9099 + 9909 = 19008, 19008 + 80091 = 99099) and the last under 100,000 ranged from 99,901 to 99,909. The longest of consecutive numbers taking 3 steps to resolve was 5 in a row (such as 1,194 to 1,198) and there were 424 of them, and the longest runs of consecutive numbers taking 4 steps to resolve were 4 numbers in length (i.e., 21,388 to 21,391.) The largest sets requiring for 5 or 6 steps to resolve were 3 consecutive numbers in size, and anything larger that 7 steps in a row only came in consecutive pairs.
With respect to runs in the sets of steps, undramatically, the longest increasing runs of Lychrel counts were of length three, and there were a total of eight of them — the first being 247 (247 + 742 = 989), 248 (248 + 842 = 1090, 1090 + 0901 = 1991) and 249 (249 + 942 = 1191, 1191 + 1911 = 3102, 3102 + 2013 = 5115), and all of them starting under 1,000. The longest decreasing runs were of length 4, and there were 16 of them (the first runs from 9,289 to 9,292, the last from 99,019 to 99,022.)
Finally, the repeats of the palindromes made were limited only to paired repeats. That is, like in the example, the longest set of consecutive numbers that resolve to the same palindrome was simply a set of two numbers. This happened 107 in the span of values from 1 to 100,000, with the lowest being both 28 and 29 resolving to 121, and the largest being both 99,850 and 99,851 resolving to 157,651.
Congratulations to Marc Anderson for submitting a solution for this past week’s puzzle and being selected at random among the reasonably correct solutions submitted. A $50 gift certificate from the fine folks at ThinkGeek is on its way to Marc — it’s just that easy to win!
Thanks to everyone that submitted a solution, and happy puzzling!
Liked it? Take a second to support GeekDad and GeekMom on Patreon!
