Ulam number の効率の良い求め方について Ulam number < ① Ulam number 1 Ulam number Ulam number N = 339 N Ulam number N = 339 ary = [1, 2] (3..N).each{|i| cnt = 0 (0..ary.size - 2).each{|j| break if ary[j] + ary[j + 1] > i (j + 1..ary.size - 1).each{|k| l = ary[j] + ary[k] break if l > i cnt += 1 if l == i } } ary.push(i) if cnt == 1 } p ary Ulam number i i = 100 1 + 2 Ulam number

Manyama

`ary[0]``ary[1]`…`ary[n - 1]`


ary[n] >= ary[n -1] + 1 = ary[0] + ary[n - 1]




`j`0`ary.include(i - ary[j])`

`j - 1`


ary[k] <= i - ary[j - 1] < ary[k + 1]


`j`


i - ary[j] < i - ary[j - 1]


`k`

O(n)