3
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Cornman
    Nov 29, 2020 at 4:06
  • 3
    $\begingroup$ 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$. $\endgroup$ Nov 29, 2020 at 4:07
  • 2
    $\begingroup$ @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$ $\endgroup$ Nov 29, 2020 at 4:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tbw
    Nov 29, 2020 at 4:17
  • $\begingroup$ @GregMartin I get your logic, but I don't quite see how it helps to solve the problem. $\endgroup$ Nov 29, 2020 at 4:45

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.