How many 4-digit positive integers not containing the digit 7 are divisible by 7?
This is part of the set Things Get Harder!
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let's call numbers that are multiples of 7 and don't contain the digit 7 unseveners .
First notice that for any non-negative arithmetic sequences with common difference of 7, their units digit cycles through 7 , 4 , 1 , 8 , 5 , 2 , 9 , 6 , 3 , 0 .
We see that the numbers 0 to 9 all appear once in the units digit of any 10 consecutive terms.
Hence, if we consider all non-negative multiples of 7 smaller than 70: 0 , 7 , 1 4 , 2 1 , 2 8 , 3 5 , 4 2 , 4 9 , 5 6 , 6 3 by lemma 1 , and because no numbers have a 7 in the tens place, we know that exactly 9 out of these 1 0 are unseveners .
This can be generalized to any 10 consecutive multiples of 7, as long as none of them have a 7 in any other place other than the units.
Now consider all non-negative multiples of 7 smaller than 700, we write them in a 1 0 × 1 0 array like this: 0 7 1 4 2 1 2 8 3 5 4 2 4 9 5 6 6 3 7 0 7 7 8 4 9 1 9 8 1 0 5 1 1 2 1 1 9 1 2 6 1 3 3 1 4 0 1 4 7 1 5 4 1 6 1 1 6 8 1 7 5 1 8 2 1 8 9 1 9 6 2 0 3 2 1 0 2 1 7 2 2 4 2 3 1 2 3 8 2 4 5 2 5 2 2 5 9 2 6 6 2 7 3 2 8 0 2 8 7 2 9 4 3 0 1 3 0 8 3 1 5 3 2 2 3 2 9 3 3 6 3 4 3 3 5 0 3 5 7 3 6 4 3 7 1 3 7 8 3 8 5 3 9 2 3 9 9 4 0 6 4 1 3 4 2 0 4 2 7 4 3 4 4 4 1 4 4 8 4 5 5 4 6 2 4 6 9 4 7 6 4 8 3 4 9 0 4 9 7 5 0 4 5 1 1 5 1 8 5 2 5 5 3 2 5 3 9 5 4 6 5 5 3 5 6 0 5 6 7 5 7 4 5 8 1 5 8 8 5 9 5 6 0 2 6 0 9 6 1 6 6 2 3 6 3 0 6 3 7 6 4 4 6 5 1 6 5 8 6 6 5 6 7 2 6 7 9 6 8 6 6 9 3
1 out of 10 multiples of 7 have 7 in the units place, hence we must have 10 out of 100 multiples of 7 that have 7 in the units place, this is represented by the second row.
As for the remaining 9 rows, if we ignore their units digit, the remaining digits form a non-negative arithmetic sequence with a common difference of 7 consisting of 10 terms, by lemma 1 , and because there are no numbers with a 7 in its hundreds place, we know that there must be exactly 9 unseveners in each row.
Thus, for multiples of 7 smaller than 700, exactly 9 × 9 = 8 1 of them are unseveners .
This can be generalized to any 100 consecutive multiples of 7, as long as none of them have a 7 in any other place other than the units and tens.
Now consider all non-negative multiples of 7 smaller than 7000, imagine writing them in a 3D 1 0 × 1 0 × 1 0 array like so (each subsequent 'plane' of numbers is 700 more than their respective numbers in the previous plane):
1 0 0 − 8 1 = 1 9 out of 100 multiples of 7 have at least one 7 in their units and tens place, hence we have 190 out of 1000 multiples of 7 that have at least one 7 in their units and tens place, this is represented by the 19 "z-rows" .
As for the remaining 8 1 z-rows , if we ignore both their units and tens digit, the remaining digits form an arithmetic sequence of common difference 7 with 10 terms, by lemma 1 , and because there are no numbers with a 7 in its thousands place, we know that there must be exactly 9 unseveners in each z-row .
Thus, for multiples of 7 smaller than 7000, 8 1 × 9 = 7 2 9 of them are unseveners .
We now know that from 1 to 6999, 7 2 9 of them are unseveners . But our target range is 1000 to 9999, we'll do the remaining inclusion and exclusion manually.
1 to 999:
We already know that from 1 to 699, 8 1 of them are unseveners . From 700 to 799, there are no unseveners . By lemma 2 , there are 9 unseveners from 800 to 869, and 9 in 880 to 949. Plus the remaining unseveners 9 5 2 , 9 5 9 , 9 6 6 , 9 8 0 , 9 9 4 , making a total of 1 0 4 unseveners .
7000 to 7999:
There are no unseveners in this range.
8000 to 8999:
By lemma 3 , there are 8 1 seveners from 8000 to 8699. From 8700 to 8799, there are no unseveners . By lemma 2 , there are 9 unseveners from 8800 to 8869, and 9 from 8880 to 8949. Plus the remaining unseveners 8 9 5 3 , 8 9 6 0 , 8 9 8 1 , 8 9 8 8 , 8 9 9 5 , making a total of 1 0 4 unseveners .
9000 to 9999:
By lemma 3 , there are 8 1 seveners from 9000 to 9699. From 9700 to 9799, there are no unseveners . By lemma 2 , there are 9 unseveners from 9800 to 9869, and 9 in 9880 to 9949. Plus the remaining unseveners 9 9 5 4 , 9 9 6 1 , 9 9 6 8 , 9 9 8 2 , 9 9 8 9 , 9 9 9 6 , making a total of 1 0 5 seveners .
Therefore, the total number of unseveners from 1000 to 9999 is 7 2 9 − 1 0 4 + 1 0 4 + 1 0 5 = 8 3 4 .