Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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. –  sonystarmap Jan 29 '13 at 13:07
add comment

1 Answer

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

Your Answer

 
discard

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.