Is there a non-negative integer x that is not a palindrome but for which x == reverse_digits(x) due to an overflow

algorithmsbinaryelementary-number-theorypalindrome

I recently started solving some problems on LeetCode where I came across a question that asks to write a function that checks whether a non-negative integer x is a palindrome, i.e. whether x reads the same backwards as forwards (e.g. 121, 1221, 91919).

One approach to check whether a number is a palindrome is to reverse its digits and compare whether the two numbers are the same. For that, assume that we have the following implementation of a reverse_digits function:

int reverse_digits(int x) {
    int acc = 0;
    while (x != 0) {
        acc = acc * 10 + x % 10;
        x = x / 10;  // integer division, rounds down
    }
    return acc;
}

However, if we use a programming language in which the int type has a fixed width, then this function is prone to overflows. If we assume, for example, that an int has 32 bits, then, using the above implementation, we get:

reverse_digits(1_000_000_001) -> 1_000_000_001 # correctly reversed
reverse_digits(1_000_000_009) -> 410_065_409   # incorrect

My question is:

For the given implementation of reverse_digits and a given number of bits in the int type, is there a non-negative integer x that is not a palindrome but for which x == reverse_digits(x) (due to the overflow caused by the finite number of bits)? We assume that x does not have any leading zeros.

I manually checked the 4-bit case and I wrote a small program in C that checks unsigned 32-bit integers by brute-force; in both cases, there is no such x. However, I am not sure how to prove that there is no such integer for the 64-bit case, or how to find one if there is.

Observation 1:

The largest unsigned 64-bit integer is ULONG_MAX := 18_446_744_073_709_551_615 (with underscores added for readability) which starts with a 1 and has 20 digits. For an overflow to happen, x must have at least 20 digits and not end in zero. Otherwise, reverse_digits correctly reverses the number.
For x to have 20 digits, it must start with a 1, as 20 digit numbers that start with a number greater than 1 don't fit into 64 bits.

Observation 2:

Let $(x_{1}x_{2} \dots x_{20})$ be the (decimal) digit representation of $x$, where $x_i$ is the digit at position $i$ of $x$. Since $x$ starts with $1$, we have $x_1 = 1$.

In the last iteration of the while-loop we calculate

$$(x_{20}x_{19} \dots x_{2})*10+x_1.$$
For an overflow to happen,

$$(x_{20}x_{19} \dots x_{2})*10+x_1 \gt \text{ULONG_MAX},$$

i.e. $(x_{20}x_{19} \dots x_{2}) \gt \text{1_844_674_407_370_955_161}$, i.e. the reverse of the last 19 digits of $x$ must be greater than that value.

Observation 3:

Let $y:=(x_{20}x_{19} \dots x_{2})$ be greater than $\text{1_844_674_407_370_955_161}$. It follows that $z:= y*10+1$ causes an overflow, which means that the binary representation of $z$ has more than 64 bits.

  • Let $(a_1a_2 \dots a_{64})$ be the 64-bit binary representation of $(x_{1}x_{2} \dots x_{20})$.
  • Let $(b_1b_2 \dots b_{64})$ be the 64-bit binary representation of $(x_{20}x_{19} \dots x_{2}) = y$.
  • Let $(c_1c_2 \dots c_{64}c_{64+1} \dots c_{64+j})$ be the (64+j)-bit binary representation of $z$.

We know that

$$
(c_1 \dots c_{64+j}) = (b_1 \dots b_{64}) * 1010_2 + 1_2.
$$

We need find bits $a_i$ and $c_i$ such that

$$
(c_{1+j} \dots c_{64+j}) = (a_1a_2 \dots a_{64})
$$

or, alternatively, show that such bits cannot exist.

This is where I'm kind of stuck. My next step would be to figure out what values $j$ can take and then do the multiplication to try to find some relation between the $a_i$, $b_i$, and $c_i$. I'm not whether this is the right approach though.

Best Answer

If you aren't wedded to base-two computers, then there are examples. Some are very silly; e.g., suppose your computer works in base $18$, and can only handle one digit numbers. Then consider the number $13$. It's not a palindrome. Its reversal is $31$, which, in base $18$, is $1(13)$ (one eighteen, plus thirteen ones). That overflows your one-digit computer, so it drops the overflow digit, and reports the reversal of $13$ to be $13$ – voila! a palindrome.

A less silly example is $1904$ in a base-three computer with seven-digit numbers.
$(1904)_{10}=(2121112)_3$.
$(4091)_{10}=(12121112)_3$.
The reversal causes overflow. Dropping the overflow digit leaves us with $(2121112)_3=(1904)_{10}$, so $1904$ gets reported as a palindrome. If seven digits seems a little small, I'm confident that bigger examples can be constructed for base-three computers.

For base two, here's an argument that this phenomenon can't happen. Let $b$ be the number of bits our machine can handle. Let $n$, our candidate palindrome, have $b$ bits when written in base two, so $$ 2^{b-1}\le n<2^b $$ Let $n$ have $d+1$ digits when written in base ten, so $$ 10^d\le n<10^{d+1} $$ Let's write $\tilde n$ for the (base ten) reversal of $n$. Then $$ \tilde n-n<9\times10^d $$ Also, $\tilde n-n$ is a multiple of nine. It consists of the overflow bits resulting from the reversal of $n$, so it's also a multiple of $2^b$. So $$ \tilde n-n\ge9\times2^b $$ These two inequalities give $$ 9\times2^b<9\times10^d $$ so $$ n<2^b<10^d\le n $$ contradiction!

Related Question