4 added 86 characters in body

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!

3 deleted 14 characters in body

Here are some extensions to Aaron Meyerowitz's comments.

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$ mod $\bar{n}$ 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!

Post Undeleted by Nick Thomas
2 Fixed error in proof.; added 72 characters in body
Post Deleted by Nick Thomas
1