Обозначим через $S_n$ сумму первых $n$ простых чисел: $S_1 =2$, $S_2=2+3=5$, $S_3=2+3+5=10$, $S_4=17$ и т. д. Докажите, что при любом $n$ между $S_n$ и $S_{n+1}$ встречается точный квадрат.
Первое решение. Докажем более общее утверждение, рассмотрев вместо последовательности простых чисел последовательность $(p_n)$ такую, что $p_1=2$, $p_2\ge3$, $p_{n+1}-p_n\ge2$. Докажем, что при любом $n$ между числами $s_n$ и $s_{n+1}$, где $s_n=p_1+p_2+\ldots+p_n$, встречается точный квадрат.
Предположим, что при каком-то $n$ между числами $s_n$ и $s_{n+1}$ нет квадратов; т. е. для некоторого $k$
$$
k^2\le s_n\lt s_{n+1}\le (k+1)^2. \tag{*}
$$
Тогда $p_{n+1}=s_{n+1}-s_n\le(k+1)^2-k^2=2k+1$, поэтому $p_n\le p_{n+1}-2\le2k-1$ и т. д. — выполняются соотношения
$$
\begin{align*}
p_{n+1}&\le2k+1,\\
p_n&\le2k-1,\\
p_{n-1}&\le2k-3,\\
p_{n-2}&\le2k-5,\\
{\ldots}\,&{\ldots}\,{\ldots}\\
p_2=3&\le x,\\
p_1=2&\le x-2.
\end{align*}$$
Каким числом может быть $x$? Если $x=3$, то все неравенства должны превратиться в равенства (при этом $k=n$) и $$
s_{n+1}=2+p_2+\ldots+p_{n+1}\gt1+3+\ldots+(2k+1)=(k+1)^2,
$$
в противоречие с правым неравенством (*). Если же $x\ge 5$, то $x-2\ge3$ и $$
s_n=2+p_2+\ldots+p_n\lt1+3+\ldots+(2k-1)=k^2
$$
в противоречие с левым неравенством (*).
Все решения, присланные читателями, так или иначе используют идею сравнения последовательности $(p_n)$ с последовательностью $(2n-1)$, которая растёт медленнее и для которой сумма первых $n$ членов равна $n^2$.
Второе решение. Пусть $S_n=p_1+p_2+\ldots+p_n$ — сумма первых $n$ простых чисел. В таблице выписаны значения $S_n$ при $n=1$, 2, $\ldots$, 12 и все точные квадраты, лежащие в интервалах $(S_1,S_2)$, $(S_2,S_3)$, $\ldots$, $(S_{11},S_{12})$. Мы видим, что все эти интервалы содержат хотя бы по одному точному квадрату, а интервал $(S_{11},S_{12})$ содержит даже два квадрата — 169 и 196. Условимся в дальнейшем называть интервал $(S_{k-1},S_k)$ богатым, если он содержит по крайней мере два точных квадрата.
Для решения задачи при $n\ge12$ воспользуемся методом математической индукции. Пусть каждый из интервалов $(S_1, S_2)$, $(S_2, S_3)$, $\ldots$, $(S_{n-1},S_n)$ содержит точный квадрат. Пусть, далее, $(S_{n-k-1},S_{n-k})$ — первый богатый интервал в последовательности интервалов $(S_{n-1},S_n)$, $(S_{n-2},S_{n-1})$, $(S_{n-3},S_{n-2})$, $\ldots$ Пусть $m^2$ — максимальный квадрат, принадлежащий $(S_{n-k-1},S_{n-k})$. Тогда $(m-1)^2\in(S_{n-k-1},S_{n-k})$, а каждый из интервалов $(S_{n-k},S_{n-k+1})$, $(S_{n-k+1},S_{n-k+2})$, $\ldots$, $(S_{n-1},S_n)$ содержит ровно по одному квадрату. Другими словами,
$$
\begin{gather*}
S_{n-k-1}\lt (m-1)^2\lt m^2\lt S_{n-k}\lt (m+1)^2\lt S_{n-k+1}\lt \ldots\\
\ldots\lt (m+k-1)^2\lt S_{n-1}\lt (m+k)^2\lt S_n\lt (m+k+1)^2.
\end{gather*}
$$
Тогда $p_{n-k}=S_{n-k}-S_{n-k-1}\gt m^2-(m-1)^2=2m-1$. Так как, очевидно, $n-k\ge12$ и $p_{s+1}\gt p_s+2$ при $s\ge2$, получаем $p_{n+1}\gt p_{n-k}+2(k+1)\gt 2(m+k)+1$. Следовательно, $S_{n+1}=S_n+p_{n+1}\gt (m+k)^2+2(m+k)+1=(m+k+1)^2$. Поэтому $S_n\lt(m+k+1)^2\lt S_{n+1}$, т. е. интервал $(S_n,S_{n+1})$ содержит точный квадрат.
