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

Question

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.

Answer 1

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!

Answer 2

Answer

No, there is no 64 bit integer that satisfies the requirement: $$ x \neq \text{actual_reverse}(x) \quad \text{and} \quad x = \text{reverse_digits}(x).$$

Proof

Suppose that there is such a $x$. I will assume that $x$ itself lies below the overflow limit, i.e. $x < 2^{64}$. Also, we can assume that $\text{actual_reverse}(x) > x$, otherwise no overflow will occur.
As you mentioned, $x$ will have 20 decimal digits.

First note that $\text{reverse_digits}(x) = \text{actual_reverse}(x) \bmod 2^{64}$.
For instance, in your own example: $\text{actual_reverse}(1000000009) = 9000000001 = 410065409 \bmod 2^{32}$ (this relation is true for all number of bits).

But, there is even a stronger relation, $\text{actual_reverse}(x)$ is not that much bigger than $2^{64}$, therefore, the $k \in \mathbb{Z}$ in the equation: \begin{equation} \label{eq1} \tag{1} x = \text{reverse_digits}(x) = \text{actual_reverse}(x) - k \cdot 2^{64} \end{equation} is bounded by: $1 \leq k \leq \left \lfloor{{10^{20} / 2^{64}}}\right \rfloor = 5$.
This means that we only have to check if there exists a solution $x$ in \eqref{eq1} for each of the $5$ possible values of $k$.

So, how can we do that?
Write $x = (x_1 x_2 \dots x_{20})$ in base $10$, where $x_{20}$ is the least significant bit.
Similarly, fix a value of $k$ and write $k \cdot 2^{64} = (y_1 y_2 \dots y_{20})$ in base $10$.
Then we can rewrite \eqref{eq1} as:

\begin{equation} \label{eq2} \tag{2} (x_1 + y_1) \cdot 10^{19} + (x_2 + y_2) \cdot 10^{18} + \dots + (x_{20} + y_{20}) = x_{20} \cdot 10^{19} + x_{19} \cdot 10^{18} + \dots + x_1. \end{equation}

Now, we can't directly say that $x_1 + y_1 = x_{20}$, not even modulo $10$. This is because there can be a carry-over from the sum $x_2 + y_2$.
However, this carry-over is limited to $0$ or $1$ (since we are taking sums of integers, in products you can have much bigger carry-overs).

Hence, we get the following relation: $$ x_1 + y_1 + j_1 = x_{20} \bmod 10 $$ where $j_1 \in \{0,1\}$. Similarly, we find $x_{20} + y_{20} + j_{20} = x_1 \bmod 10$, where again $j_{20} \in \{0,1\}$. I guess $j_{20} = 1$ can be discarded, but anyways, combining these two equations gives: $$ x_{20} + y_{20} + j_{20} + y_1 + j_1 = x_{20} \bmod 10. $$ Hence, $y_{20} + y_1 = k_1 \bmod 10$, where $k_1 \in \{ 0,9,8 \}$.
Note that this final relation only depends on the decimals of $k \cdot 2^{64}$!

We can now repeat this proces for the other digits in \eqref{eq2}. We find that for each $i = 0, 2, \dots, 19$:

$$ (y_i + y_{20-i} \bmod 10) \in \{ 0,9,8 \}. $$

It is very unlikely that there exists a $k$ such that the bits of $k \cdot 2^{64}$ satisfy all of these equations. Since, heuristically, the probability that one of them holds is $0.3$, hence the probability that all of them hold for at least one of the possible values of $k$ is $1 - (1 - 0.3^{20})^5 \approx 0$.
This is of course not a proof, that's why I checked the $5$ values of $k$ to see that they all don't work, see the Python code below.
The value for $k = 5$ came the furthest, since the first two equations held: $$ 5 \cdot 2^{64} = 92233720368547758080 $$ and $9+0, 2+8 \bmod 10 \in \{ 0,9,8 \}$, but $2+0 \bmod 10 \not \in \{ 0,9,8 \}$.

As a side-note, we now see that if the number of bits is large, then the (heuristic) probability that a solution $x$ exists is very low. If the number of bits is smaller, then the probability is a bit better, but I bruteforced everything for 20 digits or fewer and I did not find a solution. Therefore, there probably isn't a single number of digits such that a solution $x$ exists.

Python code

from math import *
n = 64
N = ceil(n*log10(2))
print(N)

K = floor(10**N / 2**n)
print(K)
print("")

for k in range(1,K+1):
    reducion_term = k*2**64
    string = str(reducion_term)
    test = True
    for i in range(N):
        y_i = int(string[i])
        y_20_i = int(string[19-i])
        condition = ((y_i + y_20_i) % 10) in [0,9,8]
        print(k,i,condition)
        if condition == False:
            test = False
            break
    if test == True:
        print("Maybe possible for k =", k)

This code did not find any value $k$ such that \eqref{eq1} could have a solution.
Therefore, no solution to \eqref{eq1} exists.