150301

Ruby


Silverman's Sequence

以下のコードより次のことがわかる。

　最初からN個取り出すに十分なaryは、

　　　　N≦ 11のとき、[1, 2, 2]

　12≦N≦ 38のとき、[1, 2, 2, 3, 3]

　39≦N≦122のとき、[1, 2, 2, 3, 3, 4, 4, 4]

　…

　である。

N = 122

ary = [1, 2, 2]

s = 1 + 2 * (6 - 1)

i = 3

while s < N

  j = ary.size

  k = j + ary[i - 1]

  ary += [i] * ary[i - 1] 

  s += i * ((k * (k + 1)) / 2 - (j * (j + 1)) / 2)

  i += 1

end

p ary

s_ary = []

s1 = 0

s2 = 0

i = 0

for j in (1..N)

  while s2 + ary[i] * (i + 1) < j

    s1 += ary[i]

    s2 += ary[i] * (i + 1)

    i += 1

  end

  s_ary << s1 + ((j - s2) * 1.0 / (i + 1)).ceil

end

p s_ary