Number Discrimination 2

Let's call numbers that are multiples of 3 but don't contain the digits $1$ , $2$ or $3$ anti-threes .

We shall first count the number of anti-threes in the range 1 to 9999.

First notice that for any 10 consecutive non-negative multiples of 3, the units digit cycles through $3,\,6,\,9,\,2,\,5,\,8,\,1,\,4,\,7,\,0$ , each number from 0 to 9 all appear once.

And also notice that for any 100 consecutive non-negative multiples of 3, each digit sequence 00 to 99 all appear once in the last two digits.

In fact, this idea can be generalized, we have this lemma:

Lemma 1: For any $10^k$ $(k\in\mathbb{N})$ consecutive non-negative multiples of 3, all $10^k$ digit sequences $\underbrace{00\ldots0}_{k\text{ 0s}}$ to $\underbrace{99\ldots9}_{k\text{ 9s}}$ appear once in the last $k$ digits of these $10^k$ numbers.

Proof:

Assume the contrary and say that some digit sequences from $\underbrace{00\ldots0}_{k\text{ 0s}}$ to $\underbrace{99\ldots9}_{k\text{ 9s}}$ don't appear. We now have $10^k$ numbers and less than $10^k$ digit sequences, by piegeonhole principle , there must be two numbers $A$ and $B$ that have the same last $k$ digits, or $A\equiv B\pmod{10^k}$ . Since $3|A, B$ and $\gcd(3, 10^k)=1$ , we have $A\equiv B\pmod{3\times10^k}$ , and since $A\neq B$ , we must have $|A-B|\geqslant3\times10^k$ . However, out of these $10^k$ consecutive non-negative multiples of 3, the difference of any two must be smaller than $3\times10^k$ , this is a contradiction. Hence all $10^k$ digit sequences digit sequences from $\underbrace{00\ldots0}_{k\text{ 0s}}$ to $\underbrace{99\ldots9}_{k\text{ 9s}}$ must appear once in the last $k$ digits of these $10^k$ numbers. $_\square$

The number of digit sequences from $\underbrace{00\ldots0}_{k\text{ 0s}}$ to $\underbrace{99\ldots9}_{k\text{ 9s}}$ that don't contain $1$ , $2$ or $3$ is $7^k$ (this is because if you create such sequence using $k$ digits, you can only choose one of the 7 digits $0$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ for each of the $k$ places, the number of ways to do this is $\underbrace{7\times7\times\ldots\times7}_{k\text{ times}}=7^k$ )

Therefore, for $10^k$ consecutive non-negative multiples of 3, $7^k$ of them don't contain the digits $1$ , $2$ or $3$ in their last $k$ places, and as long as the $1$ s, $2$ s and $3$ s don't appear in any other place other than the last $k$ places, we know that out of these $10^k$ numbers, exactly $7^k$ of them are anti-threes .

Corollary 1: For any $10^k$ consecutive non-negative multiples of 3, where all of them do not contain $1$ , $2$ and $3$ in any place except in the last $k$ digits, then exactly $7^k$ of them are anti-threes .

---

As a direct implication of corollary 1 :

(1) If we have $10$ consecutive non-negative multiples of 3, where none of them have $1$ , $2$ or $3$ in all other places except in the units, then $7$ of these $10$ numbers are anti-threes .

(2) If we have $100$ consecutive non-negative multiples of 3, where none of them have $1$ , $2$ or $3$ in all other places except in the units and the tens, then $7^2=49$ of these $100$ numbers are anti-threes .

(3) If we have $1000$ consecutive non-negative multiples of 3, where none of them have $1$ , $2$ or $3$ in all other places except in the units, the tens and the hundreds, then $7^3=343$ of these $1000$ numbers are anti-threes .

---

Okay, we now partition the numbers from 1 to 9999 into intervals and count the number of anti-threes in each of them (notation wise, we assume the intervals only contain integers): $\underbrace{[1,9]}_{\text{2 anti-threes: }\{6, 9\}}\quad\underbrace{[10,39]}_{\text{0 anti-threes}}\color{#D61F06}\quad\underbrace{[40,69]}_{\text{7 anti-threes}}\color{#D61F06}\quad\underbrace{[70,99]}_{\text{7 anti-threes}}\color{#333333}\quad\underbrace{[100,399]}_{\text{0 anti-threes}}\color{#EC7300}\quad\underbrace{[400,699]}_{\text{49 anti-threes}}\color{#EC7300}\quad\underbrace{[700,999]}_{\text{49 anti-threes}}\color{#333333}\quad\underbrace{[1000,3999]}_{\text{0 anti-threes}}\color{#20A900}\quad\underbrace{[4000,6999]}_{\text{343 anti-threes}}\color{#20A900}\quad\underbrace{[7000,9999]}_{\text{343 anti-threes}}$

( $\color{#D61F06}\text{Red}$ intervals contain 10 consecutive multiples of 3 which don't contain $1$ , $2$ or $3$ in its tens place, hence (1) applies. $\color{#EC7300}\text{Orange}$ intervals on the other hand contain 100 consecutive multiples of 3 which don't contain $1$ , $2$ or $3$ in its hundreds place, hence (2) applies. $\color{#20A900}\text{Green}$ intervals contain 1000 consecutive multiples of 3 which don't contain $1$ , $2$ or $3$ in its thousands place, hence (3) applies)

The total number of anti-threes from 1 to 9999 is $2+7+7+49+49+343+343=800$ .

Finally, the number of integers from 1 to 9999 that don't contain $1$ , $2$ or $3$ is $7^4-1=2400$ (there are only 7 ways to choose digits for each of the 4 places, subtracting $1$ to exclude 0). These $2400$ which don't contain $1$ , $2$ or $3$ are comprised of integers that are multiples of 3 (they are anti-threes , there's $800$ of them), and integers that are not multiples of 3 (which is what we are looking for).

Therefore, the total number of positive integers that are not multiples of 3 and contains neither the digits $1$ , $2$ or $3$ is $2400-800=1600$ .

---

EXTRA SNACK:

This can be generalized! If $A(x)$ is the number of positive anti-threes that are smaller than $10^x$ $(x\in \mathbb{N})$ , then $A(x)=\frac{7^x-1}{3}$

And if $M(x)$ is the number of positive integers smaller than $10^x$ that don't contain $1$ , $2$ or $3$ and are not divisible by 3, then $M(x)=\frac{2(7^x-1)}{3}$

In this problem, we are looking for $M(4)$ : $M(4)=\frac{2(7^4-1)}{3}=1600$ which in fact is our answer.

Proof incoming alert! Stop reading now if you want to try to prove these yourselves!

Proof:

Did you notice just how perfect we partitioned the intervals? It fits just nice within the desired boundary $[1, 9999]$ ! Let's try to do this in a more general level.

First of all, $A(x-1)$ is the number of anti-threes in the interval $[1, 10^{x-1}-1]$ , while $A(x)$ is the number of anti-threes in the interval $[1, 10^x-1]$ .

Let $S(x-1)$ be the number of anti-threes in the interval $[10^{x-1}, 10^x-1]$ , then $A(x)=A(x-1)+S(x-1)$

We shall first try to find $S(x-1)$ .

We can partition the interval $[10^{x-1}, 10^x-1]$ like this: $[10^{x-1}, 4\times10^{x-1}-1]\quad\color{orchid}[4\times10^{x-1}, 7\times10^{x-1}-1]\quad\color{fuchsia}[7\times10^{x-1}, \times10^x-1]$

• There are no anti-threes in the interval $[10^{x-1}, 4\times10^{x-1}-1]$ , this is because the leading digit of all numbers in this interval is either $1$ , $2$ , or $3$

• As for the interval $\color{orchid}[4\times10^{x-1}, 7\times10^{x-1}-1]$ , it consists of $(7\times10^{x-1}-1)-4\times10^{x-1}+1=3\times10^{x-1}$ integers, this implies that there are $\frac{3\times10^{x-1}}{3}=10^{x-1}$ consecutive non-negative multiples of 3 in this interval that are $x$ digits long, and since all numbers in this interval do not have $1$ , $2$ or $3$ as its leading digit, the digits $1$ , $2$ and $3$ do not appear anywhere else except in their last $x-1$ digits. By corollary 1 , we know that there are $7^{x-1}$ anti-threes in this interval.

• Now looking at $\color{fuchsia}[7\times10^{x-1}, \times10^x-1]$ , this is also an interval with size $3\times10^{x-1}$ , and has $10^{x-1}$ consecutive non-negative multiples of 3 that don't contain $1$ , $2$ or $3$ anywhere except in their last $x-1$ digits, so the same thing happens here, there are $7^{x-1}$ anti-threes in this interval.

Thus $S(x-1)=0+7^{x-1}+7^{x-1}=2(7^{x-1})$ and therefore $A(x)=A(x-1)+2(7^{x-1})$

Going down inductively, we have $A(x-1)=A(x-2)+2(7^{x-2}) \\ A(x-2)=A(x-3)+2(7^{x-3}) \\ A(x-3)=A(x-4)+2(7^{x-4}) \\ \vdots \\ A(3)=A(2)+2(7^2) \\ A(2)=A(1)+2(7^1)$

Add together all these equations, cancelling all the like terms, behold! $A(x)=A(1)+2(7^1+7^2+\ldots+7^{x-2}+7^{x-1})$

$A(1)$ is the number of anti-threes in the interval $[1, 9]$ , which we know is $2$ , and applying the sum of G.P. formula, we get

$\begin{aligned}A(x)&=2+2\left[\frac{7(7^{x-1}-1)}{7-1}\right] \\ &=2+\frac{7^x-7}3 \\ \therefore A(x)&=\frac{7^x-1}3\,_\square\end{aligned}$

Now, in the interval $[1, 10^x-1]$ , the number of integers that contains neither the digits $1$ , $2$ , $3$ is $7^x-1$ (there are 7 ways to choose digits for each of the $x$ places, subtracting $1$ to exclude 0)). These $7^x-1$ integers which don't contain $1$ , $2$ or $3$ are comprised of $A(x)$ integers that are multiples of 3 and $M(x)$ integers that are not multiples of 3.

Hence, $A(x)+M(x)=7^x-1$ $\begin{aligned}M(x)&=7^x-1-A(x) \\ &=7^x-1-\frac{7^x-1}3 \\ \therefore M(x)&=\frac{2(7^x-1)}3\,_\square \end{aligned}$

We utilize the second condition-it contains neither the digits $1,2,3$ first.

With the bound that the positive integer should be smaller than $10000$ , it is obvious that the maximum number of digits is $4$ .

The first, second, third and fourth digit can be $0,4,5,6,7,8$ , having $7$ possible choices in each slot.

So, the number of integers which contains neither the digits $1,2,3$ smaller than $10000$ $=7^4-1=2400$ .

The act of taking away $1$ is removing the number $0$ off the list( $0$ is not positive integer!).

---

Now, the difficult part is deducing the multiples of $3$ among them and hence deducting the number of them from $2400$ .

By divisibility rule , the sum of digits of a multiple of $3$ is also a multiple of $3$ .

We note that the digits can only be $0,4,5,6,7,8,9$

Now, we are finding multiples of $3$ using the sum of $0,1,2$ four times.

Only the following $\textbf{combinations}$ are possible:

$0+0+0+0,0+0+1+2,0+1+1+1,0+2+2+2,1+2+1+2$

For $0+0+0+0$ , the number of integers are $3\cdot3\cdot3\cdot3-1=80$ (0 is not a positive integer!)

For $0+0+1+2$ , the number of integers are $3\cdot3\cdot2\cdot2\cdot\cfrac{4!}{2!}=432$

For $0+1+1+1$ , the number of integers are $3\cdot2\cdot2\cdot2\cdot\cfrac{4!}{3!}=96$

For $0+2+2+2$ , the number of integers are $3\cdot2\cdot2\cdot2\cdot\cfrac{4!}{3!}=96$

For $1+2+1+2$ , the number of integers are $2\cdot2\cdot2\cdot2\cdot\cfrac{4!}{2!\cdot 2!}=96$

Note: the number of integers here already include $\textbf{permutations}$ .

So, the number of multiples of $3$ within the list $=80+432+96+96+96=800$

$\therefore$ the number of integers meeting our requirements $=2400-800=1600$