3

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?

questionasker
  • 1,148
  • 1
    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$? – Cornman Nov 29 '20 at 04:06
  • 3
    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$. – Greg Martin Nov 29 '20 at 04:07
  • 2
    @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$ – Michael Hardy Nov 29 '20 at 04:15
  • 1
    @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 '20 at 04:17
  • @GregMartin I get your logic, but I don't quite see how it helps to solve the problem. – questionasker Nov 29 '20 at 04:45

2 Answers2

2

Since the sequence was modified, the hint in the comment must be modified as well.

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$.

player3236
  • 16,413
1

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}$.

Tbw
  • 995