No.220

(3の倍数か3がつく数) = (3の倍数の数) + (3がつく数) - (3の倍数かつ3がつく数) である. これを個別に求める.

3の倍数の数:

$10^p / 3$ 個である.

3がつく数:

$10^k$ 以下の3のつく数を $A_k$ とする.

$i 10^{k-1} \leq n \lt (i+1) 10^{k-1} \ (i=0,1,\dots,9)$ の3がつく数を考えると, これは $i = 3$ のときは $10^{k-1}$ 個, そうでないときは $A_{k-1}$ 個となるので,

$$A_k = 10^{k-1} + 9A_{k-1}$$

s.t.

$$A_1 = 1$$

となる.

3の倍数かつ3がつく数:

$10^k$ 以下の3で割った余りが $m$ で3がつく数を $B_k(m)$ とする.

$i 10^{k-1} \leq n \lt (i+1) 10^{k-1} \ (i=0,1,\dots,9)$ の3で割った余りが $m$ かつ3がつく数を考えると, $n$ を3で割った余りは $n$ の各桁の数字の合計を3で割った余りと等しいので,

• $i = 3$ のとき, $m = 0$ ならば $10^{k-1} / 3 + 1$ 個, そうでないならば $10^{k-1} / 3$ 個

• $i = 0, 6, 9$ のとき, $m = 0$ ならば $B_{k-1}(0)$ 個, $m= 1$ ならば $B_{k-1}(2)$ 個, $m = 2$ ならば $B_{k-1}(1)$ 個

• $i = 1, 4, 7$ のとき, $m = 0$ ならば $B_{k-1}(2)$ 個, $m= 1$ ならば $B_{k-1}(1)$ 個, $m = 2$ ならば $B_{k-1}(0)$ 個

• $i = 2, 5, 8$ のとき, $m = 0$ ならば $B_{k-1}(1)$ 個, $m= 1$ ならば $B_{k-1}(0)$ 個, $m = 2$ ならば $B_{k-1}(2)$ 個

となる. よって,

$$B_k(0) = \frac{10^{k-1}}{3} + 3(B_{k-1}(0) + B_{k-1}(1) + B_{k-1}{2}) + 1 \\ B_k(m) = \frac{10^{k-1}}{3} + 3(B_{k-1}(0) + B_{k-1}(1) + B_{k-1}{2})$$

s.t.

$$B_1(0) = 1 \\ B_1(1) = 0 \\ B_1(2) = 0$$

となる.

なお $10^{19}$ は long の範囲を超えるので注意する.