sum of GP mod M

general
, , ,
1

Can anyone help me with the below question, I am a beginner in programming and I can’t find the solution for this problem

So basically we need to find (1 + A^1 +A^2 + A^3 + A^4 + -------+ A^N) % M

1 < = A,N,M <= 10^(19)

Let’s take an example A=3 N = 2 , M = 5;

so 1+3+3^2 = 1+3+9 = 13%5 = 3 .

Please help!!!

1 Like
2

This is more of a mathematics issue than a programming one, when N gets large. Here are the tools:

(1 + A^1 +A^2 + A^3 + A^4 + \cdots + A^N) = \frac{A^{N+1}-1}{A-1}

For prime M, the modular inverse of A{-}1 can be found from b^{M-1} \equiv 1 \bmod M, giving b\cdot b^{M-2} \equiv 1 \bmod M and thus b^{-1} \equiv b^{M-2} \bmod M. Quicker, more general purpose but harder to explain is theextended Euclidean algorithm.

Exponentiation by squaring is relatively quick if you don’t have a built-in power-to-mod function.

So in your small-number example, I’ll show the first two:

1+3+3^2 = \frac{3^3-1}{3-1} = (3^3-1)(3-1)^{-1}

(3-1)^{-1} \equiv (3-1)^{(5-2)} \equiv 8 \equiv 3 \bmod 5

(3^3-1)(3-1)^{-1} \equiv 26\cdot 3 \equiv 1\cdot 3 \equiv 3 \bmod 5

1 Like
3

You can use the formula for geometric sum if the modular multiplicative inverse of the denominator of the geometric sum exists. Refer to @joffan 's answer.

Otherwise, you can solve this recursively. Note that:

1 + a + a^2 + a^3 + \dots + a^{2n+1} = (1 + a)(1 + (a^2) + (a^2)^2 + (a^2)^3 + \dots + (a^2)^n)

If we denote 1 + a + a^2 + a^3 + \dots + a^n as S(a,\ n), then

S(a, 2n + 1) = (1 + a) \cdot S(a^2, n)
S(a, 2n) = 1 + a \cdot (1 + a) \cdot S(a^2, n-1)

with base cases:

S(a, 0) = 1
S(a, 1) = 1 + a

Since at each step we are reducing the number of terms to half, the complexity is \mathcal{O}(\log{n}).

You just have to store the answer modulo M at every step.

Here is the Python


[1].


  [1]: https://ideone.com/gWBvJl
9 Likes
4

You could use lucas theorem in that case

5

That’s a good solution also, for cases where (A-1) has no modular inverse. However even for non-prime M, whenever M and (A-1) have no common factors, the modular inverse does exist. In that case you can use the extended Euclidean algorithm to find the modular inverse of (A-1) \bmod M - and that algorithm can also tell you whether the inverse exists.

3 Likes
6

@c_utkarsh isn’t the recurrence be S(a,2n+1) = (1+a)S(aa,n)… Please correct me If I am wrong

2 Likes
7

@joffan @beginner_1111 you both are correct. I’ve updated my answer accordingly.

1 Like
8

@ssrivastava990
@anon55659401

Will matrix exponentiation work?

9

@c_utkarsh how did you derive this line S(a,2n)=1+a⋅(1+a)⋅S(a2,n−1) S(a, 2n) = 1 + a(1 + a) S(a^2, n-1) S(a,2n)=1+a⋅(1+a)⋅S(a2,n−1)