ヨセフス数（Josephus Number）の求め方

ヨセフスの問題（Josephus problem）という有名問題があります。これの一般解を求める式があるらしいので調べてみました。

　以下では、円を組む人の数をn、スキップ数をkとします。本来は、n番目（つまり最後に）処刑される人の番号を求めればよいのですが、より汎用的にs番目に処刑される人の位置を求めることにします。

　ここのページにあるように、以下のソースコードでs番目に処刑される人の位置がわかります。

int josephus(int n, int k, int s) {
    int ret = k * s;

    while (ret > n)
        ret = ((ret - n) * k - 1) / (k - 1);

    return ret;
}

　えーーっと、よくわかりません。ということで、何故上のコードで答えがでるのか考えてみました。（結構がんばりました（汗）。）

まずは、正の整数xに対して、f_k: x -> (x * k - 1) / (k - 1)という写像が何をするのか考えます。

k = 2のとき

f_2(1) = 1

f_2(2) = 3

f_2(3) = 5

f_2(4) = 7

・・・・・

k = 3のとき

f_3(1) = 1

f_3(2) = 2

f_3(3) = 4

f_3(4) = 5

f_3(5) = 7

・・・・・

ふーむ、どうやらf_kは、自然数からなる点列(1,2,3,...)からkの倍数を取り除くような効果があるようです。本当か？ちょっと数学的に考えてみます。

f_k(x) = (k * x - 1) / (k - 1)なので、f_k(1) = (k*1 - 1) / (k - 1) = 1です。

f_k(2) = (k*2 - 1) / (k - 1) はコンピュータの整数演算では2ですが、数学上は、2余り1です。

同様に、

f_k(3) = 3余り2

f_k(4) = 4余り3

・・・・

f_k(k) = k余り(k-1)

です。f(k)は(k-1)余ってますが、(k-1)で割るのでこの余りは消えて商が1増えます。ということで、f(k) = k+1となります。これで、(1,2,3,.....k)という点列が(1,2,3,....,k-1, k+1)となりました。さらに続きを調べるために、g_k(x) = (k * x - 1) を (k-1)で割った余りが0になる場所を調べます。

g_k(1) = 0 (mod (k-1))

g_k(k) = 0 (mod (k-1))

g_k(2*k-1) = 0 (mod (k-1))

・・・・

なので、y = 1 + i * (k-1), i = 0,1,2,3,...なる正の整数yに対してg_k(y) = 0 (mod (k-1))となります。先の例で正の整数の点列からkが除去されることを確認しました。2*k-1という場所は本来2*kがある場所です。（kが無くなってるから1引かれる）。ここで同様に商の繰り上がりがおこることから、2*kは点列から除去されます。同様に3*k-2に対応する3*kも除去されます。以降同様にして、kの倍数がすべて除去されるというわけです。

　ここまでで、写像f_kがkの倍数だけを除いた整数点列を生成できることが分かりました。ソースコードを見ると、まず

ret = k * s;

としているので、retは、(1,2,3...n)の点列を拡張して、(1,2,3,....,n,n+1,n+2,....... k*s)にしたものを考えていることが分かります。ここから逆算して、k*sが区間[1,n]の整数のどれに対応しているかをみていこうというわけです。(ret - n)でnからはみ出ている分が分かります。このはみ出ている部分に対して、写像f_kを適用することで、retは消えたものを除いて数えた場合にそれがあるべき場所へとマッピングされます。これをret <= nになるまで繰り返しているというわけです。ちょっと説明足らずな感じなので、表で示します。n = 5, k = 3, s = 5とした場合、

k*s	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
k*s - n	-	-	-	-	-	1	2	3	4	5	6	7	8	9	10
f_k(k*s - n)	-	-	-	-	-	1	2	4	5	7	8	10	11	13	14

となります。例えば、処刑される順番は、k*s = 3, 6, 9, 12, 15の順です。それぞれ見て行きます。

1番目に処刑される人は、3番目の人です。

2番目に処刑されるのは、6ですが、これはnより大きいので、もともといる位置に変換します。表のf_k(k*s - n)を見ると1なので、1番目の人です。

3番目に処刑されるのは、9ですが、これも同様に対応位置に変換して5になります。

4番目に処刑されるのは、12 -> 10 -> 7 -> 2と変換されるので、2番目の人です。

同様に、最後に処刑されるのは、15 -> 14 -> 13 -> 11 -> 8 -> 4で4番目の人です。

ということで、(3, 1, 5, 2, 4)の順で処刑されるということです。4の位置に居れば助かりますね！