リフルシャッフルで元に戻る回数

「52枚のトランプに対して正確なリフルシャッフルをすると8回で元に戻る」——どこかで聞いたことがあるようなフレーズです。私は昔何かのテレビ番組で見たような記憶があります。

リフルシャッフルとは、カードを2山に分けてパラパラと1枚ずつ交互に重ねていくシャッフル方法です。マジシャンとかがやると非常にかっこよく見えるシャッフル方法ですが、私はうまくできません。2枚以上のダマが入り込んでしまいます。

実はこれ、「シャッフル」と名が付いていますが全然混ざっていないんですよね。正確なリフルシャッフルは元のカード束に対して一意の結果が出てくるのはもちろんのこと、同じ側から2枚以上連続して入ってしまう下手なリフルシャッフルでも最悪ケースで並び順は$2^{N-1}$通りしかありません。完全にランダムなシャッフルの場合は$N!$通りですからリフルシャッフルのほうがはるかに混ざっていません。52枚のトランプを想定すると、リフルシャッフルでは$2.25\times10^{15}$通り、完全にランダムなシャッフルでは$8.07\times10^{67}$通りですから一目瞭然ですね。
ですので、リフルシャッフルを利用するマジックは、たいていこの「実はよく混ざっていない」を使っているんですね。Norman L. Gilbreathがギルブレスの原理として数学的に体系化しているらしいです。観客に対して混ざったと思わせるには十分大きいパターンがありますが、マジックにするには十分の混ざらなさ具合というわけですね。

さて、話を戻します。52枚のトランプでは8回正確なリフルシャッフルをすると元の配列に戻ります。これを証明していきます。

$0,1,2,3,...,24,25,26,27,28,...,50,51$の番号が付いたカードがこの順に並んでいるとします。これを1回正確なリフルシャッフルをすると、それぞれのカードは$0,2,4,8,...,48,50,1,3,5,...,49,51$番目へ移動します。カードの番号がこの順に並び変わるのではなく、それぞれのカードが何番目へ移動するかを表した数列ですので注意してください。
これは、最後の51番目のカードを除いて、$k$番目なら$2k$を51で割った番目へ遷移していることがわかります。これを$R(k)$と表すとすると、\[R(k)\equiv2k\pmod{51}\]と書けます。
さらに、2回正確なリフルシャッフルをすると$R(R(k))$へ遷移することになりますので、これを$R^2(k)$と表すとすると$R^n(k)$が定義できます。\[R^n(k)=R(R^{n-1}(k))\equiv 2R^{n-1}(k)\pmod{51}\]と書けますので、再帰的に適用すれば\[R^n(k)\equiv 2^nk\pmod{51}\]となります。非常にシンプルな式ですね。
カードの配列が元に戻ると言うことは、$0\leqq k<51$の全ての整数$k$に対して\[k\equiv 2^nk\pmod{51}\]が成立するということになります。もうちょっとわかりやすく式変形すれば\[2^n-1\equiv 0\pmod{51}\]になります。
ちなみに、一番下の51番目のカードを除いて計算してきましたが、一番下のカードは毎回一番下から動かないので、考慮に入れなくても何も問題はありません。
この式が成立する最小の$n$は8ですね（$2^8-1=255$で$255\div51=5$ですね）。

さて、証明できましためでたしめでたし。
ただ、これだけだとプログラミング関係のブログというテーマに反してしまいますので、無理やりにでもプログラミング要素を入れていきます。

52枚のトランプだけでなく、$2m$枚のカード束について考えていきます。
52枚でしたので$\bmod{51}$でしたが、$2m$枚なら$\bmod{2m-1}$にすればいいだけですね。

static int ReturnToOriginalCount(int CardCount)
{
    if(CardCount <= 0) throw new ArgumentOutOfRangeException(nameof(CardCount));
    if((CardCount & 1) != 0) throw new ArgumentException($"{nameof(CardCount)} must be even.");

    BigInteger exp = 1;
    int i = 0;
    do {
        exp <<= 1;
        i++;
    } while((exp - 1) % (CardCount - 1) != 0);

    return i;
}

これでカード枚数から何回で元に戻るかの関数が完成です。ちなみに2のべき乗はシフト演算で実現しています。これを使って100枚以下の枚数のカード束で何回で元に戻るかを計算するとこうなります。

N [枚]	k [回]
2	1
4	2
6	4
8	3
10	6
12	10
14	12
16	4
18	8
20	18
22	6
24	11
26	20
28	18
30	28
32	5
34	10
36	12
38	36
40	12
42	20
44	14
46	12
48	23
50	21
52	8
54	52
56	20
58	18
60	58
62	60
64	6
66	12
68	66
70	22
72	35
74	9
76	20
78	30
80	39
82	54
84	82
86	8
88	28
90	11
92	12
94	10
96	36
98	48
100	30

52枚は周辺の枚数に比べて突出して少ないですね。トランプの52枚というのはなかなか神秘的な枚数です。ちなみにジョーカーを含めて54枚とすると52回も正確なリフルシャッフルをしなければ元に戻りません。
ちなみに元の式を見てもらえばわかりますが、$2^n$枚のカードのときは$n$回で元に戻ります。これも突出して周囲より低い回数で元に戻る枚数ですね。

せっかくなので、ついでにk/Nも計算してみます。数学的な意味はともかく、「枚数の割には早い回数で元の並びに戻る枚数」と考えることができます。
3万枚以下でk/Nが小さい順に並べると、トップ10は次のようになります。

N [枚]	k [回]	k/N
29128	18	0.000617962
21846	16	0.0007324
25576	20	0.000781983
28680	24	0.00083682
28198	24	0.000851124
16384	14	0.000854492
25306	24	0.000948392
27306	28	0.001025416
23206	24	0.001034215
19066	20	0.001048988

この中で$2^n$枚なのは16384枚だけですね。29128枚もあるカードでも、18回正確なリフルシャッフルをするだけで元に戻ってしまうんですね。
誰かやってみてください…。