Polar_'s blog

How to calculate summation 1/(n^2) with modulo prime number .
By Polar_, history, 5 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

»
5 years ago, # |
← 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
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please elaborate ?
    Try this n = 5 and mod = 7 . I think the answer will be 6 .

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your $$$S$$$ isn't an integer, but a real number. Your formula gives a real number as the result, not an integer.

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

      Yeah Xellos You are right .

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if n = 5, and mod = 7 then

      S = 1 / 1 + 1 / 4 + 1 / 9 + 1 / 16 + 1 /25 % 7

      But why the result is 6 ? How to calculate the modulo of real number, I thought module result something left when remove the biggest number smaller than N and divides MOD

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Oh I found the blog talk about real number modulo

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can't define modulo for a general real number except perhaps as "subtract/add mod until you get a number in [0, mod)", which isn't an integer. You can make some sort of definition in special cases, e.g. $$$\sqrt{x} \equiv y$$$ if $$$y^2 = x$$$ modulo $$$mod$$$, but this has its own problem, most importantly non-uniqueness, which makes it much more impractical as a hash to check correctness in a contest. Multiplicative inverse has no such problems, coprimality guarantees nice properties.

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

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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← 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
»
5 years ago, # |
  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
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you compute an irrational number modulo a prime? I think he means $$$\sum_{n=1}^N \frac{1}{n^2}$$$, that's a rational number.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. You can
      2. It was a joke about the poor problem statement.
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I considered the possibility that it was a joke, but I wasn't sure...

        → Reply
»
5 years ago, # |
  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
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks .

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i didnt get it exactly. can you please explain it bit more or give any link where i could study this topic?

    → Reply
»
5 years ago, # |
← 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