How to reverse digits of an integer mathematically? [duplicate]

Solution 1:

Let $n = \lfloor \log_{10}x\rfloor$, then $x$ has $n + 1$ digits; see this answer.

Let $x = \displaystyle\sum_{i=0}^nx_i10^i$ where $x_i \in \{0, 1, \dots, 9\}$. To obtain $x_k$ (i.e. the $(k+1)^{\text{st}}$ digit of $x$), first divide by $10^k$ to obtain

$$x10^{-k} = \sum_{i=0}^nx_i10^{i-k} = \sum_{i=0}^{k-1}x_i10^{i-k} + \sum_{i=k}^nx_i10^{i-k}.$$

Note that the first sum on the right hand side is a non-negative number less than $1$ and the second sum is an integer. Therefore

$$\lfloor x10^{-k}\rfloor = \left\lfloor\sum_{i=0}^nx_i10^{i-k}\right\rfloor = \sum_{i=k}^nx_i10^{i-k}.$$

Now consider the corresponding expression for $k+1$:

\begin{align*} \lfloor x10^{-(k+1)}\rfloor &= \left\lfloor\sum_{i=0}^nx_i10^{i-(k+1)}\right\rfloor\\ &= \sum_{i=k+1}^nx_i10^{i-(k+1)}\\ &= 10^{-1} \sum_{i=k+1}^nx_i10^{i-k}\\ &= 10^{-1}\left(\sum_{i=k}^nx_i10^{i-k}-x_k\right)\\ &= 10^{-1}\left(\lfloor x10^{-k}\rfloor - x_k\right). \end{align*}

Rearranging for $x_k$ we find $x_k = \lfloor x10^{-k}\rfloor - 10\lfloor x10^{-(k+1)}\rfloor$. Therefore, the number you are after is

\begin{align*} \sum_{k=0}^nx_{n-k}10^k &= \sum_{k=0}^n\left(\lfloor x10^{-(n-k)}\rfloor - 10\lfloor x10^{-(n-k+1)}\rfloor\right)10^k\\ &= \sum_{k=0}^n\lfloor x10^{-(n-k)}\rfloor10^k - \sum_{k=0}^n\lfloor x10^{-(n-k+1)}\rfloor10^{k+1} \end{align*}

or if you prefer

\begin{align*} \sum_{k=0}^nx_k10^{n-k} &= \left(\lfloor x10^{-k}\rfloor - 10\lfloor x10^{-(k+1)}\rfloor\right)10^{n-k}\\ &= \sum_{k=0}^n\lfloor x10^{-k}\rfloor10^{n-k} - \sum_{k=0}^n\lfloor x10^{-(k+1)}\rfloor10^{n-k+1}. \end{align*}

We can simplify this even further. Note that $\lfloor x10^{-n+1}\rfloor = 0$ so the final term in the second sum is zero. Now shift the index in the second sum so that it begins at $k = 1$:

\begin{align*} &\sum_{k=0}^n\lfloor x10^{-k}\rfloor10^{n-k} - \sum_{k=0}^n\lfloor x10^{-(k+1)}\rfloor10^{n-k+1}\\ &= \sum_{k=0}^n\lfloor x10^{-k}\rfloor10^{n-k} - \sum_{k=1}^n\lfloor x10^{-k}\rfloor10^{n-k+2}\\ &= \lfloor x10^0\rfloor10^n + \sum_{k=1}^n\lfloor x10^{-k}\rfloor10^{n-k} - 100\sum_{k=1}^n\lfloor x10^{-k}\rfloor10^{n-k}\\ &= x10^n - 99\sum_{k=1}^n\lfloor x10^{-k}\rfloor10^{n-k}. \end{align*}

Therefore, given a positive integer $x$, the integer which has the same digits in the reverse order is $$x10^{\lfloor \log_{10}x\rfloor} - 99\sum_{k=1}^{\lfloor \log_{10}x\rfloor}\lfloor x10^{-k}\rfloor10^{\lfloor \log_{10}x\rfloor-k}.$$

Here's an example calculation. Let $x = 123$, then $\lfloor \log_{10}x\rfloor = 2$. As $\lfloor x10^{-1}\rfloor = \lfloor 12.3\rfloor = 12$ and $\lfloor x10^{-2}\rfloor = \lfloor 1.23\rfloor = 1$, we have

$$123\times 10^2 - 99\left(12\times 10 + 1\times 1\right) = 123\times 100 - 99\times 121 = 12300 - 11979 = 321$$

as expected.

Solution 2:

Here's a recursive formula:

$$R(N)=U(N)10^{[log(N)]}+R([N/10])$$

where

$$U(N)=N-10[N/10]$$

is the "unit" digit of $N$ (i.e., the digit in the "ones" column), and $R(0)$ is understood to equal $0$. The logarithm is base $10$, and the square brackets indicate the greatest-integer (floor) function.

Note: reversing digits is not an involution when $U(N)=0$. E.g., $R(100)=1$, but R($1)\neq100$.

Added later: It occurs to me that the recursive formula adapts nicely to digit reversal in any base:

$$R_b(N) = U_b(N)b^{[log_b(N)]}+R_b([N/b])$$

where

$$U_b(N)=N-b[N/b]$$