# Challenge 24: 7-digit numbers

Submitted by @PeroK

Consider all 7-digit numbers which are a permutation of the digits 1-7. How many of these are divisible by 7?

Can you prove the answer algebraically, rather than simply counting them?

Please make use of the spoiler tag

Orodruin
Staff Emeritus
Homework Helper
Gold Member
2021 Award
Well that was fun and kept me up another 20 minutes when I should be sleeping ... Well I can solve it easily in base 14. A number divisible by 7 ends either in 7 or 0. Since 0 is excluded, that leaves us only with numbers ending in 7. Thus the remaining 6 digits can have any permutation of the 6 integers 1 to 6, and the answer would be 6! = 720.

But that's probably not what you intended :P

The urge to count them was irresistible... but I did think about it first.
The pattern of 10^k mod 7 is {1,3,2,6,4,5,1} with the repeat just starting. As far as I could see there was nothing favouring one outcome of modulo 7 result over another, so my initial expectation was that one-seventh of all possible permutations would be divisible by 7 - and so it turned out, 7!/7 = 6! = 720.

But that was luck. All permutations of 1..8 gave not 8!/7 =5760, but 5768 numbers divisible by 7.

I haven't yet come up with a good non-brute-force derivation of 720.

Orodruin
Staff Emeritus
Homework Helper
Gold Member
2021 Award
The urge to count them was irresistible... but I did think about it first.
The pattern of 10^k mod 7 is {1,3,2,6,4,5,1} with the repeat just starting. As far as I could see there was nothing favouring one outcome of modulo 7 result over another, so my initial expectation was that one-seventh of all possible permutations would be divisible by 7 - and so it turned out, 7!/7 = 6! = 720.

But that was luck. All permutations of 1..8 gave not 8!/7 =5760, but 5768 numbers divisible by 7.

I haven't yet come up with a good non-brute-force derivation of 720.

The naive expectation is true for all numbers except 3, 6, and 9 (the naive expectation being number of permutations of 1-k divisible by k is (k-1)!). For example:
For 2: 12, 21, where one ((2-1)! = 1! = 1) of them is divisible by two.
For 3: 123, 231, 312, 132, 321, 213 - all of them divisible by three.
You now have a + b + 2c + 3d + 4e + 5f + 6g mod 7, where a-g are is a permutation of 1-7. The trick here is to show that for a given permutation which is divisible by 7, there are also 6 which are not - any element of the permutation group with order 7 should do (although some may be more suited than others).