Determine all $n$-digit numbers that are divisible by the cyclic permutations of its digits

226 Views Asked by At

Given an integer $n \geq 2$, determine all $n$-digit numbers $M_0 = \overline{a_1a_2 \ldots a_n}$ $(a_i \neq 0, i = 1,2,\ldots,n)$ divisible by the numbers $M_1 = \overline{a_2a_3 \ldots a_na_1}$, $M_2 = \overline{a_3a_4\ldots a_na_1a_2},\ldots,M_{n-1} = \overline{a_na_1a_2 \ldots a_{n-1}}$.

We first note that $a_i \leq 4$ for $i > 1$ unless $a_1 = \cdots = a_n$ where $a_1 > 4$. Thus assuming that is not the case, $M_0 \leq \underbrace{84\ldots4}_{n-1 \text{ 4s}}$.

What do I do from here?

2

There are 2 best solutions below

2
On BEST ANSWER

Suppose $M_i = k_iM_0$ for $i = 1, 2, \cdots, n - 1$, and we let $k_0 = 1$. Since $a_i \neq 0$, so $k_i \neq 0$.

Case 1: if $k_i = k_j$ for some $i < j$. Claim: this will be reduced to the same question with $n' = j - i$.

Proof: Since $k_i = k_j$, so $M_i = M_j$. Denote $x = \overline{a_{i + 1} \cdots a_j}$, and $y = \overline{a_{j + 1} \cdots a_{j + n'}}$

$$ \overline{xa_{j + 1}a_{j + 2}\cdots} = M_i = M_j = \overline{ya_{j + n' + 1}a_{j + n' + 2}\cdots} \Rightarrow x = y $$

Using the same argument shows that $M_i = \overline{xx \cdots xx}$, i.e. a repeating of the segment $x$. Then now $x$ (possibly a reordering of $x$) is a solution to the same problem for a smaller $n'$.

Case 2: if $k_i \neq k_j, \forall i$. Clearly $k_i < 10$ because of the number of digits. So $k_i \in \{1, \cdots, 9\}$. So $n \leq 9$. Claim: there is no solution.

Proof: We first claim that $a_1 = \max\{a_i\}$. If not, suppose $a_t > a_1$, then

$$ M_{t - 1} \leq k_{t - 1}M_{t - 1} = M_0 < (a_1 + 1)10^{n - 1} \leq a_t10^{n - 1} \leq M_{t - 1}, $$

a contradiction. Therefore $a_1 = \max\{a_i\}$. Then

$$ (\sum_{i = 0}^{n - 1}10^i)na_1 \geq (\sum_{i = 0}^{n - 1}10^i)(\sum_{i = 1}^na_i) = \sum_{i = 0}^{n - 1}M_i = (\sum_{i = 0}^{n - 1}k_i)M_0 \geq (\sum_{i = 0}^{n - 1}k_i)10^{n - 1}a_1 \geq (n + 1)10^{n - 1}a_1. $$

Cancel $a_1$ on both sides of the inequality, we have

$$ (\sum_{i = 0}^{n - 1}10^i)n \geq (n + 1)10^{n - 1} \Rightarrow n \geq (\sum_{i = 1}^{n - 1}10^{-i})^{-1} > 9, $$

a contradiction.

In conclusion, with only Case 1 possible, using induction on $n$, we will end up with the only solution $M_0 = \overline{aa\cdots aa}$.

7
On

All repdigits work, of course. But those are the only solutions.

Let's consider just those numbers where $M_1$ divides $M_0$. We can then write $$ M_0 = 10^{n-1}a + b \qquad\qquad M_1 = 10b+a $$ where $a$ is a single digit and all the other digits are in $b$. This means that for some $k\in\{2,3,\ldots,8\}$ we must have $$ 10^{n-1}a + b = k(10b+a) $$ which can be solve for $b$ to give $$ \tag{*} b = \frac{a(10^{n-1}-k)}{10k-1} $$ Furthermore $n$ can be at least $8$; otherwise $M_0$ would be made of repeats of a single digit sequence that in itself would satisfy the condition.

So all in all there are only $9\times 7\times 7=441$ combinations of $a$, $k$, $n$ to try -- a quick computer search shows that $b$ is an integer only for these 10 solutions:

102564/4 = 25641
205128/4 = 51282
307692/4 = 76923
410256/4 = 102564
512820/4 = 128205
615384/4 = 153846
717948/4 = 179487
714285/5 = 142857
820512/4 = 205128
923076/4 = 230769

and it is easy to see that for each of these one of the other $M_i$s will fail to divide $M_0$.