Reverse, add, and wait for a palindrome
Worth reading first: The question nobody can answer · The heuristic that cannot be a proof.
Start with 57. Its reversal is 75, and . Reverse and add again: , 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
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
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 -digit number is to be a palindrome. A palindrome is determined by its first half: the last digits must copy the first in reverse. So among -digit numbers, palindromes are about one in . If the orbit’s numbers were random numbers of their length, the chance of meeting a palindrome at step would be about , and the expected number of palindromes after step 100 would be about . 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 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 , symmetric in . 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: , 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
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 : ,
- step : ,
- step : ,
- step : ,
where means a block of ones. At step 8, and the first shape is 10 111 01 000. At step 12, 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
Following the shapes forever is a statement about every value of at once, and it has a short proof by blocks. Take the first shape, , and add it to its reversal, , which after dropping the leading zeros is 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 replaced by . 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 .
The figure checks the symbolic rule — each shape steps to the next — for every 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 , since a block of ones plus a block of zeros behaves the same way for every .
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
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 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.
- The sum of the parts, taken again — both name iteration, open problem, orbit
- A difference too small to draw — both name iteration, orbit
- A point that pulls, and a point that pushes — both name iteration, orbit
- One c, one picture — both name iteration, orbit
- Square it and keep the middle — both name iteration, orbit
- The numbers that fool every base — both name heuristic, open problem
Named objects
A dashed tag is an object no other essay names yet.