Number Discrimination 3

You must attempt Number Discrimination 2 first before attempting this. In that problem, the answer is $1600$ . So, there are $1600$ positive integers smaller than $10000$ which satisfy the properties above.

The question above is asking for $a_{1153}$ when the numbers are arranged in ascending order. Considering the difference between $1153$ and $1600$ is smaller compared to the difference between $4$ and $1153$ , we go for reversing method. Yup, just like how you reverse your vehicle.

---

We know that numbers smaller than $10000$ have a maximum of four digits. So, we look at the case when the first digit is $9$ and there are four digits. Among them, we hope to eliminate multiples of $3$ .

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

$9$ is divisible by $3$ . So, it follows that the remaining $3$ digits must sum up to a multiple of $3$ .

We know that the digits that can be used are $0,4,5,6,7,8,9$ only, having $7$ possible choices.

$0\equiv 0(mod3), 4\equiv1(mod3), 5\equiv2(mod3), 6\equiv0(mod3), 7\equiv1(mod3), 8\equiv2(mod3), 9\equiv0(mod3)$

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

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

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

For $0+0+0$ , the number of integers are $3\cdot3\cdot3=27$

For $0+1+2$ , the number of integers are $3\cdot2\cdot2\cdot3!=72$

For $1+1+1$ , the number of integers are $2\cdot2\cdot2=8$

For $2+2+2$ , the number of integers are $2\cdot2\cdot2=8$

So, the number of remaining which meet our requirements $=7^3-27-72-8-8=228$

---

Now, we look at the case when the first digit is $8$ and there are four digits. Among them, we hope to eliminate multiples of $3$ .

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

8 leaves a remainder of $2$ when divided by $3$ . So, it follows that the remaining $3$ digits must sum up to a number which leaves a remainder of $1$ when divided by $3$ .

We know that the digits that can be used are $0,4,5,6,7,8,9$ only, having $7$ possible choices.

$0\equiv 0(mod3), 4\equiv1(mod3), 5\equiv2(mod3), 6\equiv0(mod3), 7\equiv1(mod3), 8\equiv2(mod3), 9\equiv0(mod3)$

Now, we are finding numbers which leave a remainder of $1$ when divided by $3$ using the sum of $0,1,2$ three times.

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

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

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

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

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

So, the number of remaining which meet our requirements $=7^3-54-36-24=229$

---

$\therefore$ the number of integers meeting our requirements ranging from $8000$ to $9000$ $=229+228=457$

We then perform the following operation: $1600-457=1143$ .

This shows that the number of integers meeting our requirements but smaller than $8000=1143$ . It is somewhat close to $1153$ .

Now, we push forward our list.

The numbers not smaller than 8000 that meet our requirements are $8000,8005,8006,8008,8009,8044,8045,8047,8048,\boxed{8050},...$

$\boxed{8050}$ is indeed the value of $a_{1153}$ we are looking for!

We have the following lemma and its corollary, a sketch of the proof is given below, you can see the full details in my solution to Number Discrimination 2 :

(numbers that are multiples of 3 but don't contain the digits $1$ , $2$ or $3$ are given the name anti-threes )

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 exists 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. $_\square$

---

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 .

This is true because by lemma 1 , all digit sequences from $\underbrace{00\ldots0}_{k\text{ 0s}}$ to $\underbrace{99\ldots9}_{k\text{ 9s}}$ appear once, 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. The digits $1$ , $2$ and $3$ also don't appear anywhere else apart in the last $k$ digits.

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 .

---

Consider numbers from 1 to 7999, we partition the numbers like so (notation wise, 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}}$

$\underbrace{[7000,7009]}_{\text{2 anti-threes: }\{7005, 7008\}}\quad\underbrace{[7010,7039]}_{\text{0 anti-threes}}\color{#D61F06}\quad\underbrace{[7040,7069]}_{\text{7 anti-threes}}\color{#D61F06}\quad\underbrace{[7070,7099]}_{\text{7 anti-threes}}\color{#333333}\quad\underbrace{[7100,7399]}_{\text{0 anti-threes}}\color{#EC7300}\quad\underbrace{[7400,7699]}_{\text{49 anti-threes}}\color{#EC7300}\quad\underbrace{[7700,7999]}_{\text{49 anti-threes}}$

(Apply (1) to red intervals, (2) to orange intervals, and (3) to green intervals)

We see that there are $571$ anti-threes from 1 to 7999. From 1 to 7999, the number of integers that don't contain $1$ , $2$ or $3$ is $5\times7^3-1=1714$ (Why? Consider a 4-digit sequence $\square\square\square\square$ , 0001 represents 1, 0002 represents 2 and so on, we choose digits for the 4 places. Since we can't use $1$ , $2$ , or $3$ , we are left with 7 digits to choose for the last 3 places. For the first place, we can only use the digits $0$ , $4$ , $5$ , $6$ and $7$ . We also subtracted $1$ at the end to exclude 0000). Out of these $1714$ numbers that don't contain $1$ , $2$ , $3$ , $571$ of them are multiples of 3 ( anti-threes ), and $1714-571=1143$ of them are not multiples of 3 (which is what we're looking for).

We now know that $a_1$ to $a_{1143}$ are all in 1 to 7999, hence we can trace the next term in the sequence $a_{1144}=8000$ . Continuing the sequence, $a_{1145}=8005 \\ a_{1146}=8006 \\ a_{1147}=8008 \\ a_{1148}=8009 \\ a_{1149}=8044 \\ a_{1150}=8045 \\ a_{1151}=8047 \\ a_{1152}=8048 \\ a_{1153}=8050$

We have found our answer, $a_{1153}=8050$ .

By the way, you might wonder how did I know to consider 1 to 7999. If you've solved Number Discrimination 2 , you'll know that $a_1$ to $a_{1600}$ are all in 1 to 9999, and $a_{1153}$ is somewhat closer to $a_{1600}=9998$ , we can guess that $a_{1153}$ is somewhere between 7000 and 9998.

If you however didn't solve that other problem, well, there's always trial and error. :P