How to check if some number, say $a$, can be expressed as $a = b + \mathrm{reverse}(b)$ ? Where $a$ and $b$ are some natural numbers.
Some examples:
- $22 = 11 + \mathrm{rev}(11) = 11 + 11$;
That is, $22$ can be expressed as sum of "another natural number and its reverse". - $121 = 29 + \mathrm{rev}(29) = 29 + 92$;
$9$ can't be expressed as sum of "a number and its reverse".
Let $b = \sum\limits_{k=0}^n b_k 10^k$
$b + rev(b) = \sum\limits_{k=0}^{n}(b_k + b_{n-k})10^k < 2*10^{k+1}$.
Suppose $a$ is an $n+1$ digit number.
Case 1: The first digit of $a$ is not equal to $1$. Then if $a = b + rev(b)$ then $b$ is also an digit number and $b_0 + b_k < 10$. So the first digit and last digit of $a$ are are $b_0 + b_k$ and equal.
If the first digit and last digit of $a$ are not equal then $a $ is not is not $b+ rev(b)$. If the first digit and last digit or then remove the first digit and last digit, divide by $10$ and repeat the process.
Case 1a: The first and last digit are $1$. To see if $b_0 + b_k = 1$ and $a = b + rev(b)$, revert to case 1. If it fails, continue to case 2.
Case 2: The first digit of $a$ is $1$. If $b_0 + b_k \ge 10+ $ last digit of $a = m$ and $a = b + rev (b)$ then subtract $m$ and $m*10^{n-1}$ from $a$. Divide by $10$. Repeat the process.
Either the process will end at a single digit and $a = b+ rev(b)$ or the process will fail and $a \ne b + rev (b)$ for any $b$.
Example: $59406 + 60495=119901$ so
so subtract $100001$ to get $19900$ and divide by $10$ to get $1990$. Subtract $10$ and $1000$ to get $980$ and divide by $10$ to get $98$ and that was a failure.
So go back to $119901$ and subtract $11$ and $110000$ so get $9890$ and divide by $10$ to get $989$. Subtract $909$ and get $80$ and divid by $10$ to get $8$. That's a success.