3
$\begingroup$

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.

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

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 ).$$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ As noted in comments to your first deleted answer, there are some off-by-one errors. $\endgroup$ – Emil Jeřábek May 12 at 10:38
  • 2
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek May 12 at 10:51
  • 2
    $\begingroup$ Ok, now I corrected it but idea is still the same. $\endgroup$ – Pavel Kozlov May 13 at 10:57
  • 2
    $\begingroup$ All right. Speaking of ideas, I seem to remember that the idea is not yours, but comes from someone else’s comment (the comment thread below the question was deleted by mod when it transpired it was part of an ongoing contest). If so, you should give credit properly. $\endgroup$ – Emil Jeřábek May 13 at 11:45

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.