Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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
This is essentially how linear congruential random number generators work, and the definitive study of those is in Knuth's "The Art of Computer Programming", volume 2. – vonbrand Jan 30 '13 at 17:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.