Dynamics

Reverse, add, and wait for a palindrome

Take a number, add it to its own reversal, and repeat until the result reads the same both ways. 89 needs 24 steps; every start below 10,000 arrives within 24 steps, except 249 that have never been seen to arrive at all, beginning with 196. Nobody can prove that 196 never does. In base 2 the question has been settled for 22, written 10110: its orbit falls into four shapes of digit string that turn into one another, each a little longer every cycle, and no shape can read the same backwards.

Worth reading first: The question nobody can answer · The heuristic that cannot be a proof.

Start with 57. Its reversal is 75, and 57+75=13257 + 75 = 132. Reverse and add again: 132+231=363132 + 231 = 363, which reads the same backwards. Start with 89 and the process takes twenty-four steps, passing through numbers like 8,872,688 and 1,801,200,002,107, before landing on the palindrome 8,813,200,023,188. Start with 196 and nobody has ever seen it stop. Computer runs have carried 196’s orbit through billions of steps, to numbers with more than a billion digits, without meeting a palindrome.

The process is called reverse and add, and numbers like 196 that seem never to reach a palindrome are called Lychrel numbers, though not one has been proved to be one in base ten. The question nobody can answer introduced another iteration of the same kind — halve the even numbers, triple the odd ones and add one — and the reasons that question is hard. Reverse and add is hard for related reasons and some different ones. It also has a feature that the Collatz problem lacks: change the base, and in base two the problem has been solved, for a reason that can be drawn.

Twenty-four steps, or never

Steps to a palindrome, for every start below 10,000. 1:2837 2:2892 3:1356 4:926 5:423 6:405 7:248 8:64 9:64 10:13 11:52 12:110 13:70 14:4 15:83 16:59 17:14 18:27 19:1 20:26 21:64 22:2 23:8 24:2 none:249
Fig. 1 Every start below 10,000 by the number of steps it takes to reach a palindrome. None takes more than 24, and 249 have not arrived after 300 steps.

The figure runs every start from 1 to 9,999 for up to 300 steps. Most reach a palindrome at once: 2,837 after one step and 2,892 after two. The counts thin out quickly, and the longest any start takes is 24 steps, a distinction shared by 89 and its reversal 98, which have the same orbit after the first step. Then there is a gap. No start below 10,000 needs 25 steps, or 50, or 299. The 249 that have not arrived after 24 steps have not arrived after 300 either.

That gap is the first sign of what is going on. If a start’s orbit has not reached a palindrome quickly, its numbers grow longer by a digit every two or three steps, and the chance that a long number happens to be a palindrome is tiny. So the starts divide sharply into those that arrive early and those that, as far as anyone can tell, never arrive. Larger searches show the same shape at every scale: the longest journey known to end, found by computer search, is 261 steps from a nineteen-digit start.

The first unresolved start is 196. The next few are 295, 394, 493, 592, 689, 691 and 788, and the figure’s companion below shows that most of these are not separate questions at all.

The orbit of 196, and why it probably never stops

The orbit of 196 and the shrinking chance of a palindrome. 500:216 1000:411 1500:622 2000:834 2500:1049 3000:1268
Fig. 2 The number of digits in 196’s orbit over 3,000 steps, none of them a palindrome. The orbit gains about 0.42 digits a step, and the chance of a palindrome shrinks geometrically.

A number plus its reversal is roughly twice as large as the number, sometimes nearly ten times as large when the reversal’s leading digit is large, and on average the figure finds 196’s orbit gaining about 0.42 digits a step: after 3,000 steps the number has 1,268 digits. That growth is very steady, which is what one would expect if the digits behaved like random digits.

Now ask how likely a dd-digit number is to be a palindrome. A palindrome is determined by its first half: the last d/2d/2 digits must copy the first d/2d/2 in reverse. So among dd-digit numbers, palindromes are about one in 10d/210^{d/2}. If the orbit’s numbers were random numbers of their length, the chance of meeting a palindrome at step ss would be about 10−0.21s10^{-0.21 s}, and the expected number of palindromes after step 100 would be about 10−2110^{-21}. On that model 196 has essentially no chance of ever reaching a palindrome, and the same is true of any start that survives the first few dozen steps.

That is a heuristic, and it cannot be a proof, for the reason the heuristic that cannot be a proof gave for the Collatz problem’s drift argument: the orbit’s digits are not random. They are produced by a deterministic rule, and the rule could conspire to produce a palindrome at step 1010010^{100} without any statistical test noticing. The heuristic also predicts that almost every start reaches a palindrome quickly if it does at all, which is what the first figure shows; it explains the data. It does not prove anything about any individual orbit.

In fact the reverse-and-add rule does have strong structure that random numbers lack. A number plus its reversal is itself a palindrome whenever no carries occur, since then each digit of the sum is ai+ad−1−ia_i + a_{d-1-i}, symmetric in ii. Carries are what break the symmetry. Orbits that survive are orbits in which carries keep happening in asymmetric places, and the digit patterns of 196’s orbit show long stretches of digits that interact with the carries in structured ways. Nobody has turned that structure into a proof in base ten.

One step, and the carries that spoil it

The first figure’s tallest bar is easy to explain, and the explanation shows where the difficulty lives. Of the 2,837 starts below 10,000 that reach a palindrome in one step, 2,749 are numbers whose mirrored digits never add up to ten or more — 12, 132, 3,041 — so that adding the reversal produces no carries at all and the sum is automatically symmetric. Only 88 one-step arrivals involve carries, and they arrive by luck of a particular kind: 29+92=12129 + 92 = 121, where the carries happen to fall symmetrically. Being a palindrome after one step is almost entirely a question of avoiding carries.

After the first step, though, every number in an orbit is a sum of a number and its reversal, and such sums have a special form: the digit pairs equidistant from the ends add up to the same thing before carries are applied. The orbit is therefore always one carry pattern away from a palindrome. What decides whether it gets there is whether the next addition’s carries are symmetric, and that depends on the whole digit string, through carries that ripple from the right end towards the left. Reverse and add is a simple rule acting on a number’s digits, but the carries make each digit of the result depend on every digit to its right — the same mixing of local and global that every pattern happens exactly once found in the Collatz map, where the parity of a number after many steps depends on all of its low-order bits.

That is also why the problem is so sensitive to the base. Fourteen fractions that list the primes showed that iterations defined by simple arithmetic rules can carry out any computation whatever, so that some questions about them are undecidable in general. Nothing like that is known for reverse and add, and the binary proof below shows that in at least one base the carries can be tamed. But the rule’s whole behaviour is in its carries, and in base ten nobody has found a way to describe them over an unbounded number of steps.

The binary orbit of 22

Twenty-two in binary never becomes a palindrome. 10110 100011 1010100 1101001 10110100 11100001 101101000 110010101 1011101000 1101000101 10111010000 11000101101 101111010000 110010001101 1011110100000 1100001011101 10111110100000 11000100011101 101111101000000 110000010111101 1011111101000000 1100001000111101 10111111010000000 11000000101111101 101111111010000000
Fig. 3 22, which is 10110 in binary, under reverse and add in base 2. From the eighth step its strings cycle through four shapes, each block growing by one digit every four steps; none of the shapes can read the same backwards.

In base 2, reverse and add uses binary reversal and binary addition, and the smallest start that seems never to reach a palindrome is 22, written 10110. The figure draws its orbit one row per step, with the ones shaded. For the first seven steps the strings look irregular: 100011, 1010100, 1101001, 10110100, 11100001. From the eighth step on, something remarkable happens. The strings fall into four repeating shapes, each a sequence of solid blocks of ones and zeros:

  • step 4t4t: 10 1t+1 01 0t+110\,1^{t+1}\,01\,0^{t+1},
  • step 4t+14t + 1: 11 0t−1 1000 1t−1 0111\,0^{t-1}\,1000\,1^{t-1}\,01,
  • step 4t+24t + 2: 10 1t+1 01 0t+210\,1^{t+1}\,01\,0^{t+2},
  • step 4t+34t + 3: 11 0t+1 10 1t 0111\,0^{t+1}\,10\,1^{t}\,01,

where 1k1^k means a block of kk ones. At step 8, t=2t = 2 and the first shape is 10 111 01 000. At step 12, t=3t = 3 and it is 10 1111 01 0000, one digit longer in each block. Every fourth step the same four shapes recur, with every block one digit longer than before.

None of the four shapes is a palindrome, and the reason is visible at the ends. The first and third begin with 1 and end with 0, so their reversals begin with 0 — they cannot match. The second and fourth begin with 11 and end with 01, so their reversals begin with 10 — they cannot match either. So if the orbit really does follow the four shapes forever, it never reaches a palindrome.

Four shapes that turn into each other

Four shapes that turn into each other. checked 1200 steps; e.g. 101111010000 110010001101 1011110100000 1100001011101
Fig. 4 The four shapes for three values of t. Adding each to its reverse produces the next, and the fourth produces the first with every block one digit longer — for every t.

Following the shapes forever is a statement about every value of tt at once, and it has a short proof by blocks. Take the first shape, 10 1t+1 01 0t+110\,1^{t+1}\,01\,0^{t+1}, and add it to its reversal, 0t+1 10 1t+1 010^{t+1}\,10\,1^{t+1}\,01, which after dropping the leading zeros is 10 1t+1 0110\,1^{t+1}\,01 shifted right. The addition can be done block by block: where a block of ones meets a block of zeros the sum is just ones, with no carries; where ones meet ones, a carry starts and ripples along the block, turning it into zeros and depositing a one at its end. Writing out the carries for the four shapes, each one turns into the next, and the fourth turns into the first with tt replaced by t+1t + 1. The carries always happen in the same places relative to the blocks, whatever the blocks’ lengths, and that is why the rule holds for every tt.

The figure checks the symbolic rule — each shape steps to the next — for every tt up to 40, by building the shape and adding it to its reverse, and it also runs the actual orbit of 22 for 300 complete cycles, 1,200 steps, confirming that every string is the predicted shape, out to strings over 600 digits long. The symbolic check is the proof, made concrete: it is the same calculation for every tt, since a block of kk ones plus a block of kk zeros behaves the same way for every kk.

So 22 is a binary Lychrel number, proved, and its proof is exactly the kind of argument that has not been found for 196: a finite pattern of blocks that the rule maps to itself with every block lengthened. Ronald Brent studied these binary patterns in 1990, and the orbit of 22 is the cleanest example. In base two, the carries in an orbit like this fall into a self-reproducing pattern. In base ten, the carries of 196’s orbit look disordered, and nobody has found any finite description of them that the rule preserves.

Two hundred and forty-nine starts, five questions

Five orbits behind 249 unresolved starts. 196:113 879:72 1997:30 7059:33 9999:1
Fig. 5 The 249 unresolved starts below 10,000, grouped by whose orbit they join within 60 steps. 113 join the orbit of 196, and only five separate orbits remain.

Many unresolved starts are not independent. 196 plus its reversal is 887, and so is 295 plus its reversal, and 394 plus 493, and 592 plus 295. All five starts reach 887 at the first step and share an orbit from then on: if one reaches a palindrome they all do. 689 joins 196’s orbit at the second step, at 1,675.

The figure groups all 249 unresolved starts by whose orbit they join within 60 steps, and finds only five orbits: 113 starts join the orbit of 196, 72 join that of 879, 33 that of 7,059, 30 that of 1,997, and one, 9,999, stands alone so far. Below 10,000 there are not 249 open questions but five. The orbit of 196 is the oldest of them and the most studied, and it carries almost half of the unresolved starts below ten thousand with it.

This merging is common in iterations. Fifty-four numbers funnel into 6174 found Kaprekar’s digit-sorting routine sending every four-digit start into a single fixed point by a tree of merging orbits, and the question nobody can answer drew the Collatz orbits as a tree converging on 1. Reverse and add has the opposite character. Its orbits merge only near their beginnings, because once numbers are long the chance that two orbits collide is as small as the chance that one becomes a palindrome; after the first few steps, each surviving orbit grows off on its own.

The first unresolved start in every base

The first unresolved start in every base. 2:22(10110) 3:100(10201) 4:255(3333) 5:708(10313) 6:1079(4555) 7:2656(10513) 8:1021(1775) 9:593(728) 10:196(196)
Fig. 6 The smallest start reaching no palindrome within 300 steps, in each base from 2 to 10. Only in base 2 is it known never to arrive.

The question can be asked in any base, and the smallest unresolved start varies irregularly: 22 in base 2, 100 in base 3, 255 in base 4, 708 in base 5, 1,079 in base 6, 2,656 in base 7, 1,021 in base 8, 593 in base 9 and 196 in base 10. In base 4, the smallest is 255, written 3333 — a palindrome to begin with, whose orbit then leaves the palindromes and has never been seen to return. In base 3 the smallest is 100, written 10201, also a palindrome. Starting from a palindrome is no help: one step of reverse and add from a palindrome just doubles it, and doubling generally produces carries that destroy the symmetry.

In base 2, the four-shape argument settles 22. For the other bases in the table, the figure’s evidence is only that no palindrome appears in 300 steps, and whether a block pattern like base 2’s governs any of those orbits is not something the table tests. The difference between bases is a difference in how carries propagate. In base 2 a carry occurs exactly when two ones meet, so the carries are determined by where the blocks overlap, and block patterns can reproduce themselves. In base 10 a carry depends on whether two digits sum to ten or more, and the sum of two random digits does so with probability 0.45 — a coin toss, with no reason for a pattern to survive.

What the figures cannot show

The figures show 196’s orbit for 3,000 steps and the heuristic that predicts it never reaches a palindrome. They cannot show that it never does, and the heuristic gives no help with that: it predicts that palindromes become rare, not that they are impossible, and a deterministic rule can make a rare event happen. How high an orbit climbs faced the same gap for Collatz orbits, where the statistics are excellent and the proofs absent.

Nor do the figures show that base ten has no block pattern for 196. The orbit’s digits look random to the eye and to the simple statistics measured here, but a self-reproducing pattern could in principle exist at a scale or in a coordinate system that has not been tried. Searches for patterns in 196’s orbit have found none, and the absence of a pattern is not a proof of the absence of a palindrome either. The two questions — does 196 ever reach a palindrome, and is there a provable reason it does not — are both open.

The binary proof also hides one thing in its drawing: why the orbit of 22 should fall into the four shapes in the first place. The proof shows that once the orbit is in the shapes it stays there; the entry, at step 8, is just a computation. For other binary starts the orbit can wander for a long time before entering a pattern, or enter a different pattern, and there is no general theory saying which starts eventually settle into a self-reproducing pattern. Where the Collatz map is a coin found that the Collatz map becomes simple on the 2-adic integers, where every pattern of parities occurs; reverse and add has no comparable extension, because reversing digits needs to know where the number ends.

Still open: whether 196 ever arrives

Is 196 a Lychrel number in base ten — does its orbit never reach a palindrome? Nobody knows, and the same is true for every other base-ten candidate. No base-ten Lychrel number has been proved to exist, and there is no proof that any particular start, such as 196, fails to reach a palindrome; on the other hand there is no proof that every start eventually does. It is not even known whether the set of base-ten starts that reach a palindrome has density 1 among all whole numbers, although the heuristic suggests it does not — that a positive proportion of large numbers never arrive. Almost every number comes down showed how much can be proved about Collatz orbits for almost every start; for reverse and add, even the almost-every statement is open, and the one proved case of a start that never arrives lives in base two.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

Binary expansionCollatzHeuristicIterationOpen problemOrbit