# Recursive relation, how to calculate the period of repeating pattern

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

-
From a programming point of view or analytically? For programming you could simply check whether a resulting number already occured and the distance to the iteration where it occured would be the period. – k1next Jan 29 '13 at 13:07

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.
Then note that $\frac{b^{n + 1} - 1}{b - 1} = 1 + b + b^2 + \cdots + b^n$, and if $\gcd(q, b - 1) = 1$ this is 0 only when $b^{n + 1} - 1 = 0 \pmod{q}$, so you are interested in the order of $b$ modulo $q$. – vonbrand Jan 30 '13 at 17:20