Posts · Mathematics
In Binary, 22 Never Becomes a Palindrome
Reverse a number's digits and add. Repeat until the result reads the same backwards. In base ten nobody knows whether 196 ever gets there. In base two, 22 provably never does.
Take a number, reverse its digits, and add the two. Then do it again. Start with 87: 87 + 78 = 165, then 165 + 561 = 726, then 726 + 627 = 1353, then 1353 + 3531 = 4884. Four steps, and the result reads the same forwards and backwards. It is a palindrome, and the game stops.
Most numbers you try get there quickly. The smallest number that has never been seen to reach a palindrome is 196. Computers have followed it for decades, from John Walker's three-year search reported in 1990 to searches that pushed it past a billion digits in 2015, and no palindrome has appeared. Nobody knows whether one ever will, and no amount of searching that finds nothing can settle it. As a recent paper, Six Birds Foundations VI, puts it, "finite searches are evidence only."
Play the same game in base two, though, and there is an answer. Start from 22 and you can prove that no palindrome ever comes.
The first four steps
In base two, 22 is written 10110. Reversed, that is 01101, which is 13. So the first step is 22 + 13 = 35, and the game goes on. The paper calls each string of binary digits a word:
10110 → 100011 → 1010100 → 1101001 → 10110100
In ordinary numbers, that is 22 + 13 = 35, then 35 + 49 = 84, then 84 + 21 = 105, then 105 + 75 = 180. None of these is a palindrome. That alone proves nothing, since 196 also looks fine for as long as anyone has checked. What changes here is the shape of the fifth word.
Four shapes, forever
Read 10110100 in blocks: 10, then two 1s, then 01, then two 0s. From this point on, the paper shows, every word in the sequence has one of four shapes, and each shape turns into the next. Each shape has a size r, a whole number from 2 up, which stays fixed for one lap through the four shapes:
- 10, then r ones, then 01, then r zeros.
- 11, then r − 2 zeros, then 1, then 000, then r − 2 ones, then 01.
- 10, then r ones, then 01, then r + 1 zeros.
- 11, then r zeros, then 10, then r − 1 ones, then 01.
After the fourth shape the sequence comes back to the first, with r one larger. Here is the first lap, with r = 2. A block of "r − 2" digits is then empty, so the second shape is just 11, 1, 000, 01:
10110100 → 11100001 → 101101000 → 110010101 → 1011101000
That is 180 → 225 → 360 → 405 → 744, and the last word is the first shape again with r = 3. Each lap, r grows by one, the blocks whose length depends on r grow with it, and the sequence goes round forever.
None of the four shapes can read the same backwards. The first and third start with 1 and end with 0. The second and fourth start with 11 and end with 01, so read backwards they would start with 10. A palindrome needs its two ends to match, and these never do.
Checking each step
Why does each shape always turn into the next, for every r from 2 up? Write x for 2r. Then the value of each shape, and of its reversal, is a simple expression in x. For the first shape, the leading 1 is worth 8x2, the block of r ones is worth 4x2 − 4x, and the lone 1 just before the final zeros is worth x, so the whole word is worth 12x2 − 3x. The paper's table gives all four:
| Shape | Value | Reversed | Sum, which is the value of |
|---|---|---|---|
| 1 | 12x2 − 3x | 12x − 3 | 12x2 + 9x − 3, shape 2 |
| 2 | 12x2 + 9x − 3 | 12x2 − 15x + 3 | 24x2 − 6x, shape 3 |
| 3 | 24x2 − 6x | 12x − 3 | 24x2 + 6x − 3, shape 4 |
| 4 | 24x2 + 6x − 3 | 24x2 − 12x + 3 | 48x2 − 6x, shape 1 with r + 1 |
Each row is a line of school algebra. With r = 2, so x = 4, the first row says 180 + 45 = 225, which is the step you saw above. The rest follows because, in the paper's words, "Since a binary word is determined by its value, each identity of values is an identity of words." Both the four-shape cycle and the claim that 22 never reaches a palindrome are also checked in Lean, a proof assistant that verifies every logical step.
The law behind it
The general principle is almost too simple to state:
A run that enters a closed pattern containing no target stays in it and never reaches a target.
Strictly, it covers the run from the moment it enters, which is why the first four words of 22 were checked one by one. Here a run is the sequence of steps, the target is a palindrome, and a closed pattern is a set of words that the reverse-and-add step never leads out of, here the four shapes. If the sequence is inside the pattern now, the next step keeps it inside, and so does the one after that, forever. That is the whole proof. All of the work is in finding a closed pattern that contains no palindrome. The paper calls that condition the law's hard hypothesis, and it uses "law" in a technical sense: a general statement paired with a concrete case in which the hard hypothesis has actually been proved.
Why go round by a fence instead of following the digits? Adding in binary can carry a 1 a long way: 111 + 1 = 1000, and one carry has changed every digit. The paper names the law carry-horizon confinement for this reason. Predicting what the digits will do can take digits from deeper and deeper in, and "A closed family of states confines the run when prediction fails." The paper notes that it has not shown that this unpredictability really holds for base two in general. The proof about 22 does not need it. It does not predict the digits step by step; it fences them in.
The paper is part of Six Birds Theory, a research programme, and it catalogs thirteen general statements about step-by-step processes. For some of them, like this one, the hard part is proved in a concrete case; for others it is still open.
Why this does nothing for 196
It is tempting to hope that base ten has a pattern like this waiting for 196. The paper lists exactly that hope in a table of tempting conclusions and what blocks them: "None is known, and the base-2 family was found by hand for one orbit." (An orbit is the sequence of steps from one starting number.) A proof of this kind is what the paper calls a certificate: easy to check once you hold it, hard to find. A billion digits of 196 with no palindrome is evidence, not a certificate. The paper does not say why base two yielded such a pattern for 22, and nobody knows whether 196 has one.
That contrast is the point. The two problems look alike. More computing could only ever settle 196 one way, by finding a palindrome. To show that one never comes takes a proof, such as a fence like the one around 22, and for 196 nobody has one.
What it does not say
The result is not new, and the paper says so plainly: "The base-2 reverse-and-add result is recorded in the OEIS and on MathPages; we know of no refereed proof, and the one in Section 4.3 is self-contained." The On-Line Encyclopedia of Integer Sequences lists 22 as the smallest starting number in base two whose sequence never reaches a palindrome, and marks that entry, unlike its neighbors for other bases, as proved. Kevin Brown's MathPages site describes the same family. The paper labels nothing in it as new. What it adds is a short proof that stands on its own, every step checked by machine, and a clear statement of the law that makes it work.
It settles the sequence from 22, and from any word that already has one of the four shapes, but it does not sort out the other starting numbers in base two. It proves nothing about base ten, and says nothing about whether 196 is special or merely unlucky.
Drawn from Six Birds Foundations VI: A Catalog of Dynamical Structural Laws (Tsiokos, 2026, version 2, doi:10.5281/zenodo.23187548). The binary words of the first four steps, the four shapes, the table and the quotations are from the paper; the words of the first lap, the value of the first shape, the run from 87 and the carry example are simple arithmetic, and no new result is claimed by this essay. John Walker's search ("Three years of computing", 1990) is cited in the paper. The billion-digit search of 196 is Romain Dolbeau's (2015), as reported in Wikipedia's article on Lychrel numbers. The OEIS entry is A060382.