160528(2)

Ruby

Bell number(2)

せきゅーんさんの記事（http://integers.hatenablog.com/entry/2016/05/28/025945）を見て、
Bell number n mod n を計算しようと思った。

オンライン整数列大辞典の
A166226（http://oeis.org/A166226/list）
と比較し、答え合わせしてみる。

def bell(n)
  return 1 if n == 0
  i = 1
  bell = [1]
  while i < n
    next_bell = [bell[-1]]
    # Bell triangle
    i.times{|j| next_bell[j + 1] = next_bell[j] + bell[j]}
    bell = next_bell
    i += 1
  end
  bell[-1]
end

def A166226(n)
  (1..n).map{|i| bell(i) % i}
end
ary = A166226(85)

# OEIS A166226のデータ
ary0 =
[0,0,2,3,2,5,2,4,6,5,2,1,2,12,5,3,2,13,2,12,15,5,
 2,9,3,18,10,3,2,27,2,12,4,5,0,1,2,24,28,27,2,23,2,
 8,5,5,2,33,24,20,49,39,2,5,27,28,34,5,2,57,2,36,6,
 51,47,19,2,52,15,25,2,49,2,42,22,71,59,19,2,44,23,
 5,2,65,84]
# 一致の確認
p ary == ary0