<s>[INST] Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$ I need to find a clear formula (without summation) for the following sum:
$$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$
Well, the first few elements look like this:
$1,1,1,2,2,2,2,2,3,3,3,...$
In general, we have $(2^2-1^2)$ $1$'s, $(3^2-2^2)$ $2$'s etc.
Still I have absolutely no idea how to generalize it for $n$ first terms...
 [/INST] The way I approached this problem is dividing the sum into two halves. Where the first half contains all the numbers starting from $1$ and reaching upto $m$ such that $\sqrt{m}$ is greatest integer $<\lfloor\sqrt{n}\rfloor$, and second half contains the leftover numbers. Intuitively $m$ can be calculated by using simple formula $\lfloor\sqrt{n}\rfloor - 1$Mathematically:

$\displaystyle\sum_{k=1}^n\lfloor\sqrt{k}\rfloor = \underbrace{\displaystyle\sum_{p=1}^{\lfloor\sqrt{n}\rfloor-1}p\times(2p + 1)}^{\text{first part}} +  \underbrace{(n - {\lfloor\sqrt{n}\rfloor}^2 + 1)\times{\lfloor\sqrt{n}\rfloor}}^{\text{second part}}$

The same can be resolved using the following identities.

$\displaystyle\sum_{x = 1}^n x = \frac{x\times(x+1)}{2}$ and $\displaystyle\sum_{x = 1}^n x^2 = \frac{x\times(x+1)\times(2 \times x+1)}{6}$

I didn't tested this solution with every value, but the solution seems convincing.
I am taking an example to demonstrate it, taking $n = 5$
The answer should contain $\underbrace{1+1+1+2+2}+2+2+2+3+... = 7$

The $\lfloor\sqrt{5}\rfloor-1 = 1$(upper limit for the first part)So, our first part is calculated as $1\times (2+1) = 3$
Similarly second part is calculated as $(5-{\lfloor\sqrt{5}\rfloor}^2)\times \lfloor\sqrt{5}\rfloor = (5 - 2^2+1)\times 2 = (2)\times 2 = 4$
So we get $4 + 3 = 7$ as our answer, which is correct.

The same intuition can be used to derive formula for $\displaystyle\sum_{k=1}^n\lfloor\sqrt[x]{k}\rfloor$.
i.e.

$\displaystyle\sum_{k=1}^n\lfloor\sqrt[x]{k}\rfloor = \displaystyle\sum_{p=1}^{\lfloor\sqrt[x]{p}\rfloor}p\times ((p+1)^x-p^x)+(n - (\rfloor\sqrt[x]{n}\rfloor)^x + 1)\times\lfloor\sqrt[x]{n}\rfloor$

P.S. This is just an intuition, if anything wrong, feel free to comment.
</s>