Challenge 24: 7-digit numbers

  • #1
18,087
7,510

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,691
6,466
Well that was fun and kept me up another 20 minutes when I should be sleeping ... :oops:
 
  • #3
210
10
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
 
  • #4
473
13
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.
 
  • #5
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,691
6,466
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).
 

Related Threads on Challenge 24: 7-digit numbers

Replies
6
Views
3K
  • Last Post
Replies
4
Views
9K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
5
Views
2K
  • Last Post
2
Replies
32
Views
6K
Replies
2
Views
4K
  • Last Post
Replies
15
Views
2K
Replies
12
Views
2K
Replies
4
Views
24K
Top