Square in Interval of Primes

Question

Denote by $a_n$ the sum of the first $n$ primes. Prove that there is a perfect square between $a_n$ and $a_{n+1}$, inclusive, for all $n$.

The first few sums of primes are $2$, $5$, $10$, $17$, $28$, $41$, $58$, $75$. It seems there is a perfect square between each pair of successive sums. In addition, we can put a bound on $a_n$, namely $a_n \le 2+3+5+7+9+11+...+(2n+1)=n^2+2n+5$.

Please include what you've attempted or have trouble with. As it is, it's not a question but a command. — user137794, Sep 21 '14 at 03:41
"The first few primes are $2, 5, 10,\ldots$"; I don't agree. — Marc van Leeuwen, Sep 21 '14 at 05:09
@daniel: I've edited, and at the same time corrected a few other errors (sense of the inequality, and evaluation of the sum). — Marc van Leeuwen, Sep 21 '14 at 05:17
possible duplicate of Existence of perfect square between the sum of the first $n$ and $n + 1$ prime numbers — daniel, Sep 21 '14 at 06:59
The last element in the sample sequence 2,5,10,... should be 77 not 75. — daniel, Sep 21 '14 at 11:03
By the way, this problem was on one of the national olympiads and was on one of our problem sets called Recurrences in Combinatorics Part 1 — William Yi, Sep 21 '14 at 14:35

score 1 · Answer 1 · answered Sep 21 '14 at 04:03

1

Let $p$ be the $(n+1)$st prime. Then $a_n\le (-8)+(1+3+5+7+9+\ldots +p-2)=(\frac{p-1}{2})^2-8$ provided $p\ge 11$ (the smaller cases can be dealt with by checking manually). So with $b_n:=\lfloor \sqrt {a_n}\rfloor $ we have $b_n< \frac{p-1}{2}$. Then $a_n<(b_n+1)^2=b_n^2+2b_n+1< a_n+p=a_{n+1}$ as was to be shown.

answered Sep 21 '14 at 04:03

Hagen von Eitzen

374,180

I think I can see where you are going, but you forgot to pronounce any of the arguments you are using, leaving just the formulas. For instance I would guess you are bounding the sum of prime numbers up to $p$ by the sum of all odd numbers up to $p$, but the appearance of $-8$ is a mystery. – Marc van Leeuwen Sep 21 '14 at 05:06

score 1 · Answer 2 · answered Sep 21 '14 at 04:16

(waving my hands frantically to keep me aloft:)

$a_n \approx \sum_{k=1}^n k\ln k \approx \int_{1}^n k \ln k\ dk \approx n^2\ln n $ and $a_{n+1}-a_n \approx n\ln n $ so if $b_n = \lfloor \sqrt{a_n}\rfloor $, $b_n \approx n\sqrt{\ln n} $.

The next square after $b_n^2$ is $(b_n+1)^2 =b_n^2+2b_n+1 \approx b_n^2+2n\sqrt{\ln n} $ and since $a_{n+1}-a_n \approx n\ln n $, $(b_n+1)^2 < a_{n+1} $ for large anough $n$.

Note that $(b_n+k)^2 =b_n^2+2kb_n+k^2 \approx b_n^2+2kn\sqrt{\ln n} $, so, by choosing $k \approx \frac12 \sqrt{\ln n}$, it looks like there are about $\frac12 \sqrt{\ln n}$ squares between $a_n$ and $a_{n+1}$.

score 1 · Answer 3 · answered Sep 21 '14 at 06:07

This result follows from the well established fact that all primes numbers, with the exception of the first one which is$~2$, are odd.

Observe that for any positive integer$~n$, (a) the sum of all positive odd numbers less than $2n$ is $n^2$, and (b) the first gap of $2n$ successive natural numbers containing no perfect square is the range $n^2+1,\ldots,n^2+2n$.

I prove a stronger statement: for any set $S$ of positive odd numbers that includes $1$, if $2n-1$ is its greatest element, there is a perfect square among the $2n$ numbers $a-(2n-1),\ldots,a$ where $a=1+\sum S$.

(Apply this to the sequence of prime numbers after subtracting $1$ from the initial prime number $2$, which subtraction is compensated by the additional term $1$ in the expression for $a$.)

By the above observation (b) it suffices to show that $a-(2n-1)\leq n^2$, and since $n\geq1$ follows from $\sum S\leq n^2$ obtained from observation (a) (the sum of a subset of positive numbers is at most the sum of all).

Square in Interval of Primes

3 Answers3