hi, if a and p are relativly co-prime integers, then is there any efficient way of calculating the following:

$\displaystyle (\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

Printable View

- Nov 13th 2011, 12:27 PMpranayfinding the sum of series
hi, if a and p are relativly co-prime integers, then is there any efficient way of calculating the following:

$\displaystyle (\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, 09:46 PMCaptainBlackRe: finding the sum of series
Well the series is a geometric series so can be summed to:

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

so you question becomes one of evaluating

$\displaystyle \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 $\displaystyle N$ such that:

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

(which we can obtained by solving $\displaystyle \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