ILL 1992 Problem 19

Denote by $a_n$ the greatest number that is not divisible by $3$ and that divides $n$ . Consider the sequence $s_0 = 0, s_n = a_1 +a_2+\cdots+a_n, n \in \mathbb N$ . Denote by $A(n)$ the number of all sums $s_k \ (0 \leq k \leq 3^n, k \in \mathbb N_0)$ that are divisible by $3$ . Prove the formula $$A(n) = 3^{n-1} + 2 \cdot 3^{(n/2)-1} \cos \left(\frac{n\pi}{6}\right), n\in \mathbb N_0.$$