160516(4)

Ruby

Number of ordered ways of writing n as sum of three primes

(Σx^p)^3 の係数について、
オンライン整数列大辞典の
A098238（http://oeis.org/A098238/list）
と比較し、答え合わせしてみる。

require 'prime'

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  s10 = [s1 - 1, m].min
  (0..s10).each{|i|
    s20 = [s2 - 1, m - i].min
    (0..s20).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def A098238(n)
  ary = Array.new(n + 1, 0)
  Prime.each(n).each{|i| ary[i] = 1}
  mul(mul(ary, ary, n), ary, n)[0..n]
end
ary = A098238(74)

# OEIS A098238のデータ
ary0 =
[0,0,0,0,0,0,1,3,3,4,6,6,9,6,6,10,9,12,12,12,12,
 19,12,21,15,21,18,30,15,30,12,30,18,37,12,39,21,
 42,24,46,9,51,18,48,24,54,18,66,21,60,30,67,24,81,
 18,75,30,79,18,87,21,87,36,93,15,105,30,105,36,97,
 12,120,30,114,36]
# 一致の確認
p ary == ary0