Is it Number Theory or Combinatorics ?

Generalization For $k≥1$ , let $a_{k}$ be the greatest divisor of $k$ which is not a multiple of $3$ .

Set $S_{0}=0$ and $S_{k}=a_{1}+a_{2}+...+a_{k}$ for $k≥1$ .

Let $A_{n}$ be the number of integers $0≤k<3^{n}$ such that $S_{k}$ is divisible by $3$ .

Then $A_{n}=\frac{3^{n}+2.3^{n/2}cos(nπ/6)}{3}$ .

Proof : It is easy to see that $a_{3k}=a_{k}$ , $a_{3k+1}=3k+1$ , $a_{3k+2}=3k+2$

Now, $S_{0}≡0(mod 3)$ , $S_{1}≡1(mod 3)$ and $S_{2}≡0(mod 3)$

I claim that $S_{3k}≡S_{k}(mod 3)$ , $S_{3k+1}≡S_{k}+1(mod 3)$ and $S_{3k+2}≡S_{k}(mod 3)$ .

I will prove it by induction on $k$ .Suppose the result is true for $k$ .

Then, $S_{3k+3}=S_{3k+2}+a_{3k+3}≡S_{k}+a_{k+1}=S_{k+1} (mod 3)$

$S_{3k+4}=S_{3k+3}+a_{3k+4}≡S_{k+1}+3k+4≡S_{k+1}+1(mod 3)$

Finally, $S_{3k+5}=S_{3k+4}+a_{3k+5}≡S_{k+1}+1+5≡S_{k+1} (mod 3)$

Let $T_{k}$ be the number of $1$ 's in the ternary (base $3$ ) representation of $k$ .

$T_{0}=0$ , $T_{1}=1$ and $T_{2}=0$

A little thinking shows $T_{3k}=T_{k}$ , $T_{3k+1}=T_{k}+1$ and $T_{3k+2}=T_{k}$

Hence, $S_{k}≡T_{k} (mod 3)$ .Therefore, $A_{n}$ is the number of integers $0≤k≤3^{n}$ that has ternary representation in which the number of $1$ 's is a multiple of 3.

Now,there are $2^{n-j}\binom{n}{j}$ integers less than $3^{n}$ which have $j$ ones in their ternary representation, since there are $\binom{n}{j}$ ways to choose the places for $1$ and $2^{n-j}$ ways to put $0$ or $2$ in the remaining $n-j$ places.

Hence, $A_{n}=\sum_{j≡0(mod3)}\binom{n}{j}2^{n-j}$

Let $f(x)=(x+2)^{n}=\sum_{j=0}^{n}\binom{n}{j}x^{j}2^{n-j}$

Let $ω=e^{2πi/3}$ be cube root of unity.

By, Multisection Formula

$A_{n}=\frac{f(1)+f(ω)+f(ω^{2})}{3}=\frac{3^{n}+2.3^{n/2}cos(\frac{n\pi}{6})}{3}$ (Simplifying)

Putting $n=15$ gives the required answer.

Note The Multisection Formula says-

If $f(x)=\sum_{k}a_{k}x^{k}$ , then $\sum_{k≡r(mod m)}a_{k}x^{k}=\frac{1}{m}\sum_{s=0}^{m-1}ω^{-rs}f(ω^{s}x)$ where $ω=e^{2πi/m}$ .

Was all of this really reqd. I managed it by just using the fact that such nos. are only of form 3k-1. And all natural No's. <= 3^15. of such type satisfied it. I.e. No's. Like 2,5,8,...... To 3^15. The no. Of terms of the A. P. gives the final ans. As. G. I. F. OF [3^14+1÷3].

This was a fun puzzle. Warning: I'm in a computer scientist by nature so my solutions usually have a non purely-analytic nature to them. Here's how I solved this puzzle with linear algebra by reducing this to a rewrite system.

The difficult part of the problem depends on finding a nice recurrence to describe the system. Suppose that ${n+1\choose 2}$ describes the total of $1,\dots, n$ , then it is clear that $S_n = {n+1\choose 2} - 2 {\left\lfloor \frac{n}{3} \right\rfloor + 1 \choose 2} - 2 {\left\lfloor \frac{n}{3^2} \right\rfloor + 1 \choose 2} - \cdots$ With a bit of manipulation, and appealing to the fact the $\cdots$ in the above sum terminates after a finite ( $\left\lfloor \log_3(n) \right\rfloor$ ) number of times, we shall see that $S_n = {n+1\choose 2} + S_{\lfloor n/3 \rfloor} - 3 {\left\lfloor \frac{n}{3} \right\rfloor + 1 \choose 2}$

Theorem: Let $T_n = S_n ~\text{mod}~3$ , then $T_0 = 0, T_1 = 1, T_2 = 0$ and $T_{3n+m} = T_{n} + [m \equiv 1]$ Proof: Follows from the definition of $S_n$ . $~~~~~~~~~~\square$

Corollary: It is the case that $T_{3n} = T_n$ Proof: Also follows from the definition of $S_n$ . $~~~~~~~~~~\square$

The above two lemmas tells us two things: 1) we can uniquely determine what $S_{3n+1}, S_{3n+2}$ are from $S_{3n}$ . 2) The subsequence $(T_0, T_3, T_6, \cdots) = (T_0, T_1, T_2, \cdots)$ .

Now, in order to solve this problem, let us look at a tower of sequences.

Let $\begin{aligned} T^{15} &= (T_0) \\ T^{14} &= (T_0, T_{3^{14}}, T_{2\times 3^{14}}) \\ T^{13} &= (T_0, T_{3^{13}}, \cdots, T_{8\times 3^{14}}) \\ & \vdots \\ T^{1} &= (T_0, T_3, \cdots, T_{3^{15}-3}) \\ T^{0} &= (T_0, T_1, \cdots, T_{3^{15}-1}) \end{aligned}$

Based on the theorem we've proved above, we know that if we see a $0$ in $T ^{k+1}$ , then it would expand into the sequence $(0,1,0)$ in $T^k$ . Similarly, $1 \mapsto (1,2,1)$ and $2 \mapsto (2,0,2)$ . Now we're onto something.

Let $F(T^{k+1}) = T^k$ be the reduction rule. Suppose that we define a surjection $\gamma((0,1,2,0,2,0,0,0)) = (5,1,2)$ that counts the number of occurrences of 0, 1, and 2 respectively, then it turns out that we can transfer our reduction transformation $F(T^{k+1})$ into a linear transformation $\gamma(F) = \left(\begin{array}{ccc}2 & 0 & 1 \\ 1 & 2 &0 \\ 0 & 1 & 2\end{array}\right)$

This is because each instance of 0 in $T^k$ can be generated twice from a 0 in $T_{k+1}$ and once from a 2, so on for 1 and 2 as well. The crucial feature of the problem that enables us to construct this surjective counting is the fact that the ordering of $T_n$ isn't important.

Finally, we wish to find the count of $T_n$ that are zero, which is solved by taking $(1 ~~ 0 ~~ 0) \gamma(T^{0}) = (1 ~~ 0 ~~ 0) \gamma(F)^{15} \gamma(T^{15}) = (1 ~~ 0 ~~ 0)\left(\begin{array}{ccc}2 & 0 & 1 \\ 1 & 2 &0 \\ 0 & 1 & 2\end{array}\right)^{15} \left(\begin{array}{c}1 \\ 0 \\ 0\end{array}\right)$

You can compute this on a CAS if you want, but its characteristic polynomial $\rho(x) = (x-3) \left(x^2-3 x+3\right)$ has roots $\lambda = 3, \frac{3 \pm i\sqrt{3}}{2}$ , which means that the count is $\alpha 3^n + \beta \left(\frac{3 + i\sqrt{3}}{2}\right)^n + \gamma\left(\frac{3 + i\sqrt{3}}{2}\right)^n = 3^{n-1}$ So in our case, we just have $3^{15-1} = \boxed{4782969}$ .