フィボナッチ数列は法nで周期的

　フィボナッチ数列は法nで周期的である。
例えば、フィボナッチ数の下1桁を表示すると

0 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 ....

のように周期60の数値が並ぶ。これはフィボナッチ数列が法10で周期的であることを意味している。同様に、他のnに対してもフィボナッチ数列は法nで周期的となる。

この理由について考えてみた。

まず、mod nの要素はn個しかない。よって、フィボナッチ数列の隣合う数(f_n, f_n+1)をmod n で考えると、pigeon hole principleにより、n*n+1回目以内に既出の点に戻ることになる。よって、f_n mod nは最終的にcycleに入る。

ここまでは簡単。
問題はただcycleに入るだけじゃなくて、(f_0, f_1) mod nに戻ってくるというのをどのように示せばよいかだ。

分からなかったので、ググってみると以下のような証明が見つかった。

Proof that Fibonacci Sequence modulo m is periodic?

なるほど。

途中からサイクルに入るような列をpreperiodic（前周期的）というらしい。

一般に、有限サイズの集合Sに対して、f: S → Sを定義すると、Sの要素に対して、fを繰り返し適用してえられる列はpreperiodicになる。
つまり、あるtが存在して、十分大きなnに対して、f(n + t) = f(n)が成り立つ。

ここで、fがbijectiveな場合は、上式の両辺にf^-1を繰り返し適用すると、いずれf(t) = f(0)となるので、(strictly) periodicになる。
フィボナッチ数列の式f(a, b) = (b, a+b)はbijectiveなので、(strictly) periodicということらしい。

フィボナッチ数列だけじゃなくて、bijectiveな関数なら何でもいいらしい。

ということで、ちょっと実験してみる。
mod 10でf(x) = ax+7を考えてみる。gcd(a, 10) = 1のときは、逆関数f^-1(x) = a^-1 (x-7)が存在するので、(strictly)periodicになることを確認する。
ついでに、開始点を0にすることで、gcd(a, 10) > 1のときは0に戻ってこないことを確認する。（∵ gcd(a, 10) > 0のときは0はfのimageには含まれないため。）

def gen(a, mod):                                                                
    x = 0                                                                       
    while True:                                                                 
        yield x                                                                 
        x = (a * x + 7) % mod                                                   
                                                                                
mod = 10                                                                        
for a in range(mod):                                                            
    print "a = %d:" % a,                                                        
    g = gen(a, mod)                                                             
    for _ in range(mod + 2):                                                    
        print g.next(),                                                         
    print

以下実行結果。

a = 0: 0 7 7 7 7 7 7 7 7 7 7 7                                                
a = 1: 0 7 4 1 8 5 2 9 6 3 0 7                                                
a = 2: 0 7 1 9 5 7 1 9 5 7 1 9                                                
a = 3: 0 7 8 1 0 7 8 1 0 7 8 1                                                
a = 4: 0 7 5 7 5 7 5 7 5 7 5 7                                                
a = 5: 0 7 2 7 2 7 2 7 2 7 2 7                                                
a = 6: 0 7 9 1 3 5 7 9 1 3 5 7                                                
a = 7: 0 7 6 9 0 7 6 9 0 7 6 9                                                
a = 8: 0 7 3 1 5 7 3 1 5 7 3 1                                                
a = 9: 0 7 0 7 0 7 0 7 0 7 0 7

予想通りになってた。