Given only a large integer upto $ 10^{18} $ , what can be an efficient way to calculate $$ \sum_{k=1}^{\left \lfloor \sqrt{N} \right \rfloor} \left ( N \ mod \ k^{2} \right ) $$ Note that for a local machine, computation can go upto $ 10^{6} $ iterations.
Asked
Active
Viewed 317 times
-2
Mauro ALLEGRANZA
- 94,169
Mukul Bindal
- 115
-
Possibly useful: (Question 1629608). – Jam Apr 10 '20 at 16:16
-
N is upto $10^{18}$. So this solution https://math.stackexchange.com/questions/1629608/calculating-the-summation-of-n-bmod-i works in $O \left ( 10^{9} \right )$ which is too large for a local machine. – Mukul Bindal Apr 10 '20 at 16:32
-
The sequence has OEIS entry A072516 but unfortunately no other formulae are listed. – Jam Apr 10 '20 at 16:38
1 Answers
3
It might be worth rewriting the sum with the modulo as the floor of integer division, $\displaystyle N\lfloor\sqrt{N}\rfloor-\sum_{k=1}^{\lfloor\sqrt{N}\rfloor}k^{2}\left\lfloor\frac{N}{k^{2}}\right\rfloor$. You could then attempt to partition the sum into subsets of $k$ such that $\displaystyle\left\lfloor\frac{N}{k^{2}}\right\rfloor$ is a certain integer, $1,2,3,\ldots$, and then sum those simpler sums individually. User alex.jordan has described a similar method in (Question 3618219).
Jam
- 10,325
-
But that sum has a closed-form. and this has some precision loss issue and no closed form. – Rishabh Deep Singh Apr 11 '20 at 12:18
-
1@RishabhDeepSingh I am not claiming there is a closed form for the sum and I don't believe there is one. The method I have referenced gives a potential way to reduce the number of terms in the sum by simplifying terms with the same value of $\left\lfloor\frac{N}{k^2}\right\rfloor$ and so, potentially reducing the complexity of the calculation. Also, there should be no loss of precision with the rearrangement; it is an equivalence and all terms are integers. – Jam Apr 11 '20 at 13:23
-
The precision i was talking about in the value of $m = \sqrt[3]{n/4}$ and $k=\sqrt{\frac{n}{m+ 1}}$ – Rishabh Deep Singh Apr 11 '20 at 13:32
-
1@RishabhDeepSingh I'm not really sure what you mean. We should be able to calculate the terms $M$ and $\left\lfloor\sqrt{\frac{N}{M+1}}\right\rfloor$ exactly since they are integers. We don't need to know the fractional part of $\sqrt{\frac{N}{M+1}}$ since it gets truncated by the floor. – Jam Apr 11 '20 at 14:17
-
for smaller numbers cant there is some error in the calculation of the $\lfloor \sqrt{\frac{n}{m+1}} \rfloor$ – Rishabh Deep Singh Apr 11 '20 at 19:01
-
@Jam can you please tell where the term $k^2$ in the product will go in the referenced solution. I can't understand how we are going to partition the sum along with the variable $k^2$. – Amaan Iqbal Apr 12 '20 at 18:38
-
@AmaanIqbal I hadn't gone through the entire method or written it up into a code yet so there may be some snag I've not seen yet (my answer was intended as a possible suggestion). But the $k^2$ shouldn't be hard to deal with since when $\left\lfloor\frac{N}{k^2}\right\rfloor$ is held constant, $\displaystyle \sum_{a}^b k^2=\sum_{0}^b k^2-\sum_{0}^{a-1} k^2$ becomes a difference of geometric series and can be given a closed form. – Jam Apr 12 '20 at 18:45
-
@Jam Thanks for the response! Just one doubt, how do we decide the range
atobhere? – Amaan Iqbal Apr 12 '20 at 19:11 -
-
@AmaanIqbal Yes. I was using them as a placeholder to refer to any such subsequence of $k$. – Jam Apr 12 '20 at 19:25
-
@AmaanIqbal No problem. Out of interest, a lot of people seem to be asking about problems of the form $\sum \lfloor x\rfloor$. Has it appeared in an exam recently or something? – Jam Apr 12 '20 at 19:29
-
1Actually, it's just a small part of a complex problem for a coding contest. You can find the actual question over https://www.codechef.com/APRIL20A/problems/PPDIV – Amaan Iqbal Apr 12 '20 at 19:33