150531

Ruby


Ulam number

昨日以下のサイトで N 以下の Ulam number の効率の良い求め方について質問してみた。

（http://ja.stackoverflow.com/questions/10791/ulam-number-%E3%81%AE%E5%8A%B9%E7%8E%87%E3%81%AE%E8%89%AF%E3%81%84%E6%B1%82%E3%82%81%E6%96%B9%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6）

これを用いて、339以下の Ulam number を求め、
オンライン整数列大辞典の

A002858（http://oeis.org/A002858/list）
と比較し、答え合わせしてみる。

N = 339

ary = [1, 2]

(3..N).each{|i|

  cnt = 0

  k = ary.size - 1

  (0..k - 1).each{|j|

    break if j >= k

    m = i - ary[j]

    while ary[k] > m

      k -= 1

    end

    cnt += 1 if ary[k] == m && j < k

  }

  ary.push(i) if cnt == 1

}

# OEIS A002858のデータ

ary0 =

[1,2,3,4,6,8,11,13,16,18,26,28,36,38,47,48,53,57,

 62,69,72,77,82,87,97,99,102,106,114,126,131,138,

 145,148,155,175,177,180,182,189,197,206,209,219,

 221,236,238,241,243,253,258,260,273,282,309,316,

 319,324,339]

# 一致の確認

p ary == ary0