# Number of seven digit numbers without repetition of digits divisible by $3$

Find number of seven digit numbers divisible by $3$ with

$1.$ Repetition

$2.$ Without Repetition

For Part $1.$ The least seven digit number divisible by $3$ is $1000002$ and highest seven digit number is $9999999$

So total is $3000000$

For Part $2$ The least such number is $1023456$ and the next is $1023459$

Now sum of the digits of $1023456$ is $21$.

So if we include $7$ by removing one of the digits in $1023456$ then the digits that can be removed is $1$ or $4$.

If we include $8$ then digits that can be removed is $2$ or $5$.

but we get more cases here, any better way to approach?

• yes i missed that – Ekaveera Gouribhatla Dec 2 '17 at 16:49
• Is it of any help to see first which digits will be omitted? There are only 84 such sets, and I bet about a third is right. Then take permutations of those. Then see how many of them begin with 0? – user491874 Dec 2 '17 at 16:58
• Via a program i have that the answer is $190080$ – John Lou Dec 2 '17 at 17:00

Let $N_7 = \text{what you are looking for}$

However, this consists of one set that doesn't use any zeros - $(NZ)_7$ - and another that does. The number in the set that uses zeros can be defined recursively as $6(NZ)_6$ because the zero can be placed in 6 different places.

Notice that $(NZ)_7 = \frac{\text{pair of two numbers that are divisible by 3}}{9c2} \cdot(9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3)$

This is because the total sum of $1,2, ..8, 9$ is $45$ and we need to remove two numbers such that the sum of the others is still a multiple fo $3$ ie the two numbers we remove must be a multiple of $3$

Therefore, $(NZ)_7 = \frac{(NZ)_2}{9P2}(9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3)$

Similarly, $(NZ)_6 = \frac{(NZ)_3}{9P3}(9\cdot8\cdot7\cdot6\cdot5\cdot4)$

$(NZ)_2$ can be counted, but also it can be expressed as $9\cdot3 - \frac{1}{9}\cdot 9 \cdot 3$. This is found because if the first is $0 \mod 3$, then there is an overcounting (1/3 of such cases are false $1/3 *1/3 = 1/9$)

Similarly, $(NZ)_2=9\cdot 8 \cdot 3 - \frac{2}{8} \cdot \frac{2}{3} \cdot 9 \cdot 8\cdot 3$. Here, the second part is found by considering the probability that the second number chosen is the same modulus as the first ( $2/8$), which results in only $1/3$ of the possible last digits (so we subtract out $2/3$)

Therefore,

$$N_7 = \frac{9 \cdot 3 - 3}{72}(9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3) + 6 \cdot \frac{9\cdot8\cdot3-4\cdot9}{504}(9\cdot8\cdot7\cdot6\cdot5\cdot4) = 190080$$

This is definitely not my most eloquent answer, so please ask me questions if something is confusing, and I'll try to explain my thought process.

$(1)$ Number of possible digit combinations without $0$ digit: $\binom{9}{7}=36$

$(2)$ Number of possible digit combinations including $0$ digit: $\binom{9}{6}=84$

So there are $36 \cdot 7!+84 \cdot 6 \cdot 6!=544320$ numbers without digit repetition.

Now we have to find the numbers divisible by $3$.

We can seperate the cases:

$(1.a)$ $1$ digit divisible by $3$, $6$ digits not divisible by $3$: $\binom{3}{1}\binom{6}{6}=3\cdot1=3$

Out of the $\binom{6}{6}=1$ case $$(1,2,4,5,7,8)$$ $1$ is divisible by $3$, so there are $\binom{3}{1}\cdot 1=3$ numbers divisible by $3$.

$(1.b)$ $2$ digits divisible by $3$, $5$ digits not divisible by $3$: $\binom{3}{2}\binom{6}{5}=3\cdot6=18$

Out of the $\binom{6}{5}=6$ cases $$(1,2,4,5,7),(1,2,4,5,8),(1,2,4,7,8),(1,2,5,7,8),(1,4,5,7,8),(2,4,5,7,8)$$ $0$ is divisible by $3$, so there are $\binom{3}{2}\cdot 0=0$ numbers divisible by $3$.

$(1.c)$ $3$ digits divisible by $3$, $4$ digits not divisible by $3$: $\binom{3}{3}\binom{6}{4}=1\cdot15=15$

Out of the $\binom{6}{4}=15$ cases $$(1,2,4,5),...,(4,5,7,8)$$ $9$ is divisible by $3$, so there are $\binom{3}{3}\cdot 9=9$ numbers divisible by $3$.

So in the $(1)$ case there are $(3+0+9)\cdot 7!=12\cdot 7!=60480$ numbers divisible by $3$.

Similarly we can find that in the $(2)$ case there are $=30\cdot 6\cdot 6!=129600$ numbers divisible by $3$.

Maybe it's not the best approach and for some numbers we have to test the 3-divisibility, but we got the answer: $60480+129600=190080$