N3. Let $a_{1}, a_{2}, \ldots$ be an infinite sequence of positive integers satisfying $a_{1}=1$ and
$$
a_{n} \mid a_{k}+a_{k+1}+\cdots+a_{k+n-1}
$$
for all positive integers $k$ and $n$. Find the maximum possible value of $a_{2018}$.
(Krit Boonsiriseth)
The answer is $a_{2018} \leq 2^{1009}-1$. To see this is attainable, consider the sequence
$$
a_{n}=\left\{\begin{array}{ll}
1 & n \text { odd } \\
2^{n / 2}-1 & n \text { even. }
\end{array}\right.
$$

This can be checked to work, so we prove it's optimal.
We have $a_{2} \mid a_{1}+a_{2}=1+a_{2} \Longrightarrow a_{2}=1$.
Now consider an integer $n$, and let $s=s_{n}=a_{1}+\cdots+a_{n}$. Then
$$
\begin{array}{l}
a_{n+1} \mid s \\
a_{n+2} \mid s+a_{n+1} \\
a_{n+2} \equiv 1 \quad\left(\bmod a_{n+1}\right) .
\end{array}
$$

Thus, $\operatorname{gcd}\left(a_{n+2}, a_{n+1}\right)=1$. So $a_{n+2} \leq \frac{s+a_{n+1}}{a_{n+1}}$, and thus
$$
a_{n+1}+a_{n+2} \leq 1+a_{n+1}+\frac{s}{a_{n+2}} \leq s+2 .
$$

So, we have
$$
\begin{aligned}
a_{1}+a_{2} & =2 \\
a_{3}+a_{4} & \leq 2+2=4 \\
a_{5}+a_{6} & \leq(2+4)+2=8 \\
a_{7}+a_{8} & \leq(2+4+8)+2=16 \\
\vdots & \\
a_{2017}+a_{2018} & \leq 2^{1009} .
\end{aligned}
$$

Thus $a_{2018} \leq 2^{1009}-a_{2017} \leq 2^{1009}-1$.
Remark (Motivational notes). It's very quick to notice $a_{n+1} \mid a_{1}+\cdots+a_{n}$, which already means that given the first $n$ terms of the sequence there are finitely many possibilities for the next one. Thus it's possible to play with "small cases" by drawing a large tree.

When doing so, one might hope that somehow $a_{n}=a_{1}+\cdots+a_{n-1}$ is achievable, but quickly notices in such a tree that if $a_{n}$ is the sum of all previous terms, then $a_{n+1}=1$ is forced. This gives the idea to try to look at the terms in pairs, rather than one at a time, and this gives the correct bound.

As for extracting the equality case from this argument, there are actually two natural curves to try. We have $a_{3} \mid 1+1=2$. If we have $a_{3}=2$ we get $a_{4}=1, a_{5} \leq 5$, but then $a_{6}$ actually gets stuck. But if we have $a_{3}=1$ instead, we get $a_{4}=3, a_{5}=1, a_{6}=7$, and so on; pushing this gives the equality case above, seen to work. I think it's quite unnatural to guess the correct construction before having the corresponding $s+2$ estimate.