Divisible permutation

Number Theory Level 4

Given the number 123456789 . Find a permutation of the number's digits 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? Type $\boxed{-1}$ if permutation does not exist.

E.g.: if we have number $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}d_{7}d_{8}d_{9}$ than $d_{1}$ is divisible by 1, $d_{1}d_{2}$ is divisible by 2, $d_{1}d_{2}d_{3}$ is divisble by 3, ... , $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}d_{7}d_{8}d_{9}$ is divisible by 9.

The answer is 381654729.

3 solutions

Павел Горбонос
Jan 12, 2019

We need to find permutation $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}d_{7}d_{8}d_{9}$ of 123456789.

1) All even digits ( $d_{2}, d_{4}, d_{6}, d_{8}$ ) will be even (2, 4, 6, 8).

2) As $d_{1}d_{2}d_{3}d_{4}d_{5}$ is divisible by 5, the fifth digit is 5.

3) $d_{1}d_{2}d_{3}d_{4}$ is divisible by 4, so the last 2 digits are divisible by 4. So $d_{3}d_{4}$ 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 witch match this pattern: 12, 16, 32, 36, 72, 76, 92, 96. $d_{3}d_{4}$ is one of them. So, $d_{4}$ will be equal to 2 or to 6.

4) As $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}d_{7}d_{8}$ is divisible by 8, it is also divisible by 4. So $d_{7}d_{8}$ is divisible by 4, so $d_{8}$ is equal to 2 or to 6.

5) As $d_{4}$ and $d_{8}$ are equal to 2 or to 6, so $d_{2}$ and $d_{6}$ are to 4 or to 8.

6) As $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}d_{7}d_{8}$ is divisible by 8, so last 3 digits are divisible by 8, so $d_{6}d_{7}d_{8}$ is 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.

7) $d_{1}d_{2}d_{3}$ is divisible by 3, so the sum of all digits of the number is 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 $d_{1}d_{2}d_{3}$ is one of them.

8) $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}$ is divisible by 6, so it is divisible by 3, so the sum of digits is divisible by 3. As the sum of $d_{1}$ , $d_{2}$ and $d_{3}$ is divisible by 3, so the sum of $d_{4}$ , $d_{5}$ and $d_{6}$ is 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 $d_{4}d_{5}d_{6}$ = 258 (from (8)), then $d_{6}d_{7}d_{8}$ can be equal to 816 or to 896 (from (6)). So we can have $d_{1}d_{2}d_{3}25816d_{9}$ or $d_{1}d_{2}d_{3}25896d_{9}$ . In the first case we can not match $d_{1}d_{2}d_{3}$ to any of variants from (7), as 1 and 8 are already used. But for the second case we can match $d_{1}d_{2}d_{3}$ with 2 variants from (7): 147 and 741. And after matching the last digit we have got two variants of the number:

1 4 7 2 5 8 9 6 3

7 4 1 2 5 8 9 6 3

2) If $d_{4}d_{5}d_{6}$ = 654 (from (8)), then $d_{6}d_{7}d_{8}$ can be equal to 472 or 432 (from (6)). So we can have $d_{1}d_{2}d_{3}65472d_{9}$ or $d_{1}d_{2}d_{3}65432d_{9}$ . In the first case we can match $d_{1}d_{2}d_{3}$ with next variants from (7): 183, 189, 381, 981. In the second case we can match $d_{1}d_{2}d_{3}$ with the next variants from (7): 189 and 981. And after matching the last digit we have got another 6 options:

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

No we can check divisibility by 7 of number $d_{1}d_{2}d_{3}d_{4}d_{5}d_{6}d_{7}$ . 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 3 8 1 6 5 4 7 2 9.

Alex Li
Jan 19, 2019

max = 9
perm = [i+1 for i in range(max)]
def brute_force(n):
    if n == 0:
        # check if a given permutation satisfies the condition
        num = 0
        for i in range(max):
            num = num*10 + perm[i]
            if num % (i+1) != 0:
                return
        print(num)
    else:
        # logic to generate permutations: move each element to the end
        # of the list, and recursively generate all permutations of the rest
        for i in range(n):
            perm[i], perm[n - 1] = perm[n - 1], perm[i]
            brute_force(n - 1)
            perm[i], perm[n - 1] = perm[n - 1], perm[i]
if __name__ == "__main__":
    brute_force(max)

A Former Brilliant Member
Feb 24, 2019

The case for division by 1 and 9 are not necessary as they always succeed.

$\text{Table}[\text{If}[(\text{FromDigits}[\text{Take}[p,2]] \bmod 2)=0, \\ \text{If}[(\text{FromDigits}[\text{Take}[p,3]] \bmod 3)=0, \\ \text{If}[(\text{FromDigits}[\text{Take}[p,4]] \bmod 4)=0, \\ \text{If}[(\text{FromDigits}[\text{Take}[p,5]] \bmod 5)=0, \\ \text{If}[(\text{FromDigits}[\text{Take}[p,6]] \bmod 6)=0, \\ \text{If}[(\text{FromDigits}[\text{Take}[p,7]] \bmod 7)=0, \\ \text{If}[(\text{FromDigits}[\text{Take}[p,8]] \bmod 8)=0,p, \\ \text{Nothing}],\text{Nothing}],\text{Nothing}],\text{Nothing}],\text{Nothing}],\text{Nothing}],\text{Nothing}], \\ \{p,\text{Permutations}[\text{Range}[9]]\}] \Longrightarrow \left( \begin{array}{ccccccccc} 3 & 8 & 1 & 6 & 5 & 4 & 7 & 2 & 9 \\ \end{array} \right)$

Divisible permutation

The answer is 381654729.

3 solutions

0 pending reports