Question

given the number 123456789, is it possible to find a permutation (i.e. a rearrangement that preserves the count of each number) such that the left most digit is evenly divisible by 1, the two left most digits are evenly divisible by 2, the three left most digits are divisibly by 3 and so on?

Answer 1

Question.

Given the number 123456789. Is it possible to find a permutation (i.e. rearrangement that preserves the count of each number) such that the left most digit is evenly divisible by 1, the two left most digits are evenly divisible by 2, the three left most digits are divisibly by 3 and so on?

Solution.

We have number $\langle d_1 d_2 d_3 d_4 d_5 d_6 d_7 d_8 d_9 \rangle$ , where digits form the permutations of 123456789. We need to find, what position will have every digit to qualify the answer.

1) As $\langle d_1 d_2 \rangle$ should be divisible by 2, $\langle d_1 d_2 d_3 d_4 \rangle$ should be divisible by 4 (and it should be also divisible by 2) and so on, all even digits $(d_2, d_4, d_6, d_8)$ will be even $(2, 4, 6, 8)$ .

2) As $\langle d_1 d_2 d_3 d_4 d_5 \rangle$ should be divisible by 5, the last digit should be 0 or 5. As 0 is not used, so, $d_5 = 5$ .

3) $\langle d_1 d_2 d_3 d_4 \rangle$ should be divisible by 4. The divisibility rule for 4 states that if the last 2 digits are divisible by 4, then the whole number is divisible by 4. So $\langle d_3 d_4 \rangle$ is divisible by 4, $d_3$ is odd and $d_4$ is even, and $d_3$ is not equal to 5 (by item (2)). We can enumerate all numbers which match this pattern: 12, 16, 32, 36, 72, 76, 92, 96. $\langle d_3 d_4 \rangle$ is one of them.

We can notice, that $d_4$ by this pattern will be equal to 2 or to 6.

4) Using pattern from item (3) we can analyze digits $\langle d_7 d_8 \rangle$ . As $\langle d_1 d_2 d_3 d_4 d_5 d_6 d_7 d_8 \rangle$ should be divisible by 8, this number will also be divisible by 4. So the last two digits $\langle d_7 d_8 \rangle$ will match the same rule as $\langle d_3 d_4 \rangle$ , so $d_8$ will be also equal to 2 or to 6.

5) As it was proved in (3) and (4), $d_4$ and $d_8$ will be equal to 2 or to 6. In this case, $d_2$ and $d_6$ will be equal to 4 or to 8.

As we have found, $d_5$ is equal to 5, $d_4$ and $d_8$ are equal to 2 or to 6, $d_2$ and $d_6$ are equal to 4 or to 8. This information will be used for further conclusions.

6) $\langle d_1 d_2 d_3 d_4 d_5 d_6 d_7 d_8 \rangle$ should be divisible by 8. The divisibility rule for 8 states, that last 3 digits should be divisible by 8, so $\langle d_6 d_7 d_8 \rangle$ should be divisible by 8. As we know, $d_6$ is equal to 4 or to 8, $d_8$ is equal to 2 or to 6 and $d_7$ is not equal to 5. We can match only a few numbers for this pattern: 416, 432, 472, 496, 816, 832, 872, 896. So $\langle d_6 d_7 d_8 \rangle$ is one of them.

7) $\langle d_1 d_2 d_3 \rangle$ should be divisible by 3. The divisibility rule for 3 states, that the sum of all digits of number should be divisible by 3. Also we know, that $d_1$ and $d_3$ are odd and not equal to 5, $d_2$ is even and is equal to 4 or to 8. Only few numbers matches this pattern: 147, 183, 189, 381, 387, 741, 783, 981. So $\langle d_1 d_2 d_3 \rangle$ is one of them.

8) $\langle d_1 d_2 d_3 d_4 d_5 d_6 \rangle$ should be divisible by 6, so it should be divisible by 3, so the rule (7) can be applicable in this case. As sum of $d_1$ , $d_2$ and $d_3$ is divisible by 3 (from (7)), so sum of $d_4$ , $d_5$ and $d_6$ should be divisible by 3. As we know, $d_5$ is equal to 5, $d_6$ is equal to 4 or 8 and $d_4$ is equal to 2 or to 6. There are only two numbers, which match this pattern: 258 and 654.

Now we can concatenate all patterns from (1) - (8).

1. If $\langle d_4 d_5 d_6 \rangle = 258$ (from (8)), then $\langle d_6 d_7 d_8 \rangle$ can be equal to 816 or to 896 (from (6)). So we can have $\langle d_1 d_2 d_3 25816 d_9 \rangle$ or $\langle d_1 d_2 d_3 25896 d_9 \rangle$ .

In the first case we can not match $\langle d_1 d_2 d_3 \rangle$ to any of variants from (7), as 1 and 8 are already used. But for the second case we can match $\langle d_1 d_2 d_3 \rangle$ with 2 variants from (7): 147 and 741. And after matching the last digit we have got two variants of number:

```

d₁ d₂ d₃ d₄ d₅ d₆ d₇ d₈ d₉

1 4 7 2 5 8 9 6 3

7 4 1 2 5 8 9 6 3

```

2. If $\langle d_4 d_5 d_6 \rangle = 654$ (from (8)), then $\langle d_6 d_7 d_8 \rangle$ can be equal to 472 or 432 (from (6)). So we can have $\langle d_1 d_2 d_3 65472 d_9 \rangle$ or $\langle d_1 d_2 d_3 65432 d_9 \rangle$ .

In the first case we can match $\langle d_1 d_2 d_3 \rangle$ with next variants from (7): 183, 189, 381, 981. In the second case we can match $\langle d_1 d_2 d_3 \rangle$ with the next variants from (7): 189 and 981. And after matching the last digit we have got another 6 options:

```

d₁ d₂ d₃ d₄ d₅ d₆ d₇ d₈ d₉

1 8 3 6 5 4 7 2 9

1 8 9 6 5 4 7 2 3

3 8 1 6 5 4 7 2 9

9 8 1 6 5 4 7 2 3

1 8 9 6 5 4 3 2 7

9 8 1 6 5 4 3 2 7

```

By default all matching numbers are divisible by 9, as according to the divisibility rule for 9, the sum of all digits is divisible by 9.

The last thing to check is divisibility by 7 of number $\langle d_1 d_2 d_3 d_4 d_5 d_6 d_7 \rangle$ . It is simply checked for the all 8 numbers found in solution. And we can found, that there is the only number, which matches the question and it is 381654729.

Answer.

Such number exists. It is 381654729.

Note.

Such number can be found by the brute-force of all permutations of 123456789 with checks for divisibility on each step. But the total number of all permutations is equal to $9! = 9*8*7*6*5*4*3*2*1 = 362880$ which (including all divisibility checks) will take a noticeable large amount of time.

Divisibility rules see in:

[https://en.wikipedia.org/wiki/Divisibility_rule](https://en.wikipedia.org/wiki/Divisibility_rule)