160517(2)

Ruby


Goldbach's conjecture(3)

n = 10 ** i のとき、ペアの数を数えてみる。

require'prime'

def f(n)
  Prime.each(n / 2).count{|i| (n - i).prime?}
end

def A065577(n)
  (1..n).map{|i| f(10 ** i)}
end

p A065577(7)

出力結果
[2, 6, 28, 127, 810, 5402, 38807]

上は短いコードだが大変遅い。
ちなみに、次のコードはかなり速い。

def p_table(n)
  ary = Array.new(n + 1, true)
  ary[0], ary[1] = false, false
  i = 2
  while i * i <= n
    if ary[i]
      j = i + i
      while j <= n
        ary[j] = false
        j += i
      end
    end
    i += 1
  end
  ary
end

def f(n)
  a = p_table(n)
  (1..n / 2).count{|i| a[i] && a[n - i] == true}
end

def A065577(n)
  (1..n).map{|i| f(10 ** i)}
end

p A065577(8)

出力結果
[2, 6, 28, 127, 810, 5402, 38807, 291400]