Sum of first n terms is prime.

Question

$a_n$ is a non-decreasing sequence of positive integers. If an positive integer $k$ appears in $a_n$ exactly $k$ times and $S_n$ is the sum of the first n terms, find all $N$ such that $S_N$ is prime.

The sequence is $$1,2,2,3,3,3,4,4,4,4,5,5,5,5,5, \cdots$$ If $n$ is a triangular number, then the sum is just the sum of squares. So $S_n=$ $$\frac{n(n+1)(2n+1)}{6}-kn$$ for some non negative integer $k<n$. $$S_n=\frac{n(2n^2+3n+1-6k)}{6}$$ I have somewhat closed form, but what could I do to find the $n$ such that it's prime? Thanks!

Answer 1

Let $n=m(m+1)/2 + j$ with $m$ a positive integer and $0\leq j \leq m$.

Then $S_n=\frac{(2m+1)(m+1)m}{6} + (m+1)j$.

We write this as $\frac{(2m^2+m+6j)(m+1)}{6}$

Suppose $m+1$ is not a divisor of $6$, then the left side must be a divisor of $6$. This is clearly only possible if $m=1$, in which case $j=0$ gives $S_n=1$ and $j=1$ gives $S_n=3$.

In the other cases $m+1$ must be a divisor of $6$.

If $m=2$ then $j=0$ gives $S_n= 5$, $j=1$ gives $8$ and $j=2$ gives $11$.

If $m=5$ then then $j=0$ gives $S_n = 55$, $j=1$ gives,$j=3$ gives $67$ $j=4$ gives $73$, and $j=5$ gives $79$.

Hence the values of $n$ that you want are $2, 3,5,16,17,18,19$

Answer 2

That closed form gives you a factorization of the sum, unless the six on the bottom can eat at least one of the two terms. This can only happen for small $n$, so you should be able to get an upper bound and then check the remaining cases directly.