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

Solution 1:

One approach to improving the efficiency of calculating this would be to take $$\sum_{i=1}^{\infty}\left\lfloor\frac{N}{i^2}\right\rfloor$$ and ask how many times is the summand a $1$? How many times is it a $2$? And so on. Keep reading to the end, and this reduces the computation from $O(n^{1/2})$ time to $O(n^{1/3})$ time.

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

So the sum is the same as $$\sum_{i=1}^{\lfloor\sqrt{N/2}\rfloor}\left\lfloor\frac{N}{i^2}\right\rfloor+1\cdot\left(\left\lfloor\sqrt{N}\right\rfloor-\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor\right)$$

The original expression has $\lfloor\sqrt{N}\rfloor$ nonzero terms. Now it is written with $\lfloor\sqrt{N/2}\rfloor+2$ terms, which is an improvement if $N$ is at least $64$. You could continue like this, counting how many times $2$ appears in the original sum.

$\left\lfloor\frac{N}{i^2}\right\rfloor=2$ whenever $2\leq\frac{N}{i^2}<3$. So whenever $\sqrt{\frac{N}{2}}\geq i>\sqrt{\frac{N}{3}}$. There are $\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{3}}\right\rfloor$ such values of $i$.

So the sum is the same as $$\sum_{i=1}^{\lfloor\sqrt{N/3}\rfloor}\left\lfloor\frac{N}{i^2}\right\rfloor+1\cdot\left(\left\lfloor\sqrt{N}\right\rfloor-\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor\right)+2\cdot\left(\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor-\left\lfloor\sqrt{\frac{N}{3}}\right\rfloor\right)$$ $$=\sum_{i=1}^{\lfloor\sqrt{N/3}\rfloor}\left\lfloor\frac{N}{i^2}\right\rfloor+\left\lfloor\sqrt{N}\right\rfloor+\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor-2\left\lfloor\sqrt{\frac{N}{3}}\right\rfloor$$ Now there are $\lfloor\sqrt{N/3}\rfloor+3$ terms, which is an improvement over the previous version if $N$ is at least $72$. Keep going like this $M$ iterations, and the sum is equal to $$\sum_{i=1}^{\left\lfloor\sqrt{N/(M+1)}\right\rfloor}\left\lfloor\frac{N}{i^2}\right\rfloor+\sum_{j=1}^M\left\lfloor\sqrt{\frac{N}{j}}\right\rfloor-M\left\lfloor\sqrt{\frac{N}{M+1}}\right\rfloor$$ which is a sum with $\left\lfloor\sqrt{\frac{N}{M+1}}\right\rfloor+M+1$ terms, each of which has roughly the same computational complexity as the terms in the original sum. For a given $N$, there is an $M$ that minimizes this count of summands. If we ignore the floor function, calculus optimization leads us to $M\approx(N/4)^{1/3}$. And using that value for $M$, the number of terms in the summation is $\left(\sqrt[3]{2}+\frac{1}{\sqrt[3]{4}}\right)N^{1/3}$. That would be a noteworthy improvement over the original summand count of $\sqrt{N}$.