A polydivisible number is a number for which the first n digits form a number evenly divisible by n for all n between 1 and the number of digits of that number.
In other words, the first 2 digits form a number divisible by 2, first 3 digits form a number divisible by 3, first 4 digits form a number divisible by 4, etc. for all of the digits of the number.
Can you arrange the digits 1-9 to form a 9-digit polydivisible number? Each digit 1-9 must be used exactly once.
Solution
381654729 is the unique solution. This requires the use of divisibility rules.
First of all, we know all possible arrangements are divisible by 3 and 9, because the sum of the digits (45) is divisible by 3 and 9 regardless of the arrangement.
Since the first 5 digits are divisible by 5, the 5th digit must be 0 or 5 – and because 0 is not one of the possibilities, that means the 5th digit must be 5.
Since numbers that end in an odd digit cannot be divisible by an even number, all the even digits must be even. This also means all the odd digits must be odd.
Since we know the 6th digit is even and the 7th digit is odd, the 7th and 8th digits must be 16, 32, 72, or 96 in order for the first 8 digits to be divisible by 8.
Since we know the 3rd digit is odd, the 4th digit must be 2 or 6 in order for the first 4 digits to be divisible by 4. Because each digit can only be used once, here are the possibilities at this point:
- _ _ _ 2 5 _ 1 6 _
- _ _ _ 2 5 _ 9 6 _
- _ _ _ 6 5 _ 3 2 _
- _ _ _ 6 5 _ 7 2 _
Since the first 6 digits are divisible by 6, they must be divisible by 3. Since we know the first 3 digits must be divisible by 3, that means the 4-6th digits must also be divisible by 3 in order for all 6 digits to be divisible by 3 together. Within the possibilities above, that could only be 258 or 654. This also only leaves one even number remaining for the 2nd digit, so we have narrowed it down to these possibilities:
- _ 4 _ 2 5 8 1 6 _
- _ 4 _ 2 5 8 9 6 _
- _ 8 _ 6 5 4 3 2 _
- _ 8 _ 6 5 4 7 2 _
We are left with the first 7 digits being divisible by 7, and 3 remaining odd digits to arrange. Since there are 6 ways to arrange the odd digits for each of the 4 possibilities above, there are only 24 possible arrangements left. Unfortunately, the divisibility rule for 7 doesn’t help us much here, so we just have to test these 24 arrangements. It turns out only one of these combinations has the first 7 digits divisible by 7: 381654729.
954637281