150720

Ruby


隣接素数の和で表す表し方の数

オンライン整数列大辞典の
A054845（http://oeis.org/A054845/list）
と比較し、答え合わせしてみる。
A054845（http://oeis.org/A054845）によれば、
Moser shows that the average order of a(n) is log 2, that is, sum(i=1..n, a(i)) ~ n log 2
ということなのだが、以下のコードではこのことが正しいと確信できなかった。

require 'prime'

def A054845(n)
  ary = Array.new(n + 1, 0)
  p_ary = Prime.each(n).to_a
  size = p_ary.size
  # 先頭をp_ary[i]に固定する
  (0..size - 1).each{|i|
    j = i
    sum = p_ary[j]
    while sum <= n
      ary[sum] += 1
      j += 1
      break if j > size - 1
      sum += p_ary[j]
    end
  }
  ary
end
ary = A054845(101)

# OEIS A054845のデータ
ary0 =
[0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0,0,0,2,
 1,0,1,0,1,1,1,2,0,0,0,0,2,1,0,1,0,3,1,1,0,0,0,1,1,
 1,0,0,1,2,0,0,1,0,1,2,2,1,0,0,0,0,0,2,1,0,0,2,2,1,
 0,1,0,1,1,1,0,0,0,3,1,0,0,0,1,1,2,0,0,0,0,1,0,2,1,
 0,2,2]
# 一致の確認
p ary == ary0

def accumulation(ary)
  i = 1
  while i <= ary.size - 1
    ary[i] += ary[i - 1]
    i += 1
  end
  ary
end
# 元々
p ary
# 累積
p accumulation(ary)

M = 8
ary = A054845(10 ** M)
a_ary = accumulation(ary)
p ''
p Math.log(2) # a_ary[i]はi * log2くらい
(0..M).each{|m| p a_ary[10 ** m]}

出力結果

true
[0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 2, 1, 1, 0, 0, 0, 2, 1, 0, 1
, 0, 1, 1, 1, 2, 0, 0, 0, 0, 2, 1, 0, 1, 0, 3, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
2, 0, 0, 1, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 2, 2, 1, 0, 1, 0, 1, 1, 1,
 0, 0, 0, 3, 1, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 1, 0, 2, 1, 0, 2, 2]
[0, 0, 1, 2, 2, 4, 4, 5, 6, 6, 7, 8, 9, 10, 10, 11, 11, 13, 14, 15, 15, 15, 15,
17, 18, 18, 19, 19, 20, 21, 22, 24, 24, 24, 24, 24, 26, 27, 27, 28, 28, 31, 32,
33, 33, 33, 33, 34, 35, 36, 36, 36, 37, 39, 39, 39, 40, 40, 41, 43, 45, 46, 46,
46, 46, 46, 46, 48, 49, 49, 49, 51, 53, 54, 54, 55, 55, 56, 57, 58, 58, 58, 58,
61, 62, 62, 62, 62, 63, 64, 66, 66, 66, 66, 66, 67, 67, 69, 70, 70, 72, 74]
""
0.6931471805599453
0
7
72
684
6667
65716
650999
6475810
64581536