Polar_'s blog

How to calculate summation 1/(n^2) with modulo prime number .
By Polar_, history, 6 years ago, In English

Hi! I need help in calculating $$$\sum\frac{1}{n^2}\%MOD$$$.
Where $$$MOD$$$ is a prime number .
I know that taking of inverse modulo for every $$$k^2$$$ where $$$ 1 \le k \le n $$$ then adding them up and taking modulo.
But if $$$n$$$ is order of $$$10^9$$$ then how to do it ?
Any faster way to do it ?
Thanks .

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, hide # |
← Rev. 3  
Vote: I like it -18 Vote: I do not like it

[Wrong approach]

If I dont understand wrong. just calculate S = the total sum of 1 / k^2 for every 1 ≤ k ≤ n in O(sqrt(n))

Then the result will be S % MOD = S — floor(S / MOD) * MOD

→ Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How large can $$$MOD$$$ be?

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    I wrote a brute-force solution and printed out the result (($$$1 / i^2$$$)%$$$MOD$$$) for each $$$i$$$ until $$$n$$$ and found out that the values are cyclically repeated with cycle length equal to $$$MOD$$$. So if you calculate just one cycle and store it in an array you can get the final result easily.

    Please correct me if I am wrong.

    → Reply
»
6 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it
The answer is

Seriously, maybe this sum can be simplified if you express its summands as degrees of some primitive root.

→ Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Here's an idea: the sum for even $$$n$$$ is $$$\frac{1}{4}\sum_{n=1}^{N/2} \frac{1}{n^2}$$$, the rest is the sum for odd $$$n$$$. This way, you can split the sum based on the smallest few primes in the decomposition of $$$n$$$ in the summands. There aren't that many primes below $$$10^9$$$ and small enough sums can be precomputed, so this could give a decent runtime.

Also note that $$$(ab)^{-1} = a^{-1} \cdot b^{-1}$$$, which saves a lot of time spent on computing modular inverses.

→ Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +11 Vote: I do not like it

You can precompute each sum with step $$$10^6$$$. On ideone for range $$$10^7$$$ runtime is $$$1.32$$$ seconds, then for $$$10^9$$$ runtime is $$$132$$$ seconds (two minutes). Now you know each sum with step $$$10^6$$$ and can copy-paste array into code. So, you can find any required sum with precalculated values by addition at most $$$10^6$$$ terms.

→ Reply