Suppose we were to list all 4-digit numbers we can make
with the digits 1 to 7 in increasing order.
1111 will be #1 in the list.
There are 74 = 2401 numbers in the list.
So 7777 will be #2401 in the list
In order for a natural number to be a multiple of 3, the
sum of its digits must be a multiple of 3. That is,
Its sum of digits modulo 3 must be 0
We will investigate the sums of digits to find the ones
in the list with sum of digits (modulo 3) = 0.
We will use the notation d1 = 1st digit,..., d4 = 4th digit.
To get the (n+1)st number in the list from the nth number
in the list. we have four cases:
Case 1: (Example: 4756)
d4 < 7, add 1 to d4.
(In the example, we get 4757)
That adds 1 to the sum of digits.
Case 2: (Example: 7347)
d4 = 7, d3 < 7, increase d3 by 1, decrease d4 by 6.
(In the example, we get 7351)
So we have added -5 to the sum of digits.
-5 is 1 more than a multiple of 3, (i.e., -5 = 1 (mod 3)
Case 3: (Example: 2577)
d4 = 7, d3 = 7, d2 < 7. increase d2 by 1, decrease d3 by 6,
and decrease d4 by 6.
(In the example, we get 2611)
So we have added -11 to the sum of digits.
-11 is 1 more than a multiple of 3, [i.e., -11 = 1 (mod 3)]
Case 4: (Example: 1777)
d4 = 7, d3 = 7, d2 = 7, d1 < 7. increase d2 by 1, decrease d3 by 6,
and decrease d3 by 6.
(In the example, we get 2111)
So we have added -17 to the sum of digits.
-17 is 1 more than a multiple of 3, (i.e., -17 = 1 (mod 3)
Therefore, when we get each successive number, we add
(1 mod 3) to the sum of digits.
Therefore every third number in the list has the equivalent
sum of digits modulo 3.
As we showed above, there are 74 or 2401 numbers in the list.
The smallest number in the list which is a multiple of 3 is
1113. The largest number in the list which is a multiple of 3
is 7776.
1113 is list #3 in the list and 7776 is list #2400.
So list numbers #3, #6, #9, ..., #2400 are multiples of 3.
Dividing those list numbers by 3, gives the sequence:
1, 2, 3, ... , 800.
So there are 800 4-digit natural numbers that we can form
which are divisible by 3, if we use only the digits 1 to 7.
Edwin
