Find the greatest n for which the sum $\sum_{k=1}^n \lfloor\sqrt{k}\rfloor$ is a prime number.

Question

I've come across the sum: $$\sum_{k=0}^n \lfloor\sqrt{k}\rfloor$$ According to Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$ I approached the formula: $$\sum_{k=0}^n \lfloor\sqrt{k}\rfloor = n\lfloor\sqrt{n}\rfloor-\frac{1}{3}\lfloor\sqrt{n}\rfloor^3-\frac{1}{2}\lfloor\sqrt{n}\rfloor^2+\frac{5}{6}\lfloor\sqrt{n}\rfloor$$ Now, programmaticaly I attempted this formula for first $100$ terms. The biggest possible $n$ for which this sum was a prime number should be $47$. Now, is there a precise mathematical approach to this? I can't seem to find a solution.

Answer 1

Note that for $n\geq 1$, the sum $S_n$ is a positive integer which can be written as $$S_n:=\sum_{k=0}^n \lfloor\sqrt{k}\rfloor =\frac{1}{6}\cdot\lfloor\sqrt{n}\rfloor\cdot\left(6n-(2\lfloor\sqrt{n}\rfloor^2+3\lfloor\sqrt{n}\rfloor-5)\right).$$ where $f_1:=\lfloor\sqrt{n}\rfloor$ and $f_2:=\left(6n-(2\lfloor\sqrt{n}\rfloor^2+3\lfloor\sqrt{n}\rfloor-5)\right)$ are positive integers.

Therefore if $f_1:=\lfloor\sqrt{n}\rfloor>6$ (i.e. $n\geq 49$) and $$f_2=\left(6n-(2\lfloor\sqrt{n}\rfloor^2+3\lfloor\sqrt{n}\rfloor-5)\right)\geq \left(6n-(2n+3n-5)\right)=n+5>6$$ (i.e. $n\geq 2$) then $S_n=\frac{f_1\cdot f_2}{6}$ is not a prime (because $S_n$ is the product of two integer factors both greater than $1$).

Hence the largest $n$ such that $S_n$ is a prime, exists, it is less than $49$ and, according to your computations, we may conclude that it is equal to $47$ with $S_{47}=197$.