Status of the 196 conjecture?

Question

A palindrome is a number which remains the same when reversing it, for instance 34143. Now pick an arbitrary number, say 26: then 26+62=88 is a palindrome. If the number was 57, then 57+75=132 is not a palindrome; but 132+231=363 is.

In general, iterating $a_1\ldots a_n\to a_1\ldots a_n+a_n\ldots a_1$ always seems to lead to a palindrome. But, the point is that this doesn't work for 196!

This problem is well-known, and there is a heavy numerical evidence for it, see http://en.wikipedia.org/wiki/Lychrel_number and http://www.p196.org/. I was wondering, is there any theoretical advance on this subject? Or at least, to which math area does this problem belong to? Many thanks.

Answer 1

The progress (which may not be recent) appears to be in programming tricks to push the iterations starting from 196 into more and more millions of digits.

It is not true that iterating almost always seems to lead to a palindrome. Unless iterating leads to a palindrome "fairly quickly," one almost never seems to arrive at a palindrome. For a number with few digits, an eventual palindrome is fairly likely. As the number of digits grows the likelihood seems to decrease rapidly. Let $s(x)$ be the result of applying the reverse and add operation to $x$. There is no proof which rules out the possibility that for all $x$ there is a $j$ with $s^j(x)$ a palindrome, but it seems highly unlikely. If we examine a large range of numbers and classify $x$ as a probably never getting to a palindrome if none of $s(x),s^2(x),..s^{50}(x)$ is a palindrome then we will have some errors (probably under $1\\%$) which can be discovered by pushing out to $s^{500}(x)$. But if we push out that far, or even just to $s^{300}(x)$ then we are likely to never have an error (that we can discover.)

There is (according to Wikipedia) a 19 digit number which arrives at a palindrome after 261 iterations and this is the current record. I tried 500 random 10 digit integers (actually, random integers under $10^{10}.$) Of them, 224 went to 300 iterations without a palindrome. There were 13 cases which did arrive at a palindrome but taking at least 30 iterations. They took 30,30,32,32,32,34,38,41,42,46,49,66 and 88 iterations.

Further discussion Some observations and questions in no special order:

Let $r(x)$ be the reverse of $x$ and $s(x)=x+r(x)$ be the result of applying the reverse and add operation to $x$.

• If $x$ is a multiple of $11$ so is $r(x)$ and hence $s(x)$ and all future iterates $s^i(x)$
• if $x$ has an even number of digits then $s(x)$ is a multiple of $11$
• A palindrome with an even number of digits is a multiple of 11.
• Of the $9\cdot10^M$ palindromes with $2M+1$ digits, about $\frac{1}{11}$ are multiples of $11.$

Call $x$ special if no carries occur in the addition $x+r(x).$ In this case $x+r(x)$ is a palindrome. Call $x$ exceptional if $x+r(x)$ is a palindrome but $x$ is not special (i.e. some carries do occur). By definition, $s(x)$ is a palindrome exactly when $x$ is special or exceptional.

If $z=s(y)$ then when we appropriately match up $z$ with $r(z)$, corresponding digits will be equal or differ by $1$ (in case of a carry immediately before one but not the other.) Here appropriately means that when $z$ has one more digit than $y$ we do not match the leading $1$,

So, if $x$ has an even number $2M$ of digits then $s(x)$ is a multiple of $11$ which, if not a palindrome, misses it only by having some positions which should be equal differ by $1$ and perhaps having a leading $2M+1$st digit which is a $1$. If $x$ has an odd number of digits then almost the same is true.

The previous comments shows that integers of the form $s(x)$ are fairly special. What can be said about numbers of the form $s^2(x)$, $s^3(x)$ etc? Certainly by $s^6(x)$ (and usually earlier) we have had an even number of digits at some earlier stage and hence are at a multiple of $11$ from then on.

Clearly there must be many solutions of $s(x)=s(y)$ with $x \ne y$ since the the image set is much sparser. We can see that directly because for $y=\sum_0^{N-1}a_i10^i$ we have $s(y)=\sum_0^{N-1}(a_i+a_{N-1-i})10^i.$ This usually presents many chances to increase one of $a_i,a_{N-1-i}$ by $1,2,3$ or even more and lower the other by an equal amount to get $x$ with $s(x)=s(y).$

Recall that every $y$ with $s(y)$ a palindrome is special or exceptional (and vice versa). Roughly $(1.8)^{-N/2}$ of the $N$ digit integers $z$ are special and I do not see that knowing also that $z=s^j(x)$ for some $x$ changes that. So for small starting $x$ there is a fair chance of getting to a special number as we repeatedly apply $s$. However this chance gets smaller as the number of digits rises. This suggests that if iterating $s(x)$ gets into enough digits without running into a palindrome, it is unlikely to ever arrive at one.

Here is some justification of the counts: Let $N=2M$ be even. There are $9\cdot10^{N-1}$ integers $x=\sum_{0}^{N-1}x_i10^i$ with $N$ digits. The proportions of these which are special and exceptional are easy to give exactly but less than $\frac{1}{1.8^M}$ of them are special and and less than $\frac{1}{10^M}$ are exceptional. This is because there are $100$ ways to pick each of the $M$ pairs $x_i,x_{N-i-1}$ (except for $90$ ways to pick $x_0,X_N$.) To be special there are only $55$ choices with $x_i+x_{N-i-1}\le 9$ (except $45$ for $i=0$). A number is exceptional if each pair $x_i,x_{N-1-i}$ has sum $0$ or $11.$ (I think I proved that to my satisfaction.) For $N=2M+1$ the ratios are about the same taking into account the central digit.

Final thoughts Here is an easier related problem which might be called the 49 problem, I don't know if there is a 49+49=98 problem although we have just looked at the 98+98=196 problem. 196+196=392 and I've spent time on the 392 problem but it is unrelated. Here is the 49 problem: Call an integer $z$ very even if all digits are even (equivalently,if $z=d(x)=x+x$ for an $x$ with all digits less than $5$) .

Q: for which $n$ does $n,d(n),d^2(n),\cdots$ arrive at a very even integer?

Up to 20001 there is a single starter which gets to a very even number after 47 doublings but no sooner. Curiously 49,98,196,392,... is the first example which never seems to arrive at a very even number. I actually included this example because I thought there would be some integers which provably never lead to a very even number. My proposed proof was that $x,d(x),d^2(x),\cdots$ is eventually periodic mod $10^j$ for any $j$, so one would just need to find the appropriate $j$ where every member of the cycle had an odd digit. However now I see that the $\mod 10^j$ orbit has length $4\cdot 5^{j-1}$ so almost surely does have a $j$ digit very even member (which may be the tail end of much much longer integers with plenty of room for odd digits.) However it seems clear that when the number of digits is small there is a reasonable chance of bumping into a very even number but that goes to $0$ exponentially in $d$ for a "random" $d$-digit number. It would be nice to find some invariant for your problem, or for this one, (similar to the proposed reduce mod $10^j$ here) which could rule out a palindrome. Short of something like that it seems hard to imagine a definitive proof (as opposed to probabilistic heuristic) of never arriving at a palindrome.

Answer 2

Here are some heuristic calculations. Let $r(x)$ be the reversal of $x$ in base 10, $s(x)=x+r(x)$, and $f(x)=s(x)$ if $x$ is nonzero modulo 10, and $f(x)=s(s(x))$ if $x$ is a multiple of 10.

The palindromes in the sequence $s(x),s^2(x),s^3(x),\dots$ are the same as those in the sequence $f(x),f^2(x),f^3(x),\dots$ [Edit: as per comments this isn't 100% true], and $f$ grows exponentially fast: $$100 x > f(x) > \frac{11}{10} x.$$ The constants here aren't so important: the sequence grows exponentially. Homework: what is $\sup f(x)/x$ ? [Edit: it's still true that $s$ grows exponentially fast on average, and that's enough to justify all below.]

How likely is a random number to be palindromic? Between $a\cdot 10^k$ and $(a+1)\cdot 10^k$ (with $1\leq a \leq 8$), there are $10^{\lfloor k/2 \rfloor}$ palindromes. So a random number of size around $N$ has probability around $1/\sqrt{N}$ of being a palindrome (this is crude, but we're just talking heuristics here). Roughly then, the probability of none of $f(x),f^2(x),f^3(x),\dots$ being palindromes, assuming independence, is something like $$p_x:=P(\text{$x$ is Lychrel}) \approx \prod_{i=1}^\infty \left(1-\frac{1}{\sqrt{(11/10)^i x}}\right).$$ Continuing, $$\log(p_x) \approx \sum_{i=1}^\infty \log(1-1/\sqrt{(11/10)^i x})\approx -\sum_{i=1}^\infty 1/\sqrt{(11/10)^i x} \approx -\frac{20}{\sqrt{x}},$$ where the $\approx$ symbol means I'm not being precise except in the ways that I think matter. This all comes to $p_x \approx c^{1/\sqrt{x}}$ for some $0 < c < 1$.

Assuming that I can still do calculus, this means that $p_x\to 1$ and so $\sum_{x=1}^\infty p_x$ diverges, and so by the Borel-Cantelli Lemmas there are infinitely many Lychrel numbers. For any particular (random) $x$, it has a nonzero-nonone probability of being Lychrel, and most of that probability is tied up in the first few iterations of $f$. As 196 survives the first so-many iterations, it becomes increasingly unlikely (but not impossible) that a palindrome will be chanced upon.

Answer 3

Here are some extensions to Aaron Meyerowitz's comments. (Edit: As Aaron points out in the comments, my primary claim here is actually wrong.)

As Aaron points out, it is clear that if computing the sum $s(x) = x + r(x)$ involves no carries, then $s(x)$ is a palindrome. In this case we call $x$ "special." If computing $s(x)$ does involve carries (i.e., $x$ is not special) but $s(x)$ is nonetheless a palindrome, we call $x$ "exceptional." Aaron asks how common exceptional numbers are.

I claim that exceptional numbers only occur in one very specific situation, and that this gives us a necessary and sufficient condition for $s(x)$ to be a palindrome. Specifically, I claim that a carrying computation of $s(x)$ results in a palindrome if and only if the carry happens in the first and last place of the number, and results in the first two digits and the final two digits all being one. So basically, the rule is that $s(x)$ is a palindrome iff there are no carries in its computation, except in one very specific situation. This applies in all bases.

Given a nonnegative integer $n$ and a base $b \geq 2$, we shall write $\bar{n}$ to denote the number of digits in $n$'s base $b$ representation. We write $n_i$ to denote the $i$th digit from the left, with $n_1$ being the first (least significant) digit, and $n_{\bar{n}}$ being the last (most significant) digit.

We shall write $n_{-i}$ to abbreviate $n_{\bar{n} - i + 1}$. This is the digit "corresponding" to $n_i$ in the reverse of $n$. We have $n_{-i} = r(n)_{i}$.

Given a number $n$, a "carry" is an index $1 \leq i \leq \bar{n}$ such that $n_i + n_{-i} \geq b$. It is a location where a carry happens in computing $s(n)$. If $n$ has no carries, then $s(n)$ is a palindrome.

Define an "inner carry" as a carry $i$ where $1 < i < \bar{n}$. An "outer carry" is a carry $i$ where $i = 1$ or $i = \bar{n}$. An "exceptional outer carry" is an outer carry is an outer carry where, letting $m = s(n)$, we have

$ m_{\bar{m}} = m_{\bar{m}-1} = m_{\bar{n}} = m_2 = m_1 = 1. $

That is, in an exceptional outer carry, the first two digits and the last two digits of $s(n)$ are all $1$.

Proposition. $s(n)$ is a palindrome iff every carry for $n$ is an exceptional outer carry.

(Left to right.) Let $m = s(n)$, and suppose $m$ is a palindrome. Suppose there is an outer carry. Then $m_{\bar{m}} = 1$. Then $m_1 = 1$. Then

$m_{\bar{m}-1} = m_{\bar{n}} = n_1 + n_{\bar{n}} - b = m_1 = 1.$

Then $m_2 = m_{\bar{m}-1} = 1$. So if there is an outer carry, it is exceptional. Now suppose there is an inner carry, and let $i$ be the smallest inner carry. (Observe that $i \leq \lceil \frac{\bar{n}}{2} \rceil$, since if $i$ is a carry, then $-i$ is also a carry.)

To begin, suppose there is no outer carry. Then $i$ is the smallest carry. Then

$m_{i-1} = n_{i-1} + n_{-(i+1)}.$

$-i$ is also a carry, so there is a carry into $-i+1$. But $-i$ is the largest carry, so there is no carry from $-i+1$. So

$m_{-i+1} = m_{-(i-1)} = n_{-(i-1)} + n_{--(i-1)} + 1 = n_{i-1} + n_{-(i-1)} + 1 \neq m_{i-1},$

so $m$ is not a palindrome. So in the case where there is no outer carry, there is no inner carry. Now suppose there is an outer carry. The outer carry is exceptional, and then

$m_{\bar{m}} = m_{\bar{m}-1} = m_{\bar{n}} = m_2 = m_1 = 1.$

If $i \geq 3$, then we can argue as in the case where there is no outer carry, since we have that there is no carry into the $i$th place. $i \neq 1$, since $i$ is inner. Suppose $i = 2$. Then there is a carry from $m_{\bar{n}-1}$ into $m_{\bar{n}}$. $n_1 + n_{\bar{n}} = b+1$, (i.e., 11 in base $b$), since there is an outer carry and $m_1 = 1$. So

$m_{\bar{n}} = n_1 + n_{\bar{n}} - b + 1 = b + 1 - b + 1 = 1 + 1 = 2,$

contradicting $m_{\bar{n}} = 1$. So there is no inner carry, and we are done with the left to right case.

(Right to left.) Suppose every carry for $n$ is an exceptional outer carry. If there are no carries, then $m = s(n)$ is a palindrome. Suppose there is an exceptional outer carry. Then $m_i = m_{-i}$ for all $i \in \{1,2,\bar{m},\bar{m}-1\}$ by definition, and $m_{i} = m_{-i}$ for all $2 < i < \bar{m}-1$ by the absence of inner carries.

Comments and criticisms are welcome; I suspect the proof could use refining, and it might actually be wrong!