Proving a simpler test cannot exist for testing $x - \operatorname{reverse}(x) \equiv 0 \pmod{k}$

Question

I'm looking at the following programming puzzle:

Beautiful Days at the Movies

Here's a summary of the problem:

An integer $d$ is "beautiful" w/respect to $k$ if

$$d - \operatorname{reverse}(d) \equiv 0\pmod{k}$$

where $\operatorname{reverse}(d)$ is the integer produced if the base-$10$ representation of $d$ were reversed; here's some examples: $$\begin{align*} \operatorname{reverse}(123) & & & = 321 \\ \operatorname{reverse}(200) & & & = 2 \\ \operatorname{reverse}(2) & & & = 2 \end{align*}$$

Given integer inputs:

• $1 \le x \le y \le 2 \cdot 10^6$
• $1 \le k \le 2 \cdot 10^9$

... write a function that counts the number of beautiful numbers $d$ in $x \le d \le y$.

The solutions I've seen are equivalent to the following:

• Define: $$\operatorname{reverse}(x) \ := \ \sum_{k=0}^n 10^{k}\left(\left\lfloor{\frac{x}{10^{n-k-1}}}\right\rfloor \bmod 10\right)$$
• Test: $$x - \operatorname{reverse}(x)\equiv 0 \pmod{k}$$

Initially I figured this was one of those "it's easy if you know the trick" problems, however after toying with it I don't believe there is any such shortcut.

How can I prove this problem doesn't have a trivial solution?

Answer 1

TLDR: Yes there is a faster way, no there isn't a "simple trick"; this is probably the simplest test:

1. Decompose into base-10 digits
2. Compute & test:
   $\hspace{10mm}\Bigg[\sum_{i}^{n/2}(d_{n-i}-d_{i})(10^{n-i}-10^{i})\Bigg]\bmod{k}$

The rest of this response is some details I learned while looking into this.

---

In Knuth's "The Art of Computer Programming, Vol 2", exercise 4.4.14 encourages the reader to prove it's possible to convert between binary/decimal in $O(M(n)\cdot\log{n})$ time.

Given a function $C(x)$ for converting from base $\beta_1$ to $\beta_2$:

$\hspace{10mm}C(d) = C(d_{left})\cdot C(\beta_{1}^{n/2}) + C(d_{right})$

... where $d_{left}$ & $d_{right}$ are partitions of the digits of $d$.

By recursively splitting / computing / combining a result may be obtained in $O(M(n)\cdot\log{n})$ time. This can be further optimized, but I'll skip that part since the optimizations just reduce the size of the constant factor.

More efficient options exist, but they're generally for [much] larger numbers.

---

The implementation of $reverse(x)$ given in the question has time complexity at least $O(M(n)\cdot{n})$.

"Hackers Delight" section 7.1 gives an $O(\log{n})$ divide-and-conquer algorithm for reversing the bits of a binary number by shuffling the bits as follows:

$\hspace{10mm}abcdefgh$
$\hspace{10mm}badcfehg$
$\hspace{10mm}dcbahgfe$
$\hspace{10mm}hgfedcba$

A similar method could be used for swapping the base-10 digits after they've been computed; this combined with the approach from TAoCP (above) then converting back to binary would still be $O(M(n)\cdot\log{n})$