What multiples of $d$ are still multiples of $d$ when they have their digits reversed?

Question

I teach at a school for 11 to 18 year olds. Every term I put up a Challenge on the wall outside my classroom.

This question is one that I have devised for that audience. I think that it is quite interesting and I would like to share it with a wider audience. I am not aware of it being a copy of another question.

An underlying assumption to this question is that we are writing numbers in base 10. A further question could be to investigate the same question in other bases.

Define the reverse of a number as the number created by writing the digits of the original number in the opposite order. Leading zeroes are ignored, although you will see that this makes very little difference to my question if this stipulation is removed.

Thus $Reverse(1456)=6541$ and $Reverse(2100)=12$

My question is this: For a given value $d$, what numbers $x$ have the property that $x$ is a multiple of $d$ and $Reverse(x)$ is a multiple of $d$? I call such numbers "reversible multiples of $d$."

Clearly there are "brute force" ways to investigate this question, but I am looking for more subtle answers.

A good answer should address the following:

a) For some values of $d$ all multiples are reversible multiples. List those values, with a proof of why this is so.

b) For other values there are certain properties that the multiple must have for it to be a reversible multiple. Explain these.

c) For at least one value there is an algorithm that can be used to construct reversible multiples. Describe such an algorithm.

Enjoy!

Answer 1

Interesting question! I see no obvious route toward a general solution yet.

For $d = 2^k$, the solution is not very interesting: Numbers that qualify are those whose last $k$ digits are divisible by $d$, and whose first $k$ digits, when reversed, are also divisible by $d$.

For $d = 3$ or $9$, any number divisible by $d$ remains divisible by $d$ when reversed.

For $d = 5$, the solution is again not very interesting: The number must begin with 5, and end in either 0 or 5.

For $d = 6$, any number divisible by $6$ that begins with an even digit remains divisible by $6$ when reversed.

There are some interesting divisibility tests for $d = 7$, but I'm still working on how to turn them into conditions for divisibility surviving digit reversal. I'll come back to edit this if/when I come up with something.

There are, of course, no numbers divisible by $10$ that remain so when reversed. (Note that this is affected by whether leading zeros are dropped.)

Any number divisible by $11$ remains so when reversed.

Analogously with the $d = 6$ case, any number divisible by $12$, that begins with two digits that yield a number divisible by $4$ when reversed, remains divisible by $12$ when reversed.

Answer 2

I think this question is fascinating, thanks for posting it. In addition to $3$ and $9$, I might add that multiples of $11$ are also always reversible. Therefore, multiplies of $33$ and $99$ are also always reversible. One might hope that squaring an always reversible number leads to an always reversible number, but that's not true: $81$ and $121$ multiples are not always reversible. Similarly, $33^2 = 1089 \ $ is not always reversible. However, 1089 is one of my favorite numbers because it is reversible for the first ten multiples, which is pretty unusual for a 4 digit number!

Now, $1001$ is reversible for much more than just the first ten multiples. It is reversible for so many multiplies that one might be tempted to conjecture it is always reversible. However, a quick Mathematica search reveals $1001 \cdot 1009 \ $ is not reversible, even though it any multiple less than $1009$ is reversible!

Is $1, 3, 9, 11, 33, 99 \ $ the complete list of numbers whose multiples are always reversible? I do not know ... (Edit: actually, this question is answered here: https://oeis.org/A018282/a018282.pdf )

Answer 3

The division test for $3$ and $9$ (i.e if a number's digits sum to a multiple of $3$, than the number is a multiple of $3$, and similarly for $9$), shows that the reversal of any multiple of these numbers is also a multiple of these numbers.

Obvious restrictions on the first digit gives conditions for multiples of $2$ and $5$. This also gives a condition for $6$, since any multiple of $2$ and $3$ is a multiple of $6$. For $4$, we just require that the first two digits (when reversed) are divisible by $4$. A divisibility test for $8$ is to see if the last three digits of a number are divisible by $8$. This can be used to give a condition for $8$. For $7$, a restriction could be placed, but it seems a bit more complicated.

I'm not sure what the algorithm question is getting at (for instance, just take any multiples of $3$. Does this satisfy your question?).

Answer 4

As Tyler Seacrest noted, the only numbers whose every multiple is reversible are the divisors of $99$. Further, no number divisible by $10$ admits reversible multiples (unless we allow padding with zeros).

Now suppose that $d$ is not divisible by $2$ or $5$ and let $a = \phi(d)$, where $\phi$ is Euler's totient function. Then by Fermat's little theorem we know that $10^a \equiv 1 \pmod{d}$. Hence for any positive integer $k$ the number $$ n_k = n_k(d) := \sum_{i = 0}^{d-1} 10^{ika} $$ is divisible by $d$. Moreover, $n_k$ is palindrome, because $$ \text{Reverse}(n_k) = \sum_{i = 0}^{d-1} 10^{(d-1-i)ka} = \sum_{j = 0}^{d-1} 10^{jka} $$ therefore it is reversible.

Further, define $n_k(1) = 10^k + 1$ and suppose that $p \in \{2,5\}$ and $p^h \parallel d$ for some $h \geq 1$. If we can find an $m$ reversible wrt $p^h$, then $m n_k(\frac{d}{p^h})$ is reversible with respect to $d$ for every $k$ greater or equal than the number of digits of $m$.

Finally, as Brian Tung observed every power of $2$ admits a reversible number. Similarly, we can prove that a number $m$ is divisible by $5^h$ if and only if the number formed by its last $h$ digits is, namely by observing that $5^h \mid 10^{h+i}$ for every $i \geq 0$ and taking the residue class modulo $5^h$ of $m$. Hence the number given by the concatenation of $\text{Reverse}(5^h)$ and $5^h$ is reversible wrt $5^h$.

Putting it all together, we conclude that every positive integer $d$ not divisible by $10$ admits infinitely many reversible numbers, while every multiple of $10$ doesn't admit any reversible number.

Answer 5

I take this question in its more open ended form of how to look at such problems. I have seen, in my 18 years, that it is good to take these problems as directly as possible in powers of ten.

Suppose we have a positive integer x in its decimal expansion, defined as

$$ x = n_0 10^0 + n_1 10^1 + ... n_{j-1} 10^{j-1} + n_j 10^j $$

Define Rev(x) as a permutation of the $ n_i $ values, specifically, a reversal of them, as

$$ x = n_j 10^0 + n_{j-1} 10^1 + ... n_1 10^{j-1} + n_0 10^j $$

It might be helpful here to define the Rev(x) as two different functions for an odd number of digits and an even number, since the middle number remains the same. But I actually have little to say about computing algorithms and more about the mathematical parts.

We start, as the OP described, with a value d. We then construct the multiples of d to find x values that have it as a divisor, and find their expansions. Since we want to test $ divisibility $, we can simply reduce mod d to make things easier.

$ n_j 10^0 + n_{j-1} 10^1 + ... n_1 10^{j-1} + n_0 10^j ≡ 0 $ (mod d)

Finding the order of 10 mod d and its series of iterates, we simply replace the powers of ten with those iterates and then look for solutions in the Rev(x) permutation. We can reverse the powers of ten or the actual n values, works the same either way.

Note this method allows us to group digits once we have gone around the order of 10, so it doesn't get much slower as we get way up into the integers for smaller d. A 210 digit x value could be checked without any division by seeing if the congruence holds, and adding the digits that are d spaces from each other before multiplying, since they would group together after simplifying the orders of ten.

I know it's not exactly what you asked for, but I will work on it next chance I get some time. This gives the basic framework for a, b and c as you gave them, listing what properties are necessary.