160223

Ruby


Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(4)

まず、n が4000 以下の場合を5時間半かけて求めた。
（データの容量が1MB を超えているので、
https://sites.google.com/site/manyamanobuwu/201602230001
に添付しています。）
そしてもう一回、n が4000 以下の場合を5時間半かけて求め、
さらに、以下のコードでn が4000 のときの値を5時間半かけて求めてみた。

=begin
1～nまでの和がn(n + 1) / 2なので、
1～nの中からいくつか選び、和がn(n + 1) / 4
となるものを数えればよい。
=end
 
def A063865(n)
  ary = [1]
  m = n * (n + 1) / 4
  a = Array.new(m + 1){0}
  a[0] = 1
  (1..n).each{|i|
    b = a.clone
    (0..[(i - 1) * i / 2, m - i].min).each{|k| b[k + i] += a[k]}
    a = b
    i * (i + 1) % 4 == 0 ? ary << a[i * (i + 1) / 4] : ary << 0
  }
  ary
end

p A063865(4000)[-1]

出力結果
71988492379520999128249554426154581015291162663671572693079317490501671952439341913581770187175201211036073750576661260789144040611195986123603335736134428477266374720430458902973948122489987121193650881632464039185888492976917812137525865723628284363474812215388436258130149465369928595748642085797004549989847304722675831846802658041877155022294706883010316527350806366775299036272657281664834832822654950774530751416630242972046114884262990945180426106270677181107671565139805177586222813051792763936917726321820816501410579507955349798468140704472383598040510041704675040518022006750403480472327386246730717625429721425300449588300444061820168372181794496655723711960469407449893343144449618343187464932501498523740489078321964441381954785886825780941777869204494691212583389243770699088932295443311178506666405371750138742130494941718968478581141296325202458078708773243605791737578190646587968003753863162455122176416551554120678092826070090678734355966067889054222589927684372473193312663627864520451588087161180439657477125986345961497749102968303731402709536949905145427036889747009374141404530359939293397818378788311806751915442925817101510044249965430490308744023360879418563308731401524