10797


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 を探せば効率が良いか教えていただけないでしょうか？


CC BY-SA 3.0
2015-05-30T06:22:51.783
10791
2015-05-30T14:27:21.357
2015-05-30T12:54:03.360
5363
5363
question
ruby アルゴリズム
Ulam number の効率の良い求め方について


相異なる２つの Ulam number の和が i となるものを数えるということは、  
片方が ary[j] と決めたとき、もう片方は i - ary[j] でなくてはいけない。  
よって、以下のコードとなる。

[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
        cnt += 1 if ary.include?(i - ary[j])
      }
      ary.push(i) if cnt == 1
    }
    p ary
    
[/code]

出力結果  
[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72,
7  
7, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180,
1  
82, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282,
3  
09, 316, 319, 324, 339]

(追記)  
pgrho さんの回答を見て次のように改良しました。

[code]

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

コードに無駄な部分があれば、ご指摘いただければ幸いです。


CC BY-SA 3.0
2015-05-30T12:18:42.383
10794
2015-05-30T14:27:21.357
2015-05-30T14:27:21.357
5363
5363
10791
answer


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)ぐらい減らせるかと思います。


CC BY-SA 3.0
2015-05-30T12:54:59.370
10797
2015-05-30T13:14:36.607
2015-05-30T13:14:36.607
5750
5750
10791
answer