ハノイの搭を4本にしたら



ハノイの搭は再帰的プログラムの例として有名であり、 n枚の円盤を他の搭に移すのに2^n-1回の移動が必要です。
本来のハノイの搭は3本ですが、 4本以上にすると移動回数が下の表のように非常に面白い数列^*になります。

円盤の枚数	1	2	3	4	5	6	7	8	9	10	11	12
3本のときの移動回数	1	3	7	15	31	63	127	255	511	1023	2047	4095
4本のときの移動回数	1	3	5	9	13	17	25	33	41	49	65	81
5本のときの移動回数	1	3	5	7	11	15	19	23	27	31	39	47
6本のときの移動回数	1	3	5	7	9	13	17	21	25	29	33	37

下の移動開始ボタンを押せば, 最小回数での移動の仕方を表示します。
円盤 枚, 塔 本の初期状態を , 注 : 塔が 3 本で円盤の枚数が多いと時間がかかります(7枚で約 2分)。

* 階差数列は2の冪が並んだものになります。
塔が t本のときの階差数列の中の 2ⁿ の個数を a(t, n) とすると
a(3, n) = 1, a(t, 1) = t-2 であり,
t > 3, n > 1 のときは a(t, n) = a(t, n-1) + a(t-1, n) となります。