4. Let $n$ be a positive integer. Given a real number $x$, let $\lfloor x\rfloor$ be the greatest integer less than or equal to $x$. For example, $\lfloor 2.4\rfloor=2,\lfloor 3\rfloor=3$ and $\lfloor\pi\rfloor=3$. Define a sequence $a_{1}, a_{2}, a_{3}, \ldots$ where $a_{1}=n$ and
$$
a_{m}=\left\lfloor\frac{a_{m-1}}{3}\right\rfloor,
$$
for all integers $m \geq 2$. The sequence stops when it reaches zero. The number $n$ is said to be lucky if 0 is the only number in the sequence that is divisible by 3 . For example, 7 is lucky, since $a_{1}=7, a_{2}=2, a_{3}=0$, and none of 7,2 are divisible by 3. But 10 is not lucky, since $a_{1}=10, a_{2}=3, a_{3}=1, a_{4}=0$, and $a_{2}=3$ is divisible by 3 . Determine the number of lucky positive integers less than or equal to 1000 .
Solution ${ }^{1}$ : Note that $\lfloor m / 3\rfloor$ is simply chopping off the right-most digit of the base 3 representation of $m$. Hence, what the sequence is doing is that given an integer $n$, we repeatedly chop the right-most digit of the base 3 representation of $n$, until no digits remain. A base 3 representation is divisible by 3 if and only if the right most digit is zero. Then $n$ is lucky if and only if none of the digits of the base 3 representation of $n$ is zero.

We convert the integer $n$ to base 3 . We first find the base 3 representation of 1000 . Note that $1000 / 3=333+1 / 3,333 / 3=111+0 / 3,111 / 3=37+0 / 3,37 / 3=12+1 / 3,12 / 3=4+0 / 3$, $4 / 3=1+1 / 3$ and $1 / 3=0+1 / 3$. Therefore, the base 3 representation of 1000 is $1101001_{3}$. We need to find the number of base 3 representations, whose digits does not contain zero, less than or equal to this number.

Note that the largest lucky number less than or equal to $1101001_{3}$ is is $222222_{3}$. Lucky numbers less than or equal to 1000 are those whose base 3 representation consists of only digits 1 and 2 , and has at most 6 digits. There are $2^{k}$ such numbers whose base 3 representation has $k$ digits. Therefore, the total number of lucky numbers is $2^{6}+2^{5}+2^{4}+2^{3}+2^{2}+2^{1}=126$.