# Efficient computation of $\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor$

I need to compute efficiently the sum $$\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor.$$

We can do this in $$O({\sqrt{n}})$$ but I need a faster algorithm: for example, it would be fine an algorithm of complexity $$O(\sqrt[3]{n})$$ (cube root in time) or $$O(\log n)$$ whatever, but however less than the square root in time.

edit1:

So far what i have got $$\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor= n *\left \lfloor {\sqrt{n}} \right \rfloor - \sum_{i=1}^{i=\left \lfloor {\sqrt{n}} \right \rfloor} n \mod i^{2}$$

Now how can we efficiently compute $$\sum_{i=1}^{i=\left \lfloor {\sqrt{n}} \right \rfloor} n \mod i^{2}$$

edit2:

We can look at it by taking $$\left\lfloor\frac{N}{i^2}\right\rfloor=1$$ whenever $$1\leq\frac{N}{i^2}<2$$. So whenever $$\sqrt{N}\geq i>\sqrt{\frac{N}{2}}$$. There are $$\left\lfloor\sqrt{N}\right\rfloor-\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor$$ such values of $$i$$.Now how can $$i^2$$ can be multiplied to the above terms.

• This seems to be an active question on codechef competition. It has been flooding math.stackexchange. – Gerry Myerson Apr 12 at 11:44

Following by comment of Alexey Kulikov we could split our sum in the next way: $$\sum_{i=1}^{[\sqrt{n}]} i^2\left [\frac{n}{i^2}\right ]= \sum_{[n/i^2]>[\sqrt[3]{n}]} i^2\left [\frac{n}{i^2}\right ]+\sum_{[n/i^2]\leq [\sqrt[3]{n}]} i^2\left [\frac{n}{i^2}\right ]=$$ $$=\sum_{i=1}^{\left [\sqrt{\frac{n}{[\sqrt[3]{n}]+1}}\right ]} i^2\left [\frac{n}{i^2}\right ]+\sum_{j=1}^{[\sqrt[3]{n}]} j \sum_{i=[\sqrt{n/(j+1)}]+1}^{[\sqrt{n/j}]} i^2,$$ while last sum can be computed effectively: $$\sum_{i=[\sqrt{n/(j+1)}]+1}^{[\sqrt{n/j}]} i^2=\sum_{i=1}^{[\sqrt{n/j}]} i^2-\sum_{i=1}^{[\sqrt{n/(j+1)}]} i^2=$$ $$=\frac{1}{6}\left (\left[ \sqrt{\frac{n}{j}}\right ]*\left (\left[ \sqrt{\frac{n}{j}} \right ] +1\right ) *\left (2\left[\sqrt{\frac{n}{j}}\right ] +1\right ) - \left[ \sqrt{\frac{n}{j+1}}\right ]*\left (\left[ \sqrt{\frac{n}{j+1}}\right ] +1\right ) *\left (2\left[ \sqrt{\frac{n}{j+1}}\right ] +1\right ) \right ).$$
• In particular, the second summand in your final expression actually covers all $i>\bigl\lfloor\sqrt{n/(\lfloor\sqrt[3]{n}\rfloor+1)}\bigr\rfloor$, and this bound may be strictly less than $\lfloor\sqrt[3]n\rfloor$. – Emil Jeřábek May 12 at 10:51