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.

  • 2
    $\begingroup$ Why do you think that there should be "a greatest $n$" with this property? $\endgroup$ – 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$.

  • $\begingroup$ Let me get the understanding of this. So if floor(sqrt(n)) is greater than six, that means i am able to factor something out of the bracket and that means it cannot be ever a prime. What i don't get is the line of the inequality: (6n-(2floor(sqrt(n))^+3floor(sqrt(n))-5))>= (6n-(2n+3n-5)) = n+5>6 $\endgroup$ – Michal Dvořák Nov 27 '17 at 15:49
  • $\begingroup$ Because $\lfloor\sqrt{n}\rfloor^2$ and $\lfloor\sqrt{n}\rfloor$ are less or equal to $n$. $\endgroup$ – Robert Z Nov 27 '17 at 15:56
  • $\begingroup$ Wait, I am still confused, would you please reveal it for me in more detail? $\endgroup$ – Michal Dvořák Nov 27 '17 at 16:11
  • $\begingroup$ $\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$. $\endgroup$ – Robert Z Nov 27 '17 at 16:45
  • $\begingroup$ Ah, I missed that $-$ sign there. Now it's clear $\endgroup$ – Michal Dvořák Nov 27 '17 at 16:49

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.