modulo of series summation
I have trouble with computing modulo.
First, I have a summation of series like this:
$$1+3^2+3^4+\cdots+3^n$$
And this is the formula which can be used to compute the series:
$$S=\frac{1-3^{n+2}}{1-3^2}=\frac{3^{n+2}-1}{8}$$
Then I want to compute $S \mod 1000000007$. But if $n$ is a large number, it's really hard for me to compute it. The only thing I know is $3^{n+2}-1$ divisible by 8 (n is an even number). Could anyone give me some good hint to solve this problem?
Update
My intention is computing $$M=\frac{3^{n+2}-1}{8} \mod 1000000007$$
For example: If $n=4000$ I must split $3^{4000+2}$ into $3^{40}3^{40}...3^{40}3^2$ and compute modulo for each part to improve speed like this:
$$(3^{40}\mod 1000000007)(3^{40}\mod 1000000007)...(3^{40}\mod 1000000007)3^2$$
But how can I compute M with the above idea.
Update more
It seems related to inverse modulo. I think the problem was solved like this
$$I=\frac{(1000000007+1)}{8}=125000001$$
$$\frac{3^{n+2}-1}{8} \mod 1000000007=(3^{n+2}I-I)\mod 1000000007$$
Is it right?
5 Answers
$\begingroup$The modulo value of a geometric sum
1 + a + a^2 + ... +a^n mod mcan be calculated based on the identity (if the highest exponent is odd)
1 + a + a^2 + ... +a^(2x+1) = (1 + a)(1 + a^2 + (a^2)^2 + ... + (a^2)^x)A complete algorithm which can deal with odd and even highest exponents looks like this in Mathematica:
geometricSeriesMod[a_, n_, m_] := Module[ {q = a, exp = n, factor = 1, sum = 0, temp}, While[And[exp > 0, q != 0], If[EvenQ[exp], temp = Mod[factor*PowerMod[q, exp, m], m]; sum = Mod[sum + temp, m]; exp--]; factor = Mod[Mod[1 + q, m]*factor, m]; q = Mod[q*q, m]; exp = Floor[ exp /2]; ]; Return [Mod[sum + factor, m]]
]Parameters:
ais the "ratio" of the series. It can be any integer (including zero and negative values).nis the highest exponent of the series. Allowed are integers >= 0.mis the integer modulus != 0
Note: The algorithm performs a Mod operation after every arithmetic operation. This is essential, if you transcribe this algorithm to a language with a limited word length for integers.
$\endgroup$ $\begingroup$Note that $n$ needs to be even for the formula to hold.
Hint for the first part: Let $S=1+3^2+3^4+...+3^n$. What is $3^2 \cdot S$? Can you find $S-3^2S$?
For the second part, do you know what $n$ is, or do you need a general formula? Are you familiar with the Euler Theorem?
$\endgroup$ $\begingroup$The modulo value of a geometric sum
1 + a + a^2 + ... +a^n mod m
for n=6;
(1 + a^2+ (a^2)^2) + a((1 + a^2+ (a^2)^2))
for n is odd
1 + a(1 + a + a^2 + ... +a^(n-1))
A complete algorithm which can deal with odd and even highest exponents looks with O(log(n))like this:
typedef long long ll;
ll bigSsum(ll a, ll b,ll m)
{ if(b==0) return 0; ll sum; if(b&1){ sum =bigSsum( (a%m * a%m)%m, ( b-1 )/2, m ); sum = ( sum + (( a%m )*( sum ) )%m )%m; sum = ( 1 + ( ( a%m )*sum )%m )%m; } else{ sum = bigSsum( (a%m * a%m)%m,b/2, m ); sum = ( sum + ( ( a%m )*( sum ) )%m )%m; } return sum%m;
}To calculate$$M=\frac{3^{4000+2}-1}{8} \mod 1000000007$$First find $$a = 8^{-1} \mod 1000000007 = 125000001$$and$$b = 3^{4002} \mod 1000000007 = 417856696$$then you have$$M=(b-1)*a \mod 1000000007 = 927232093$$Wikipedia has great articles on computing the modular inverse and Modular exponentiation . These methods take $O(log(m)^2)$ time and $O(log(n)^2)$ time to compute respectively, where you have used $m=1000000007$ and $n=4000$. In Mathematica, these methods are already built in and you can find the answer with:
Mod[(PowerMod[3, 4000 + 2, 1000000007] - 1)*ModularInverse[8,1000000007], 1000000007]You can use the property of modulus,i.e., $$(a+b)\%m = (a\%m+b\%m)\%m$$
So to calculate $$S=1+3+3^2+3^3+...$$
you can use
$$S\%M = (1\%M + 3\%M +3^2\%M +......)\%M$$
This will speed the process and even save you from integer overflow.
$\endgroup$
