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

I have tried to find a closed form but did not succeed but is there an efficient way to calculate the following expression

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

So Far I have noticed the following

$$\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}{i^{2}} \right \rfloor = \sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N-N \mod i^{2}}{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}$$

I want to solve it in either log(N) or as a closed form

• Note that the upper limit of summation can go higher, since after $i=\lfloor\sqrt{N}\rfloor$, the summands will be $0$. Then this is the same as OEIS A013936, which allows the upper limit to go all the way to $N$. There are some results there, but no explicit formula. The terms are very close to OEIS A145353. Commented Apr 10, 2020 at 1:51
• I tried finding to come to a from the links, but I wasn't able to come up with anything. Do you think that i have to calculate (Expression) mod 1000000007 changes anything and helps to get a more computationally feasible solution? Commented Apr 10, 2020 at 2:09
• Third question about this sum, or something very like it, today. Is there a run on floor functions? Commented Apr 10, 2020 at 3:26
• Your summation is bounded between $\frac{\pi^2}{6} N-\sqrt{n} \leq Y_S \leq \frac{\pi^2}{6} N - 2 \sqrt{N}$ for all $N \geq 10$, for sure one can reduce $-2\sqrt{N}$ the constant may be less than $2$ but bigger than $1.60772$
– user411780
Commented Apr 10, 2020 at 17:03
• I'm guessing that it's a competition problem. More of it are incoming. Will try to link to this. Commented Apr 11, 2020 at 20:35

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