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
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
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