3. Let $n, m$ be positive integers with $m>n \geq 5$ and with $m$ depending on $n$. Consider the sequence $a_{1}, a_{2}, \ldots, a_{m}$ where
$$
\begin{aligned}
a_{i} & =i & & \text { for } i=1, \ldots, n \\
a_{n+j} & =a_{3 j}+a_{3 j-1}+a_{3 j-2} & & \text { for } j=1, \ldots, m-n
\end{aligned}
$$
with $m-3(m-n)=1$ or 2 , i.e., $a_{m}=a_{m-k}+a_{m-k-1}+a_{m-k-2}$ where $k=1$ or 2. (Thus if $n=5$, the sequence is $1,2,3,4,5,6,15$ and if $n=8$, the sequence is $1,2,3,4,5,6,7,8,6,15,21$.) Find $S=a_{1}+a_{2}+\cdots+a_{m}$ if (i) $n=2007$, (ii) $n=2008$.
3. We shall solve the problem for general $n$. Initially, let $a_{1}, a_{2}, \ldots, a_{n}$ be the active sequence. An operation removes the first three terms and append their sum as the last term of the sequence. Thus after one operation on the initial sequence, the active sequence is $a_{4}, a_{5}, \ldots, a_{n+1}$. Such operations will stop when the active sequence is of length at most 2. In this case, the last term of the active sequence is $a_{m}$. The following observations are obvious.
1. After each operation, the length of the active sequence decreases by 2 and the sum of its terms is preserved.
2. If the length of an active sequence is $3 k$ and the last term is $a_{p}$, then after $k$ operations, the length of the active sequence is $k$ and the first term is $\|_{p}+1$.

To compute $S$, we have two cases:
Case (i). $n$ odd. Let $k$ and $r$ be integers such that $n=3^{k}+2 r<3^{k+1}$, i.e., $0 \leq r<3^{k}$. Note that $3 r<n$. The first $3 r$ terms, $a_{1} \ldots \ldots a_{3 r}$ is called the forst block and the sum of its terms is $M=1+2+\cdots+3 r=3 r(3 r+1) / 2$. Now apply the above observations. The sum of the terms of any active sequence is $N=1+2+\cdots+n=n(n+1) / 2$. After $r$ operations, the length of the active sequence is $3^{k}$ and its first term is $a_{1 i r+1}$. This active sequence is called the scromd block. After $3^{k-1}$ operations, the length of the active sequence is $3^{k-1}$. This active sequence is called the third block. Repeat this until the length of the active sequence is 1 . This is now the $(k+2)^{\text {mil }}$ block. Thus we have a block whose sum is $M$ and $k+1$ blocks whose sum is $N$. Hence $S=M+(k+1) N$. Since $3^{b}=729, n=2007=3^{6}+2(639)$, we have $S=15943599$.
Case (ii). $n$ even. Let $k$ and $r$ be integers such that $n=2\left(3^{k}\right)+2 r<2\left(3^{k-1}\right)$, i.e., $0 \leq r<2\left(3^{k}\right)$. Note that $3 r<n$. The first $3 r$ terms, $a_{1} \ldots \ldots, a_{i s}$ is called the first block and the sum of its terms is $M$. As in case $\mathrm{i}$, after $r$ 'operations, the length of the active sequence is $2\left(3^{k}\right)$ and its first term is $a_{3 r-1}$. This active sequence is called the second bleck: After $2\left(3^{k-1)}\right.$ operations, the length of the active sequence is $2\left(3^{k-1}\right)$. This active sequence is called the thard block. Repeat this until the length of the active sequence is 2 . This is now the $(k+2)^{\text {1ut }}$ block. Thus we have a block whose sum is $M$ and $k+1$ blocks whose sum is $N$. Hence $S=M+(k+1) N$. Since $3^{6}=729,2008=2\left(3^{6}\right)+2(275)$. Thus $r=275$ and $k=6$ and so $S=14159977$.