170402

Ruby

A109091 の計算

二通りで計算してみたが、後者の方がコードがシンプル。

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

def p0(n)
  (3 * n * n - n) / 2
end

def p1(n)
  (3 * n * n + n) / 2
end

def A010815(n)
  ary = Array.new(n + 1, 0)
  ary[0] = 1
  i = 1
  j = p0(i)
  while j <= n
    ary[j] = (-1) ** i
    i += 1
    j = p0(i)
  end
  i = 1
  j = p1(i)
  while j <= n
    ary[j] = (-1) ** i
    i += 1
    j = p1(i)
  end
  ary
end

# m次以下を取り出す
def power(ary, n, m)
  return [1] if n == 0
  k = power(ary, n >> 1, m)
  k = mul(k, k, m)
  return k if n & 1 == 0
  return mul(k, ary, m)
end

def f(ary, k, n)
  aryk = Array.new(n + 1, 0)
  (0..n / k).each{|i| aryk[k * i] = ary[i]}
  aryk
end

def A(k, n)
  ary = A010815(n)
  aryk = power(ary, k, n)
  ps = Array.new(n + 1, 0)
  ps[0] = 1
  (1..n).each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  psk = f(ps, k, n)
  mul(aryk, psk, n)
end

def A109091_1(n)
  ary = A(5, n)
  (1..n).map{|i| - ary[i] / 5}
end

def s(k, m, n)
  s = 0
  (1..n).each{|i| s += i if n % i == 0 && i % k == m}
  s
end

def A109091_2(n)
  (1..n).map{|i| s(5, 1, i) + s(5, 4, i) - s(5, 2, i) - s(5, 3, i)}
end

n = 1000
p ary = A109091_1(n)
p ary == A109091_2(n)

出力結果
[1, -1, -2, 3, 1, 2, -6, -5, 7, -1, 12, -6, -12, 6, -2, 11, -16, -7, 20, 3, 12, -12, -22, 10, 1, 12, -20, -18, 30, 2, 32, -21, -24, 16, -6, 21, -36, -20, 24, -5, 42, -12, -42, 36, 7, 22, -46, -22, 43, -1, 32, -36, -52, 20, 12, 30, -40, -30, 60, -6, 62, -32, -42, 43, -12, 24, -66, -48, 44, 6, 72, -35, -72, 36, -2, 60, -72, -24, 80, 11, 61, -42, -82, 36, -16, 42, -60, -60, 90, -7, 72, -66, -64, 46, 20, 42, -96, -43, 84, 3, 102, -32, -102, 60, 12, 52, -106, -60, 110, -12, 72, -66, -112, 40, -22, 90, -84, -60, 96, 10, 133, -62, -84, 96, 1, 42, -126, -85, 84, 12, 132, -72, -120, 66, -20, 80, -136, -44, 140, -18, 92, -72, -144, 77, 30, 72, -86, -108, 150, 2, 152, -100, -112, 72, 32, 72, -156, -80, 104, -21, 132, -61, -162, 126, -24, 82, -166, -60, 157, 16, 140, -126, -172, 60, -6, 132, -120, -90, 180, 21, 182, -72, -124, 110, -36, 64, -192, -138, 120, -20, 192, -86, -192, 96, 24, 129, -196, -84, 200, -5, 132, -102, -180, 96, 42, 102, -154, -132, 240, -12, 212, -156, -144, 106, -42, 100, -192, -110, 144, 36, 192, -72, -222, 126, 7, 112, -226, -120, 230, 22, 144, -150, -232, 84, -46, 180, -160, -96, 240, -22, 242, -133, -182, 186, 43, 84, -240, -160, 164, -1, 252, -126, -264, 126, 32, 171, -256, -84, 216, -36, 210, -132, -262, 120, -52, 120, -180, -198, 270, 20, 272, -176, -144, 136, 12, 132, -276, -140, 224, 30, 282, -92, -282, 216, -40, 144, -252, -147, 273, -30, 192, -216, -292, 86, 60, 180, -240, -150, 264, -6, 252, -152, -204, 220, 62, 112, -306, -216, 204, -32, 312, -120, -312, 156, -42, 240, -316, -104, 360, 43, 212, -132, -320, 183, -12, 162, -220, -210, 276, 24, 332, -246, -252, 166, -66, 132, -336, -157, 224, -48, 384, -140, -300, 210, 44, 172, -346, -180, 350, 6, 240, -252, -352, 120, 72, 270, -192, -180, 360, -35, 381, -182, -266, 216, -72, 124, -366, -242, 294, 36, 312, -192, -372, 192, -2, 230, -360, -120, 380, 60, 252, -192, -382, 170, -72, 192, -294, -288, 390, -24, 352, -215, -264, 196, 80, 252, -396, -200, 240, 11, 402, -132, -384, 306, 61, 180, -432, -160, 410, -42, 272, -306, -360, 154, -82, 252, -280, -240, 420, 36, 422, -212, -322, 260, -16, 144, -372, -318, 288, 42, 432, -220, -432, 192, -60, 330, -440, -144, 440, -60, 301, -192, -442, 216, 90, 222, -300, -258, 450, -7, 504, -336, -304, 226, 72, 200, -456, -230, 320, -66, 462, -144, -462, 330, -64, 232, -466, -252, 396, 46, 312, -300, -504, 160, 20, 288, -364, -240, 480, 42, 432, -242, -264, 399, -96, 182, -486, -310, 324, -43, 492, -252, -480, 240, 84, 352, -432, -164, 500, 3, 332, -252, -502, 210, 102, 264, -314, -378, 510, -32, 432, -341, -400, 256, -102, 252, -552, -216, 344, 60, 522, -210, -522, 396, 12, 262, -512, -264, 507, 52, 420, -360, -504, 180, -106, 330, -360, -270, 516, -60, 542, -272, -364, 336, 110, 144, -546, -408, 434, -12, 600, -220, -480, 276, 72, 420, -556, -224, 504, -66, 384, -282, -562, 276, -112, 282, -366, -360, 570, 40, 572, -432, -384, 252, -22, 301, -576, -273, 384, 90, 492, -192, -624, 360, -84, 292, -586, -258, 640, -60, 392, -396, -592, 240, 96, 450, -400, -264, 600, 10, 602, -252, -462, 456, 133, 204, -606, -420, 360, -62, 552, -336, -612, 306, -84, 360, -616, -204, 620, 96, 440, -312, -540, 264, 1, 312, -480, -468, 576, 42, 632, -400, -424, 316, -126, 312, -516, -360, 504, -85, 642, -212, -642, 396, 84, 320, -646, -305, 720, 12, 384, -486, -652, 220, 132, 462, -504, -276, 660, -72, 662, -332, -384, 410, -120, 252, -660, -498, 444, 66, 744, -252, -672, 336, -20, 471, -676, -224, 576, 80, 452, -384, -682, 420, -136, 300, -460, -462, 624, -44, 692, -516, -504, 346, 140, 300, -672, -350, 464, -18, 702, -240, -720, 516, 92, 352, -612, -360, 710, -72, 560, -450, -704, 192, -144, 540, -480, -360, 720, 77, 612, -381, -484, 546, 30, 266, -726, -360, 547, 72, 672, -372, -732, 366, -86, 462, -792, -294, 740, -108, 480, -312, -742, 320, 150, 372, -574, -576, 636, 2, 752, -506, -504, 360, 152, 360, -756, -380, 528, -100, 762, -252, -660, 576, -112, 382, -720, -342, 770, 72, 512, -576, -772, 294, 32, 480, -432, -390, 840, 72, 864, -352, -600, 473, -156, 264, -786, -588, 524, -80, 672, -420, -744, 396, 104, 600, -796, -240, 736, -21, 630, -402, -864, 396, 132, 384, -540, -510, 810, -61, 812, -540, -544, 432, -162, 352, -840, -410, 504, 126, 822, -272, -822, 510, -24, 360, -826, -462, 830, 82, 552, -516, -688, 280, -166, 720, -640, -420, 840, -60, 871, -422, -564, 636, 157, 322, -798, -572, 564, 16, 792, -432, -852, 372, 140, 530, -856, -288, 860, -126, 504, -432, -862, 420, -172, 432, -546, -576, 960, 60, 792, -550, -672, 440, -6, 432, -876, -440, 584, 132, 882, -301, -882, 576, -120, 442, -886, -360, 756, -90, 732, -666, -920, 300, 180, 510, -528, -450, 960, 21, 832, -504, -504, 560, 182, 304, -906, -678, 714, -72, 912, -440, -984, 456, -124, 690, -792, -320, 920, 110, 612, -462, -864, 432, -36, 462, -714, -630, 930, 64, 860, -696, -624, 466, -192, 420, -936, -396, 624, -138, 942, -312, -924, 660, 120, 504, -946, -480, 864, -20, 632, -480, -952, 364, 192, 720, -720, -480, 816, -86, 993, -432, -742, 726, -192, 264, -966, -665, 640, 96, 972, -546, -840, 486, 24, 682, -976, -324, 1080, 129, 770, -492, -982, 420, -196, 480, -552, -720, 924, -84, 992, -672, -664, 432, 200, 492, -996, -500, 720, -5]
true