CJ7

How many 4-digit positive integers not containing the digit 7 are divisible by 7?

This is part of the set Things Get Harder!


The answer is 834.

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.

2 solutions

Kenneth Tan
Jul 5, 2018

Let's call numbers that are multiples of 7 and don't contain the digit 7 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 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.

Lemma 1: For any non-negative arithmetic sequences with common difference of 7, the units digit of every 10 consecutive terms must have every number from 0 0 to 9 9 .

Hence, if we consider all non-negative multiples of 7 smaller than 70: 0 , 7 , 14 , 21 , 28 , 35 , 42 , 49 , 56 , 63 0,\, \color{#EC7300}7\color{#333333},\, 14,\, 21,\, 28,\, 35,\, 42,\, 49,\, 56,\, 63 by lemma 1 , and because no numbers have a 7 7 in the tens place, we know that exactly 9 9 out of these 10 10 are unseveners .

This can be generalized to any 10 consecutive multiples of 7, as long as none of them have a 7 7 in any other place other than the units.

Lemma 2: For any 10 consecutive multiples of 7, where none of them have a 7 7 in any place except the units, exactly 9 9 of them are unseveners .

Now consider all non-negative multiples of 7 smaller than 700, we write them in a 10 × 10 10\times10 array like this: 0 70 140 210 280 350 420 490 560 630 7 77 147 217 287 357 427 497 567 637 14 84 154 224 294 364 434 504 574 644 21 91 161 231 301 371 441 511 581 651 28 98 168 238 308 378 448 518 588 658 35 105 175 245 315 385 455 525 595 665 42 112 182 252 322 392 462 532 602 672 49 119 189 259 329 399 469 539 609 679 56 126 196 266 336 406 476 546 616 686 63 133 203 273 343 413 483 553 623 693 \begin{matrix} 0 & \color{#EC7300}70 & 140 & 210 & 280 & 350 & 420 & 490 & 560 & 630\\ \color{#EC7300}7 & \color{#EC7300}77 & \color{#EC7300}147 & \color{#EC7300}217 & \color{#EC7300}287 & \color{#EC7300}357 & \color{#EC7300}427 & \color{#EC7300}497 & \color{#EC7300}567 & \color{#EC7300}637\\ 14 & 84 & 154 & 224 & 294 & 364 & 434 & 504 & \color{#EC7300}574 & 644\\ 21 & 91 & 161 & 231 & 301 & \color{#EC7300}371 & 441 & 511 & 581 & 651\\ 28 & 98 & 168 & 238 & 308 & \color{#EC7300}378 & 448 & 518 & 588 & 658\\ 35 & 105 & \color{#EC7300}175 & 245 & 315 & 385 & 455 & 525 & 595 & 665\\ 42 & 112 & 182 & 252 & 322 & 392 & 462 & 532 & 602 & \color{#EC7300}672\\ 49 & 119 & 189 & 259 & 329 & 399 & 469 & 539 & 609 & \color{#EC7300}679\\ 56 & 126 & 196 & 266 & 336 & 406 & \color{#EC7300}476 & 546 & 616 & 686\\ 63 & 133 & 203 & \color{#EC7300}273 & 343 & 413 & 483 & 553 & 623 & 693\\ \end{matrix}

1 out of 10 multiples of 7 have 7 7 in the units place, hence we must have 10 out of 100 multiples of 7 that have 7 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 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 = 81 9\times9=81 of them are unseveners .

This can be generalized to any 100 consecutive multiples of 7, as long as none of them have a 7 7 in any other place other than the units and tens.

Lemma 3: For any 100 consecutive multiples of 7, where none of them have a 7 7 in any place except the units and the tens, exactly 81 81 of them are unseveners .

Now consider all non-negative multiples of 7 smaller than 7000, imagine writing them in a 3D 10 × 10 × 10 10\times10\times10 array like so (each subsequent 'plane' of numbers is 700 more than their respective numbers in the previous plane):

100 81 = 19 100-81=19 out of 100 multiples of 7 have at least one 7 7 in their units and tens place, hence we have 190 out of 1000 multiples of 7 that have at least one 7 7 in their units and tens place, this is represented by the 19 "z-rows" .

As for the remaining 81 81 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 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, 81 × 9 = 729 81\times9=729 of them are unseveners .

We now know that from 1 to 6999, 729 729 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, 81 81 of them are unseveners . From 700 to 799, there are no unseveners . By lemma 2 , there are 9 9 unseveners from 800 to 869, and 9 9 in 880 to 949. Plus the remaining unseveners 952 952 , 959 959 , 966 966 , 980 980 , 994 994 , making a total of 104 104 unseveners .

7000 to 7999:

There are no unseveners in this range.

8000 to 8999:

By lemma 3 , there are 81 81 seveners from 8000 to 8699. From 8700 to 8799, there are no unseveners . By lemma 2 , there are 9 9 unseveners from 8800 to 8869, and 9 9 from 8880 to 8949. Plus the remaining unseveners 8953 8953 , 8960 8960 , 8981 8981 , 8988 8988 , 8995 8995 , making a total of 104 104 unseveners .

9000 to 9999:

By lemma 3 , there are 81 81 seveners from 9000 to 9699. From 9700 to 9799, there are no unseveners . By lemma 2 , there are 9 9 unseveners from 9800 to 9869, and 9 9 in 9880 to 9949. Plus the remaining unseveners 9954 9954 , 9961 9961 , 9968 9968 , 9982 9982 , 9989 9989 , 9996 9996 , making a total of 105 105 seveners .

Therefore, the total number of unseveners from 1000 to 9999 is 729 104 + 104 + 105 = 834 729-104+104+105=834 .

Haha😂A short question yields a hell long solution. Anyway, saying that, your solution is flawless. You might wanna attach a relevant wiki:Principle of inclusion and exclusion(Pie).

donglin loo - 2 years, 11 months ago

Log in to reply

To be honest I used to think of a problem similar to this but harder XD. I wonder if you have a shorter and more elegant one than mine?

Kenneth Tan - 2 years, 11 months ago

Log in to reply

I believe there is no shorter solution and principle of inclusion and exclusion practically helps do all the job here. Just for the record, the way I do this is to find number of all 4-digit multiples of 7-at least one digit is 7+at least two digit is 7-at least 3 digit is 7+all 4 digits are 7

donglin loo - 2 years, 11 months ago

Length [ Table [ If [ ¬ MemberQ [ IntegerDigits [ i ] , 7 ] , i , Nothing ] , { i , 1001 , 9999 , 7 } ] ] 834 \text{Length}[\text{Table}[\text{If}[\neg \text{MemberQ}[\text{IntegerDigits}[i],7],i,\text{Nothing}],\{i,1001,9999,7\}]] \Longrightarrow 834

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...