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

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.

• Why do you think that there should be "a greatest $n$" with this property? – Dietrich Burde Nov 27 '17 at 9:28

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$.
• Because $\lfloor\sqrt{n}\rfloor^2$ and $\lfloor\sqrt{n}\rfloor$ are less or equal to $n$. – Robert Z Nov 27 '17 at 15:56
• $\lfloor\sqrt{n}\rfloor^2\leq n$, $\lfloor\sqrt{n}\rfloor\leq n$ imply $(2\lfloor\sqrt{n}\rfloor^2+3\lfloor\sqrt{n}\rfloor-5)\leq (2n+3n-5)=5n-5$. – Robert Z Nov 27 '17 at 16:45
• Ah, I missed that $-$ sign there. Now it's clear – Michal Dvořák Nov 27 '17 at 16:49