トランプのシャッフルは何回で元に戻る？
トランプのシャッフルの中でもよく使われるリフルシャッフルですが、これを完全に1枚ずつ交互に混ぜる方法をパーフェクトシャッフルと呼ぶようです。これを繰り返すと何回のシャッフルで元に戻るかは色々紹介されていますが、簡単にまとめると、
上からk番目(一番上を0とする)のカードが\\
シャッフルでf(k)番目に移るとすると\\
\begin{equation}
f(k)= \left \{
\begin{array}{l}
2k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (上半分) \\
2k-(N-1) (下半分)
\end{array}
\right.
\end{equation}
両辺の\mod{(N-1)}を取ると場合分けがなくなって、\\ \\
\\
f(k) \equiv 2k \pmod{(N-1)}\\
これをs回繰り返す関数をf^s(k)とすると\\
f^s(k) \equiv 2^sk \pmod{(N-1)} \\
よってs回シャッフルで元に戻る条件は \\
\large 2^s \equiv 1 \pmod{(N-1)} \ \cdots (1) \\
を満たす最小のsが求める数となります。
元に戻る回数と位数の関係
式(1)を見てピンと来た方もいると思いますが。これはまさに 「法(N-1)における２の位数」 の定義になります。参考のために「位数の性質と原始根の応用」から位数の定義を引用します。
\cdot \ a^n \equiv 1 \pmod p となる最小の正の整数nを法pにおけるaの位数と呼びます。
sympyのn_orderで位数を求める
位数の求め方は色々あると思いますが、sympyには既にn_orderという関数がありますので、これを使ってN=52の時の位数が8なので、 8回 で元に戻ることが分かると思います。
from sympy import n_order
print(n_order(2, 52-1))
# 8
同様にN＝2~52の偶数に対して位数を求めてみました。8回で元に戻るのは他にN=18の場合があるのが分かります。次なる疑問として他にはないのかというのが気になります。
from sympy import n_order
print([n_order(2,(n-1)) for n in range(2,52+1,2)])
# [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8]
8回で元に戻る枚数をすべて求める
ループの上限を増やせば分かりそうですが、闇雲にチェックするのは効率的ではありません。そこで式(1)を以下のように変形します。
2^s - 1 \equiv 0 \pmod{(N-1)} \ \\
(2^s - 1)が(N-1)で割り切れるので\\
(N-1)は(2^s - 1)の約数となる
$(2^s - 1)$の約数に対して2の位数をチェックすれは良いことになります。
from sympy import divisors,n_order
s = 8
for d in divisors(2**s-1):
print(d, n_order(2,d),d+1)
#1 1 2
#3 2 4
#5 4 6
#15 4 16
#17 8 18
#51 8 52
#85 8 86
#255 8 256
2の位数が8になるのはN=18, 52, 86, 256の時でこれらがすべてであることが分かりました。
（開発環境：Google Colab）
この考え方はProject Euler, Problem 622:Riffle Shufflesを解くのに役に立ちます。