The qualification round of the Facebook Hacker Cup was held last weekend, and in the last problem you had to calculate the values of a vector according to this recursive relation (for some given values of a, b, c and r):
$m(0) = a\\ m(i) = (b \cdot m(i - 1) + c) \bmod r$
After programming a trivial solution for the problem I could see there was a pattern. For instance, for this test case:
a: 6, b: 30, c: 524, r: 98
The vector was:
[[18, 84, 6, 18, 84, 6, 18, 84, 6,...
How can I calculate the period of the pattern? (Do not worry, the qualif. round ended and this won't give me additional points or anything, it's just out of curiosity ;)
Notice that $\displaystyle m(n) = \left( b^n a + c\sum_{j=0}^{n-1}{b^j}\right) \mod r$. If $a$ occurs again as $m(n)$, then $$ b^n a + c\sum_{j=0}^{n-1}{b^j} \equiv a \mod r $$ $$ (ab+c-a)\sum_{j=0}^{n-1}{b^j} \equiv 0 \mod r $$
Let $q = r/gcd(r,ab+c-a)$. Then you need $\displaystyle \sum_{j=0}^{n-1}{b^j} \equiv 0 \mod q$. So, if you look at the sequence $1,1+b,1+b+b^2,\ldots$ modulo $r$, the period is given by the period in this sequence. The repetition need not always start with the first element.