Problem 1776

Denote by $S = \{2, 0, 1, 5\}$ and
$$A(n, i) = \{\overline{x_n x_{n-1} \dots x_1} : x_j \in S \text{ and } x_1 + \dots + x_n \equiv i \pmod{3}\}.$$
Let $a_n, b_n$ and $c_n$ be the cardinal number of $A(n, 0)$, $A(n, 1)$ and $A(n, 2)$ respectively. Since a natural number is divisible by $3$ if and only if the sum of its digits is a multiple of $3$, we only need to count the number of elements in the set $A(k, 0)$. Let $\overline{x_1 \dots x_{n+1}}$ be an element of $A(n+1, 0)$, we have

* If $x_{n+1} = 0$ then $(x_1, x_2, \dots, x_n) \in A(n, 0)$.
* If $x_{n+1} = 2$ or $5$ then $(x_1, x_2, \dots, x_n) \in A(n, 1)$.
* If $x_{n+1} = 1$ then $(x_1, x_2, \dots, x_n) \in A(n, 2)$.

Hence, $a_{n+1} = a_n + 2b_n + c_n$ (1). Similarly, we get
$$b_{n+1} = a_n + b_n + 2c_n, \quad (2)$$
$$c_{n+1} = 2a_n + b_n + c_n. \qquad (3)$$
From those equations, we have $a_2 = 5$, $b_2 = 6$, $c_2 = 5$, $a_3 = 22$, $b_3 = 21$, $c_3 = 21$. Moreover,
$$a_{n+1} - b_{n+1} = a_n + 2b_n + c_n - a_n - b_n - 2c_n = b_n - c_n,$$
$$b_{n+1} - c_{n+1} = a_n + b_n + 2c_n - 2a_n - b_n - c_n = c_n - a_n,$$
$$c_{n+1} - a_{n+1} = c_{n+1} - b_{n+1} + b_{n+1} - a_{n+1} = a_n - b_n.$$
This leads to
$$a_{n+3} - b_{n+3} = b_{n+2} - c_{n+2} = c_{n+1} - a_{n+1} = a_n - b_n.$$
Similarly,
$$b_{n+3} - c_{n+3} = b_n - c_n, \quad c_{n+3} - a_{n+3} = c_n - a_n.$$
Hence, it is easy to see that
* If $k \equiv 0 \pmod 3$ then $b_k = c_k = a_k - 1$.
* If $k \equiv 1 \pmod 3$ then $a_k = b_k = c_k - 1$.
* If $k \equiv 2 \pmod 3$ then $a_k = c_k = b_k - 1$.

On the other hand, $a_k + b_k + c_k$ is equal to the cardinal number of $A(k) = \{\overline{a_k a_{k-1} \dots a_1} : a_j \in S\}$ so that
$$a_k + b_k + c_k = 4^k.$$
In conclusion, the value of $a_k$ is
* $a_k = \frac{4^k - 1}{3}$ if $k$ is not a multiple of $3$;
* $a_k = \frac{4^k + 2}{3}$ if $k$ is a multiple of $3$.