Calculating number of terms that should be added to get the required sum in series

Question

I have a geometric progression like series:

S = x1 + x2 + .....    xn (mod m)
where xi = (x(i-1))*r (mod m) for i>1 and x1=1  , 2<=m<10^9, 1<=r<m, 1<=S<m, 1<=n<p

here m is a prime number and r,m,S are known.

Property of r : If we form a set of r (mod m), r^2 (mod m), ..., r^(m-1) (mod m) then it will contain all the numbers form 1 to m-1.

I want to find the the value of n (if possible). I cannot apply the Geometric Progression (GP) formula here so I made an alternate algorithm making an assumption that these powers will make a cycle of length much smaller than n-1. I thought to find a pattern such that the series repeats itself but this pattern of cycle occurs only for some r's so I failed to do so. Of course, naive approach of setting a loop till m wont work because it's too large and hence took a large amount of time before terminating.

I found a similar problem here. But in this link there is no property on r to make the algorithm faster. I applied all the answers given here to my code but none is reducing its complexity as required.

I know that somehow I have to use property of r to make an efficient algorithm but I don't know how.

So is there any other pattern we can find out or any use of this property we can make to get the most efficient algorithm? (Basically I don't want to iterate over m.) So please give me an idea of an efficient algorithm to find the n.

You wrote: `r,r^2,....r^(n-1) then it will contain all the numbers [from] 1 to m-1`. Do you mean `r (mod m), r^2 (mod m), ..., r^(n-1) (mod m)`? — ljeabmreosn, Jun 17 '17 at 23:37
@ljeabmreosn Yes! I updated that so others don't have this doubt! :) PS: And it is `m` not `n` in the power. — Daemon, Jun 17 '17 at 23:42
Also, doesn't `xi = (x(i-1))*r (mod m) for i>1 and x1=1` imply that `S = 1 + r + r^2 + r^3 + ... + r^n (mod m)`? — ljeabmreosn, Jun 17 '17 at 23:56
Can we chat somewhere so i can show you pics? If `a1 + (a1*r)%m + ((a1*r)%m*r)%m + ... .` In this if I take the 3rd term....then you can write `((a1%m)*(r%m))%m * (r%p))%m = (a*r^2)%m...`So `a1 + (a1*r)%m + (a1*r^2)%m.. a1*r^(n-1)%m....` = > Your output till `r^(m-1)` though.....then you can replace them with sum of `1 to m-1`.I thought that and find the sum but still it was terminating before the required and showing wrong in some test cases. Can we talk at facebook or gmail?? — Daemon, Jun 18 '17 at 00:11
I can't because I must have 20 reputation to chat there.I am new to stackoverflow. — Daemon, Jun 18 '17 at 00:22
Ongoing contest's question. [**LINK**](https://www.hackerearth.com/challenge/competitive/june-circuits-17/algorithm/dexter-plays-with-gp-1/) — Sanket Makani, Jun 18 '17 at 07:05

ljeabmreosn · Accepted Answer · 2017-06-18T16:31:43.250

I believe I have found a solution. Note that r is a primitive root modulo m by the property of r given.

Consider the geometric sum S = 1 + r + r^2 + ... + r^n. Then we write S in the closed form as S = (r^n - 1) / (r - 1).

Well, we want to solve this equation modulo m for n as we are already given S and r. So we need to solve:

   (r^n - 1) / (r - 1) = S (mod m)
=> r^n - 1 = S * (r - 1) (mod m)
=> r^n = S * (r - 1) + 1 (mod m)

We have now run into the Discrete Logarithm Problem.

Using the Baby-step Giant-step algorithm, we can solve this in O(sqrt(m)) which is doable if m is at most 10^9. Below is my implementation in Python 3 where answer(r, m, S) gives the desired answer:

from math import sqrt, ceil

def invmod(r, p):
    """
    solves x = r^(-1) modulo p
    Note: p must be prime
    """
    return pow(r, p-2, p)


def discrete_log(a, r, p):
    """
    solves r^x = a (mod m) for x
    using the baby-step giant-step algorithm:
    https://math.berkeley.edu/~sagrawal/su14_math55/notes_shank.pdf
    Note: r must be a primitive root modulo p
    """


    m = int(ceil(sqrt(p)))

    # compute 1, r, r^2, ..., r^(m-1) modulo p
    pows = {pow(r, mp, p): mp for mp in range(m)}

    # compute r^(-m) modulo p
    y = pow(invmod(r, p), m, p)

    # compute a, ay, ay^2, ..., until we find a number
    # already in pows
    for q in range(m):
        z = (a * pow(y, q, p)) % p
        if z in pows:
            return pows[z] + (q * m)

    raise Exception("discrete logarithm not found")


def answer(r, p, S):
    """
    if S = 1 + r + r^2 + ... + r^n (mod p),
    then answer(r, p, S) = n
    """
    a = (S * (r-1) + 1) % p
    return discrete_log(a , r, p)

Calculating number of terms that should be added to get the required sum in series

1 Answers1