# finding the sum of series

• Nov 13th 2011, 01:27 PM
pranay
finding the sum of series
hi, if a and p are relativly co-prime integers, then is there any efficient way of calculating the following:
$(\sum_{k=0}^n\frac{1}{a^k}) \% p$ ? here n and p can be as large as: 0 ≤ N ≤ 2147483647, 2 ≤ P ≤ 2147483647 thanks
• Nov 20th 2011, 10:46 PM
CaptainBlack
Re: finding the sum of series
Quote:

Originally Posted by pranay
hi, if a and p are relativly co-prime integers, then is there any efficient way of calculating the following:
$(\sum_{k=0}^n\frac{1}{a^k}) \% p$ ? here n and p can be as large as: 0 ≤ N ≤ 2147483647, 2 ≤ P ≤ 2147483647 thanks

Well the series is a geometric series so can be summed to:

$\sum_{k=0}^n a^{-k}=\frac{1-a^{-(n+1)}}{1-a^{-1}}$

so you question becomes one of evaluating

$\frac{1-a^{-(n+1)}}{1-a^{-1}} \text{ mod } p$

efficiently.

It might be productive to split the sum up into blocks (which can be summed explicitly using the geometric series formula) and computing the remainder on the blocks before combining the blocks and doing the grand remainder.

We could consider a block size $N$ such that:

$\frac{1-a^{-(N+1)}}{1-a^{-1}} > p$

(which we can obtained by solving $\frac{1-a^{-(x+1)}}{1-a^{-1}}=p$ numerically)

This thread is not really number theory (the remainders are fractional not integer) this is more like numerical analysis or mathematical software, so I am moving this to the "other advanced topics" area of MHF.

CB