151220

Ruby

Josephus problem

最後に残ったものの番号を求めてみた。
オンライン整数列大辞典の
A032434（http://oeis.org/A032434/list）
と比較し、答え合わせしてみる。

def f(n, m)
  return 1 if n == 1
  (m - 1 + f(n - 1, m)) % n + 1
end

def A032434(n)
  ary = []
  i = 1
  while ary.size < n
    ary += (1..i).map{|j| f(i, j)}
    i += 1
  end
  ary[0..n - 1]
end
ary = A032434(95)

# OEIS A032434のデータ
ary0 =
[1,2,1,3,3,2,4,1,1,2,5,3,4,1,2,6,5,1,5,1,4,7,7,4,
 2,6,3,5,8,1,7,6,3,1,4,4,9,3,1,1,8,7,2,3,8,10,5,4,
 5,3,3,9,1,7,8,11,7,7,9,8,9,5,9,5,7,7,12,9,10,1,1,
 3,12,5,2,5,6,11,13,11,13,5,6,9,6,13,11,2,4,10,8,
 14,13,2,9]
# 一致の確認
p ary == ary0