# Permutation & Combination - how many numbers smaller than $2.10^8$ and are divisible by $3$ can be written by means of the digits $0$,$1$ and $2$

How many numbers smaller than $2\times10^8$ and divisible by $3$ can be written by means of the digits $0$,$1$ and $2$? Left zero padding not allowed.

I am getting this as -
$3$ digits - $2\cdot3 = 6$
$4$ digits - $2\cdot3\cdot3 = 18$
$5$ digits - $2\cdot3\cdot3\cdot3 = 54$
$6$ digits - $2\cdot3\cdot3\cdot3\cdot3 = 162$
$7$ digits - $2\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3 = 486$
$8$ digits - $2\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3 = 1458$

From $10^8$ to $2\times10^8$ - $2\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3 \cdot3\cdot3/2 = 2187$

I get $4371$ as the answer, but in the book the result is $4351$, am I making an error somewhere?

-
What is meant by zero padding? Padding on left, right, or even in between the other digits? –  Milind May 6 '13 at 4:31
Zeros on left... Not allowed. –  Joy May 6 '13 at 4:37
Total number of numbers divisible by $3$ is $2.10^8/3$. Now we need to count only the numbers whose digit are $0,1,2$ –  Learner May 6 '13 at 5:04

We solve the simpler problem of counting the numbers from $0$ to $10^8-1$ of the right shape that are divisible by $3$. We do allow zero padding to make all the numbers into $8$-digit numbers. This makes no difference to the count.

The same method works for the other half of our interval.

We use a general approach, though the particular case is too simple and quickly collapses. One could then in hindsight give a slicker argument, but we won't do that.

Let $a(n)$ be the number of $n$-digit numbers that use only $0$, $1$, and $2$ and are divisible by $3$. Let $b(n)$ be the number of $n$-digit numbers, of the right form, that give remainder $1$ on division by $3$, and let $c(n)$ be the same thing, except for remainder $2$. We have $a(1)=b(1)=c(1)=1$. Note that $$a(n+1)=a(n)+b(n)+c(n).$$ This is because a qualifying $n+1$ digit number can be obtained by appending a $0$ to an $n$-digit number divisible by $3$, or a $2$ to an $n$-digit number that has remainder $1$, or a $1$ to an $n$-digit number that has remainder $2$. Similarly, we have $b(n)=a(n)+b(n)+c(n)$ and $c(n)=a(n)+b(n)+c(n)$.

It follows that $a(2)=b(2)=c(2)=3$, and $a(3)=b(3)=c(3)=9$, and so on. Thus $a(8)=3^7$.

For the numbers from $1\times 10^8$ to $2\times 10^8-1$, do the same calculation for numbers of the form $1x$, where $x$ is a (padded) $8$-digit number.

-
I am getting this as - 3 digits - 2*3 = 6 4 digits - 2*3*3 = 18 5 digits - 2*3*3*3 = 54 6 digits - 2*3*3*3*3 = 162 7 digits - 2*3*3*3*3*3*3 = 486 8 digits - 2*3*3*3*3*3*3*3 = 1458 From 1*10^8 to 2*10^8 - 2*3*3*3*3*3*3*3*3/2 = 2187 I get 4371 as the answer, but in book this show 4351, am I making an Error somewhere. Please help!! Thanks. –  Joy May 6 '13 at 7:31
Will get back to you, probably not for half day or so, sleep, then busy half-day. –  André Nicolas May 6 '13 at 9:05
Checked again. from $0$ to $2\times 10^8$, have $2\times 3^7$. Take away $1$ if we don't want to count $0$. Your counts are correct, bur left out the $2$ digit $12$ and $21$, and (subject to interpretation) the $1$-digit number $0$. So $4373$ or $4374$, depending on interpretation. I do not see anything that we can discard that would lead to $4351$. –  André Nicolas May 6 '13 at 21:46