Ulam number の効率の良い求め方について


Ulam number とは以下の性質を持つ数である。  
（<http://en.wikipedia.org/wiki/Ulam_number>）  
①今まで現れた相異なる２つの Ulam number の和で表そうとしたとき、1通りしか出来ない。  
注）相異なる２つの Ulam number の和で表せないときは、Ulam number ではない。

N = 339 とし、  
N 以下の Ulam number を次のように求めてみた。

[code]

    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
    
[/code]

しかし、このコードは  
相異なる２つの Ulam number の和が i となるものを数えるのに、  
逐一調べている。  
（例えば、i = 100 のときでも、1 + 2 から調べている。）

どのように Ulam number を探せば効率が良いか教えていただけないでしょうか？




Manyamaさんの回答のコードで感じたことを。

計算済みの数列を`ary[0]`、`ary[1]`…、`ary[n - 1]`とすると

[code]

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

が成り立ちます。

なので`j`が0の場合、回答で`ary.include(i - ary[j])`としている部分は最後の要素だけを判定すればよいです。

さらに`j - 1`の時の探索結果が

[code]

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

であれば、次の`j`の時は

[code]

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

を満たすので`k`から降順に判定すると効率的です。

この二点で計算オーダーがO(n)ぐらい減らせるかと思います。




Manyamaさんの回答のコードで感じたことを。

計算済みの数列を`ary[0]`、`ary[1]`…、`ary[n - 1]`とすると

[code]

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

が成り立ちます。

なので`j`が0の場合、回答で`ary.include(i - ary[j])`としている部分は最後の要素だけを判定すればよいです。

さらに`j - 1`の時の探索結果が

[code]

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

であれば、次の`j`の時は

[code]

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

を満たすので`k`から降順に判定すると効率的です。

この二点で計算オーダーがO(n)ぐらい減らせるかと思います。

