Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
It seems that the question in your title is already answered in the linked Wikipedia article: the status is that the conjecture is open. But your questions in the last paragraph — looking for information about recent progress and techniques — are more interesting (and also more open-ended). –  Theo Johnson-Freyd Dec 23 '12 at 22:10
3  
I wonder what has been investigated about starting points with many digits. All 2 digit starts (evidently) lead to a palindrome and most 3 digit starts are known to. A 20 digit start like $10^{20}+23$ goes almost immediately to a palindrome but what about $\lfloor 2^{20}\pi \rfloor$ or any fairly random 20 digit string. Perhaps most of those don't obviously terminate in a palindrome so a small start which is lucky enough to get that high keeps going. Anyway, one could experiment but perhaps it is known. –  Aaron Meyerowitz Dec 24 '12 at 10:36
6  
I should be interested in probabilistic insight. It seems that the probability that $a_1\cdots a_n+a_n\cdots a_1$ be palindromic decays with $n$. Therefore the probability that a sequence beginning with some number $N$ reaches some palindrome is finite and possibly less than $1$ is $N$ is large enough. What is known about that? –  Denis Serre Dec 24 '12 at 10:37
    
@Mike D, you might want to add this as an answer to mathoverflow.net/questions/100265/… –  Joel Reyes Noche Dec 24 '12 at 13:11
    
Please add open-problem tag –  Alexander Chervov Dec 28 '12 at 18:33
add comment

3 Answers

up vote 17 down vote accepted

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.

share|improve this answer
1  
Both answers say that "most" big numbers do not get to a palindrome. Practically speaking if you test a bunch of numbers and give up when you get to 300 or 500 iterations it would be rare to unprecedented to be proved wrong even once. By that measure I'd guess that over 80% of 20 digit numbers are 'Lychrel" –  Aaron Meyerowitz Dec 27 '12 at 3:19
add comment

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.

share|improve this answer
    
I agree with the conclusion but I added to my answer above and suggest that things are far for independent. –  Aaron Meyerowitz Dec 27 '12 at 10:28
3  
Typically, this sort of heuristic argument cannot be "fixed" because the underlying process is not random, but it can be improved. Aaron's answer explains some of the dependence, and one could try to bring that into this probabilistic model. One could then try and push the model to give the probability of, say, a 20 digit number having one of its first 50 iterates a palindrome. Such a probability can be compared to experiment as a way of assessing the heuristic. But to be clear: there is no chance that this will lead to a proof. –  Kevin O'Bryant Dec 28 '12 at 18:08
add comment

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!

share|improve this answer
1  
Nice! They are rare but (after cranking up a computer program) it is not exactly as you say. 302008+800203=1102211 and 30208+80203=110411 so having carries only at the start and end is not sufficient. Also 9832+2389=12221 so having carries in the middle is not fatal either. –  Aaron Meyerowitz Feb 12 '13 at 20:31
    
Aaron: Shoot! I will try to see where I have gone wrong. –  Nick Thomas Feb 12 '13 at 22:58
1  
I think I got it. Each matched pair of digits has to add to a multiple of $11$ so 0+0 , 2+9, 3+8, 4+7 or 5+6. Of course we can't start with 0+0. –  Aaron Meyerowitz Feb 13 '13 at 4:52
    
Aaron: Sorry I missed your comment! That's an exciting idea! Could you possibly state your conjecture more explicitly? Are you trying to give a necessary and sufficient condition for $s(x)$ to be a palindrome? –  Nick Thomas Feb 22 '13 at 5:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.