# Finding the amount of prime numbers in $S_1, S_2,S_3,\ldots$

Let $$\{a_n\}$$ be a non-decreasing sequence of positive integers. For any positive integer $$k,$$ there are exactly $$k$$ terms in the sequence equal to $$k.$$ Let $$S_n$$ be the sum of first $$n$$ terms. How many prime numbers are there in the set $$\{S_1,S_2,\ldots\}?$$

My initial thought was to find a pattern of sorts, so I got \begin{align*} S_1 &= 1 \\ S_2 &= 3 \\ S_3 &= 5 \\ S_4 &= 8 \\ S_5 &= 11 \\ S_6 &= 14 \\ S_7 &= 18 \\ S_8 &= 22 \\ & \vdots \\ \end{align*} I noticed that after a certain $$S_n,$$ all the numbers seemed to be composite no matter what. However, I wasn't quite sure how to prove this, so can somebody help me?

• If I understand correctly we have the sequence $(1,2,2,3,3,3,4,4,4,4,5,5,5,5,5, 6, \dotso)$. Then $S_1=1$, $S_2=3$, $S_3=5$, $S_4=8$ and so on. How do you get your $S_n$? Nov 29, 2020 at 4:06
• Your sequence is simply $S_n =$ the sum of the first $n$ squares, which is well known to equal $n(n+1)(2n+1)/6$. In particular, $S_n$ is automatically composite once $n\ge7$. Nov 29, 2020 at 4:07
• @GregMartin : $3$ and $8$ and $11$ and $18$ and $22$ are not the sum of the first $n$ squares, for any value of $n. \qquad$ Nov 29, 2020 at 4:15
• @Greg Martin, while you are correct in your conclusion, $S_n$ is not the sum of the first $n$ squares; $S_{n(n+1)/2}$ is.
– Tbw
Nov 29, 2020 at 4:17
• @GregMartin I get your logic, but I don't quite see how it helps to solve the problem. Nov 29, 2020 at 4:45

The $$\dfrac {n(n+1)}2$$-th term of the sequence is given by $$\dfrac {n(n+1)(2n+1)}6$$.
From this term to the $$\dfrac {(n+1)(n+2)}2$$-th term, the terms are given by $$\dfrac {n(n+1)(2n+1)}6 + k(n+1)=\frac {n+1}6(2n^2+n+6k)$$ for some integer $$k$$.
Since the above expression is always an integer, it cannot be prime for $$n+1 >6$$.
Because the sequence is $$(1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,…)$$, the sum up to the end of a run of the same number is $$S_{n(n+1)/2} = \frac{n(n+1)(2n+1)}{6}$$ which must be an integer. Therefore, the terms on the top of the fraction must contain a 2 and a 3 in their factorizations.
After $$S_{n(n+1)/2}$$, the following terms of $$S$$ are additions of $$n+1$$. If $$n+1$$ did not contribute in giving a 2 or a 3 to the fraction, then $$n+1$$ is a factor of each successive term, proving they are all composite. If it contributed a 2, then $$(n+1)/2$$ is a factor. A similar factor is found if it contributed a 3 or a 6. This proves that each term is composite whenever these factors are not equal to 1 or $$n+1 \neq 1,2,3,6$$. So one need only compute up to $$S_{21}$$.