151011(4)

Ruby

Number of times 1 is used in writing out all the numbers 1 through n(3)

オンライン整数列大辞典のA014778のCOMMENTSを見ると、
このような性質をもつ数は84個あるらしい。
これらを出力してみる。

def A014778(n)
  i = 0
  cnt = 0
  ary = [0]
  num = 1
  while num < n
    i += 1
    cnt += i.to_s.count("1")
    if i == cnt
      ary << i
      num += 1
    end
  end
  ary
end

p A014778(84)

出力結果
[0, 1, 199981, 199982, 199983, 199984, 199985, 199986, 199987, 199988, 199989, 199990, 200000, 200001, 1599981, 1599982, 1599983, 1599984, 1599985, 1599986, 1599987, 1599988, 1599989, 1599990, 2600000, 2600001, 13199998, 35000000, 35000001, 35199981, 35199982, 35199983, 35199984, 35199985, 35199986, 35199987, 35199988, 35199989, 35199990, 35200000, 35200001, 117463825, 500000000, 500000001, 500199981, 500199982, 500199983, 500199984, 500199985, 500199986, 500199987, 500199988, 500199989, 500199990, 500200000, 500200001, 501599981, 501599982, 501599983, 501599984, 501599985, 501599986, 501599987, 501599988, 501599989, 501599990, 502600000, 502600001, 513199998, 535000000, 535000001, 535199981, 535199982, 535199983, 535199984, 535199985, 535199986, 535199987, 535199988, 535199989, 535199990, 535200000, 535200001, 1111111110]

151011(3)

Ruby

Number of times 1 is used in writing out all the numbers 1 through n(2)

オンライン整数列大辞典の
A014778（http://oeis.org/A014778/list）
と比較し、答え合わせしてみる。

def A014778(n)
  i = 0
  cnt = 0
  ary = [0]
  num = 1
  while num < n
    i += 1
    cnt += i.to_s.count("1")
    if i == cnt
      ary << i
      num += 1
    end
  end
  ary
end
ary = A014778(28)

# OEIS A014778のデータ
ary0 =
[0,1,199981,199982,199983,199984,199985,199986,
 199987,199988,199989,199990,200000,200001,1599981,
 1599982,1599983,1599984,1599985,1599986,1599987,
 1599988,1599989,1599990,2600000,2600001,13199998,
 35000000]
# 一致の確認
p ary == ary0

151011(2)

Ruby

Number of times 1 is used in writing out all the numbers 1 through n(1)

「非公認 Googleの入社試験」に載っている次の問題を解いてみた。

Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?

(http://mathworld.wolfram.com/news/2004-10-13/google/)

i = 0
cnt = 0
num = 0
while num < 2
  i += 1
  cnt += i.to_s.count("1")
  num += 1 if i == cnt
end
p i

出力結果
199981

151011

Ruby

整数零点

「リーマン予想を解こう」の第７章の問題を実装してみた。

# n - 1を2進表記したときの1の個数
def d(n)
  (n - 1).to_s(2).count('1')
end

def sign(n)
  n % 2 == 0 ? 1 : -1
end

# nが0以上のとき
def power(a, n)
  return 1 if n == 0
  k = power(a, n >> 1)
  k *= k
  return k if n & 1 == 0
  return k * a
end

def ncr(n, r)
  return 1 if r == 0
  return (n - r + 1..n).inject(:*) / (1..r).inject(:*)
end

def z(r, s)
  ans = 0
  (1..2 << (r - 1)).each{|n| ans += sign(d(n)) * power(n, - s)}
  ans
end

(1..7).each{|r|
  # 1 - r ≦ s ≦ 0のときzは0
  0.downto(1 - r - 1){|s| p [r, s, z(r, s)]}
}

def z_bin(r, s)
  ans = 0
  (1..r).each{|n| ans += sign(n - 1) * ncr(r - 1, n - 1) * power(n, - s)}
  ans
end

# 多重フルビッツゼータ関数（負位数）のs = 0, -1, -2, …における零点
(1..7).each{|r|
  # 2 - r ≦ s ≦ 0のときz_binは0、1 - rのときz_binは(-1)^(r - 1)*(r - 1)!
  0.downto(1 - r){|s| p [r, s, z_bin(r, s)]}
}

出力結果
[1, 0, 0]
[1, -1, -1]
[2, 0, 0]
[2, -1, 0]
[2, -2, 4]
[3, 0, 0]
[3, -1, 0]
[3, -2, 0]
[3, -3, -48]
[4, 0, 0]
[4, -1, 0]
[4, -2, 0]
[4, -3, 0]
[4, -4, 1536]
[5, 0, 0]
[5, -1, 0]
[5, -2, 0]
[5, -3, 0]
[5, -4, 0]
[5, -5, -122880]
[6, 0, 0]
[6, -1, 0]
[6, -2, 0]
[6, -3, 0]
[6, -4, 0]
[6, -5, 0]
[6, -6, 23592960]
[7, 0, 0]
[7, -1, 0]
[7, -2, 0]
[7, -3, 0]
[7, -4, 0]
[7, -5, 0]
[7, -6, 0]
[7, -7, -10569646080]
[1, 0, 1]
[2, 0, 0]
[2, -1, -1]
[3, 0, 0]
[3, -1, 0]
[3, -2, 2]
[4, 0, 0]
[4, -1, 0]
[4, -2, 0]
[4, -3, -6]
[5, 0, 0]
[5, -1, 0]
[5, -2, 0]
[5, -3, 0]
[5, -4, 24]
[6, 0, 0]
[6, -1, 0]
[6, -2, 0]
[6, -3, 0]
[6, -4, 0]
[6, -5, -120]
[7, 0, 0]
[7, -1, 0]
[7, -2, 0]
[7, -3, 0]
[7, -4, 0]
[7, -5, 0]
[7, -6, 720]

151004(4)

Ruby

素数が無数に存在すること(2)

ans を次のように変更してみた。

ans =
[[11, 1, 26], [11, 2, 12], [11, 3, 14], [11, 5, 13], [11, 7, 17],
 [13, 1, 16], [13, 2, 10], [13, 3, 14], [13, 5, 11], [13, 7, 29], [13, 11, 13],
 [17, 1, 14], [17, 2, 15], [17, 3, 12], [17, 5, 10], [17, 7, 14], [17, 11, 9], [17, 13, 14],
 [19, 1, 11], [19, 2, 22], [19, 3, 14], [19, 5, 24], [19, 7, 12], [19, 11, 15], [19, 13, 11], [19, 17, 17]]

出力結果
[11, 2, 23, 3, 7, 10627, 433, 17, 13, 10805892983887, 73, 6397, 19, 489407, 2753, 87491, 18618443, 5, 31, 113, 41, 10723, 35101153, 25243, 374399, 966011]
[11, 13, 5, 3, 19, 53, 2160017, 17, 941, 2689, 33199, 347]
[11, 2, 5, 113, 12433, 13, 271, 149, 81123368170133, 2257771, 7, 647, 187927, 17]
[11, 2, 3, 71, 4691, 19, 17, 62921, 107, 7, 547, 53, 41]
[11, 2, 29, 3, 17, 5, 19, 3091117, 1365167, 47934661, 647, 5851, 3191, 64613, 13, 1835467, 31]
[13, 2, 3, 79, 6163, 7, 1601, 11, 137, 5, 199, 151, 263, 983, 31, 83]
[13, 3, 41, 1601, 769, 11, 26981, 109, 4423, 347]
[13, 2, 29, 757, 570781, 103, 7, 89, 5, 19, 23333, 11, 579239, 17]
[13, 2, 31, 811, 439, 7, 457, 37, 33965372384767, 11, 3]
[13, 2, 3, 5, 397, 67, 10373617, 17, 31, 183377, 79331891, 461, 3259, 809, 1423, 29, 3897871, 11, 929, 41, 59, 1549, 47, 13291, 223, 937, 33802553, 263, 272887]
[13, 2, 37, 7, 5, 3, 101021, 17, 29, 211, 163, 881, 8293]
[17, 2, 5, 3, 7, 3571, 31, 395202571, 13, 29, 137, 23, 97, 1896893]
[17, 19, 5, 3, 37, 11, 463, 29, 26476902707, 41, 31, 7, 193, 128461, 1091]
[17, 2, 37, 13, 11, 179897, 7, 23, 43, 224044832325317, 50707, 3321049]
[17, 2, 3, 107, 61, 151, 100528859, 13793921, 43, 331]
[17, 2, 41, 3, 59, 5, 23, 163, 12713, 19, 83, 251, 1321, 103]
[17, 2, 3, 113, 83, 7, 6696617, 53, 2376764095840817]
[17, 2, 47, 3, 11, 52747, 2781560311, 419, 5, 727, 281, 4999, 593, 7]
[19, 2, 3, 5, 571, 271, 457, 397, 1123, 23, 103]
[19, 3, 59, 5, 67, 17, 7, 13, 13883, 139, 47, 158073099816915467, 743837, 96211, 4721, 11, 131, 3957743, 3519413, 167, 6221, 3307]
[19, 2, 41, 7, 10909, 2473, 5, 89, 23, 17, 28163, 137, 67, 71]
[19, 2, 43, 11, 3, 53927, 89, 7, 263, 1553, 26183, 6581, 179, 193357, 109, 2699, 135043, 647, 131, 193, 139, 1033, 17, 2797]
[19, 2, 3, 11, 13, 47, 89, 68191273, 5, 40289, 3797, 17]
[19, 2, 7, 277, 73693, 113, 3, 5, 17, 29, 22933501, 31, 2099, 13, 6131]
[19, 2, 3, 127, 43, 11, 7, 47936671, 17, 607, 5]
[19, 2, 5, 3, 587, 7, 163, 127, 173, 577, 293, 11, 24592219, 41, 476633, 9581771, 1277]

151004(3)

Ruby

素数が無数に存在すること(1)

素数が無数に存在することの証明はたくさんあるが、ユークリッドの証明を真似て次のように示してみた。

p0, p1を異なる素数とする。

m1 = p1 + p0 とおく。

①m1 が素数なら、p0, p1 と異なる素数である。

②m1 が合成数なら、p0, p1 で割り切れないので、m1 はp0, p1 と異なる素因数を含む。

①の場合、p2 = m1 とし、②の場合、p0, p1 と異なるm1 の素因数のうち最小のものをp2 とする。

m2 = p1 * p2 + p0 とおく。

①m2 が素数なら、p0, p1, p2 と異なる素数である。

②m2 が合成数なら、p0, p1, p2 で割り切れないので、m2 はp0, p1, p2 と異なる素因数を含む。

①の場合、p3 = m2 とし、②の場合、p0, p1, p2 と異なるm2 の素因数のうち最小のものをp3 とする。

m3 = p1 * p2 * p3 + p0 とおく。

先程と同様にして、p0, p1, p2, p3 と異なる素数p4 が見つかる。

このことを繰り返せば、任意の自然数Nに対し、異なるN個の素数が見つかる。

よって、素数は無数に存在する。

ユークリッドの証明および上記の証明で行なっている作業を以下のように書いてみた。

require 'prime'

# 素因数の候補
p_ary = Prime.each(10 ** 8).to_a

ans =
[[2, 1, 16],
 [3, 1, 16], [3, 2, 21],
 [5, 1, 18], [5, 2, 14], [5, 3, 17],
 [7, 1, 16], [7, 2, 12], [7, 3, 19], [7, 5, 20]]

ans.each{|a, b, n|
  ary = [a]
  s = a
  i = 1
  while i < n
    s0 = s + b
    if s0.prime?
      a = s0
    else
      j = 0
      # aryに含まれていないs0の素因数を探す
      while ary.include?(p_ary[j]) || s0 % p_ary[j] > 0
        j += 1
      end
      a = p_ary[j]
    end
    ary << a
    s *= a
    i += 1
  end
  p ary
}

出力結果
[2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003]
[3, 2, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003]
[3, 5, 17, 257, 65537, 641, 7, 318811, 19, 1747, 12791, 73, 90679, 67, 59, 113, 13, 41, 47, 151, 131]
[5, 2, 11, 3, 331, 19, 199, 53, 21888927391, 29833, 101, 71, 23, 311, 7, 72353, 13, 227]
[5, 7, 37, 1297, 17, 3, 13, 11, 953, 19, 24239, 5376221562149172737, 36061, 2633]
[5, 2, 13, 7, 11, 17, 167, 4079, 487, 73, 421, 2382557, 337, 19, 577, 29573, 97]
[7, 2, 3, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003]
[7, 3, 23, 5, 2417, 1021, 19, 79, 17, 66643, 13, 11]
[7, 2, 17, 241, 19, 5, 29, 23, 52673, 113, 5101, 127, 31, 1013, 97, 17327749, 83, 73859, 43]
[7, 2, 19, 271, 72091, 29, 3, 452117408867, 6959, 55691, 23, 659, 11141863, 11, 171881, 677, 31181, 313, 819493, 4871]

151004(2)

Ruby

Number of permutations of the multiset {1,1,2,2,....,n,n} with no two consecutive terms equal(2)

n が大きくなると、次のコードの方が断然速い。

def A114938(n)
  i = 2
  a, b = 0, 2
  ary = [a, b]
  while i < n
    i += 1
    a, b = b, i * (2 * i - 1) * b + i * (i - 1) * a
    ary << b
  end
  ary
end
ary = A114938(16)

# OEIS A114938のデータ
ary0 =
[0,2,30,864,39480,2631600,241133760,29083420800,
 4467125013120,851371260364800,197158144895712000,
 54528028997584665600,17752366094818747392000,
 6720318485119046923315200,
 2927066537906697348594432000,
 1453437879238150456164433920000]
# 一致の確認
p ary == ary0

151004

Ruby

Number of permutations of the multiset {1,1,2,2,....,n,n} with no two consecutive terms equal(1)

オンライン整数列大辞典の

A114938（http://oeis.org/A114938/list）

と比較し、答え合わせしてみる。

def ncr(n, r)
  return 1 if r == 0
  return (n - r + 1..n).inject(:*) / (1..r).inject(:*)
end

def f(n)
  s = 0
  # 包除原理を使用
  (0..n).each{|i| s += (-1) ** i * ncr(n, i) * (1..2 * n - i).inject(:*) / 2 ** (n - i)}
  s
end

def A114938(n)
  (1..n).map{|i| f(i)}
end
ary = A114938(16)

# OEIS A114938のデータ
ary0 =
[0,2,30,864,39480,2631600,241133760,29083420800,
 4467125013120,851371260364800,197158144895712000,
 54528028997584665600,17752366094818747392000,
 6720318485119046923315200,
 2927066537906697348594432000,
 1453437879238150456164433920000]
# 一致の確認
p ary == ary0

150929

Ruby

オイラー関数のベキ(3)

φ(x)^n の1≦n≦10のときについて、
オンライン整数列大辞典の
A010815（http://oeis.org/A010815/list）、
A002107（http://oeis.org/A002107/list）、
A010816（http://oeis.org/A010816/list）、
A000727（http://oeis.org/A000727/list）、
A000728（http://oeis.org/A000728/list）、

A000729（http://oeis.org/A000729/list）、

A000730（http://oeis.org/A000730/list）、

A000731（http://oeis.org/A000731/list）、

A010817（http://oeis.org/A010817/list）、

A010818（http://oeis.org/A010818/list）

と比較し、答え合わせしてみる。

# 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

# 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 phi_k(k, n)
  ary = [1]
  # 無限積のうち必要なところだけ取り出す
  (1..n).each{|i|
    b_ary = Array.new(i + 1, 0)
    b_ary[0], b_ary[-1] = 1, -1
    ary = mul(ary, b_ary, n)
  }
  # k乗
  power(ary, k, n)
end

def A010815(n)
  phi_k(1, n)
end
ary = A010815(92)

# OEIS A010815のデータ
ary0 =
[1,-1,-1,0,0,1,0,1,0,0,0,0,-1,0,0,-1,0,0,0,0,0,0,
 1,0,0,0,1,0,0,0,0,0,0,0,0,-1,0,0,0,0,-1,0,0,0,0,0,
 0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
 -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
# 一致の確認
p ary == ary0

def A002107(n)
  phi_k(2, n)
end
ary = A002107(77)

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

def A010816(n)
  phi_k(3, n)
end
ary = A010816(98)

# OEIS A010816のデータ
ary0 =
[1,-3,0,5,0,0,-7,0,0,0,9,0,0,0,0,-11,0,0,0,0,0,13,
 0,0,0,0,0,0,-15,0,0,0,0,0,0,0,17,0,0,0,0,0,0,0,0,
 -19,0,0,0,0,0,0,0,0,0,21,0,0,0,0,0,0,0,0,0,0,-23,
 0,0,0,0,0,0,0,0,0,0,0,25,0,0,0,0,0,0,0,0,0,0,0,0,
 -27,0,0,0,0,0,0,0]
# 一致の確認
p ary == ary0

def A000727(n)
  phi_k(4, n)
end
ary = A000727(81)

# OEIS A000727のデータ
ary0 =
[1,-4,2,8,-5,-4,-10,8,9,0,14,-16,-10,-4,0,-8,14,
 20,2,0,-11,20,-32,-16,0,-4,14,8,-9,20,26,0,2,-28,
 0,-16,16,-28,-22,0,14,16,0,40,0,-28,26,32,-17,0,
 -32,-16,-22,0,-10,32,-34,-8,14,0,45,-4,38,8,0,0,
 -34,-8,38,0,-22,-56,2,-28,0,0,-10,20,64,-40,-20,
 44]
# 一致の確認
p ary == ary0

def A000728(n)
  phi_k(5, n)
end
ary = A000728(56)

# OEIS A000728のデータ
ary0 =
[1,-5,5,10,-15,-6,-5,25,15,-20,9,-45,-5,25,20,10,
 15,20,-50,-35,-30,55,-50,15,80,1,50,-35,-45,-15,5,
 -50,-25,-55,85,51,50,10,-40,65,10,-10,-115,50,
 -115,-100,85,80,-30,5,20,45,70,65,45,-55,-100]
# 一致の確認
p ary == ary0

def A000729(n)
  phi_k(6, n)
end
ary = A000729(68)

# OEIS A000729のデータ
ary0 =
[1,-6,9,10,-30,0,11,42,0,-70,18,-54,49,90,0,-22,
 -60,0,-110,0,81,180,-78,0,130,-198,0,-182,-30,90,
 121,84,0,0,210,0,-252,-102,-270,170,0,0,-69,330,0,
 -38,420,0,-190,-390,0,-108,0,0,0,-300,99,442,210,
 0,418,-294,0,0,-510,378,-540,138,0]
# 一致の確認
p ary == ary0

def A000730(n)
  phi_k(7, n)
end
ary = A000730(45)

# OEIS A000730のデータ
ary0 =
[1,-7,14,7,-49,21,35,41,-49,-133,98,-21,126,112,
 -176,-105,-126,140,-35,147,259,98,-420,-224,238,
 -455,273,-14,322,406,-35,-7,-637,-196,245,-181,
 -574,462,147,924,217,-329,-140,-7,-371,-777]
# 一致の確認
p ary == ary0

def A000731(n)
  phi_k(8, n)
end
ary = A000731(60)

# OEIS A000731のデータ
ary0 =
[1,-8,20,0,-70,64,56,0,-125,-160,308,0,110,0,-520,
 0,57,560,0,0,182,-512,-880,0,1190,-448,884,0,0,0,
 -1400,0,-1330,1000,1820,0,-646,1280,0,0,-1331,
 -2464,380,0,1120,0,2576,0,0,-880,1748,0,-3850,0,
 -3400,0,2703,4160,-2500,0,3458]
# 一致の確認
p ary == ary0

def A010817(n)
  phi_k(9, n)
end
ary = A010817(40)

# OEIS A010817のデータ
ary0 =
[1,-9,27,-12,-90,135,54,-99,-189,-85,657,-162,
 -135,-171,-810,702,495,837,-673,-900,243,-1053,
 -297,1566,2700,-1764,81,-1188,-1377,270,-2043,
 3321,-756,3726,3015,-4563,-3348,504,-351,-1350,
 -468]
# 一致の確認
p ary == ary0

def A010818(n)
  phi_k(10, n)
end
ary = A010818(45)

# OEIS A010818のデータ
ary0 =
[1,-10,35,-30,-105,238,0,-260,-165,140,1054,-770,
 -595,0,-715,2162,455,0,-2380,-1820,2401,-680,1495,
 3080,1615,-6958,-1925,0,0,5100,-1442,8330,-5355,
 1330,0,-16790,0,8190,8265,0,1918,0,8415,-10230,
 -7140,-9362]
# 一致の確認
p ary == ary0

出力結果

true
true
true
true
true
true
true
true
true
true

150927(2)

Ruby

オイラー関数のベキ(2)

φ(x)^n の最初の方を出力してみた。
また、「ラマヌジャンの遺した関数」の3.8 において、
φ(x)^n の最初の方の，たとえば500個の，係数の中の0の数を求めることは，
単純なコンピュータ・プログラムの問題である
と書いてあったので、この個数も出力してみた。

# -*- coding: cp932 -*-

# 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

# 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 phi_k(k, n)
  ary = [1]
  # 無限積のうち必要なところだけ取り出す
  (1..n).each{|i|
    b_ary = Array.new(i + 1, 0)
    b_ary[0], b_ary[-1] = 1, -1
    ary = mul(ary, b_ary, n)
  }
  # k乗
  power(ary, k, n)
end

(1..35).each{|k| p [k, phi_k(k, 50)]}
puts "500次までに現れる0の個数"
(1..35).each{|k| p [k, phi_k(k, 500).count(0)]}

出力結果

[1, [1, -1, -1, 0, 0, 1, 0, 1, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
[2, [1, -2, -1, 2, 1, 2, -2, 0, -2, -2, 1, 0, 0, 2, 3, -2, 2, 0, 0, -2, -2, 0, 0, -2, -1, 0, 2, 2, -2, 2, 1, 2, 0, 2, -2, -2, 2, 0, -2, 0, -4, 0, 0, 0, 1, -2, 0, 0, 2, 0, 2]]
[3, [1, -3, 0, 5, 0, 0, -7, 0, 0, 0, 9, 0, 0, 0, 0, -11, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 0, -15, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, -19, 0, 0, 0, 0, 0]]
[4, [1, -4, 2, 8, -5, -4, -10, 8, 9, 0, 14, -16, -10, -4, 0, -8, 14, 20, 2, 0, -11, 20, -32, -16, 0, -4, 14, 8, -9, 20, 26, 0, 2, -28, 0, -16, 16, -28, -22, 0, 14, 16, 0, 40, 0, -28, 26, 32, -17, 0, -32]]
[5, [1, -5, 5, 10, -15, -6, -5, 25, 15, -20, 9, -45, -5, 25, 20, 10, 15, 20, -50, -35, -30, 55, -50, 15, 80, 1, 50, -35, -45, -15, 5, -50, -25, -55, 85, 51, 50, 10, -40, 65, 10, -10, -115, 50, -115, -100, 85, 80, -30, 5, 20]]
[6, [1, -6, 9, 10, -30, 0, 11, 42, 0, -70, 18, -54, 49, 90, 0, -22, -60, 0, -110, 0, 81, 180, -78, 0, 130, -198, 0, -182, -30, 90, 121, 84, 0, 0, 210, 0, -252, -102, -270, 170, 0, 0, -69, 330, 0, -38, 420, 0, -190, -390, 0]]
[7, [1, -7, 14, 7, -49, 21, 35, 41, -49, -133, 98, -21, 126, 112, -176, -105, -126, 140, -35, 147, 259, 98, -420, -224, 238, -455, 273, -14, 322, 406, -35, -7, -637, -196, 245, -181, -574, 462, 147, 924, 217, -329, -140, -7, -371, -777, 588, -560, -196, -489, 1246]]
[8, [1, -8, 20, 0, -70, 64, 56, 0, -125, -160, 308, 0, 110, 0, -520, 0, 57, 560, 0, 0, 182, -512, -880, 0, 1190, -448, 884, 0, 0, 0, -1400, 0, -1330, 1000, 1820, 0, -646, 1280, 0, 0, -1331, -2464, 380, 0, 1120, 0, 2576, 0, 0, -880, 1748]]
[9, [1, -9, 27, -12, -90, 135, 54, -99, -189, -85, 657, -162, -135, -171, -810, 702, 495, 837, -673, -900, 243, -1053, -297, 1566, 2700, -1764, 81, -1188, -1377, 270, -2043, 3321, -756, 3726, 3015, -4563, -3348, 504, -351, -1350, -468, -891, 7074, 1611, 2700, -2423, -1512, -3267, -5265, -1800, 3510]]
[10, [1, -10, 35, -30, -105, 238, 0, -260, -165, 140, 1054, -770, -595, 0, -715, 2162, 455, 0, -2380, -1820, 2401, -680, 1495, 3080, 1615, -6958, -1925, 0, 0, 5100, -1442, 8330, -5355, 1330, 0, -16790, 0, 8190, 8265, 0, 1918, 0, 8415, -10230, -7140, -9362, -7315, 10010, 0, 14260, 14641]]
[11, [1, -11, 44, -55, -110, 374, -143, -462, 55, 495, 1287, -2069, -902, 1210, -275, 3795, -1507, -2431, -3575, -385, 8690, -1661, 1143, 1265, -4290, -12716, 2299, 11440, 3905, 8635, -10472, 6105, -20548, -1540, 8690, -24904, 29634, 25003, 8470, -23320, -18183, -4741, 2420, -19195, 2200, 18271, 5643, 52382, -14520, 990, -12287]]
[12, [1, -12, 54, -88, -99, 540, -418, -648, 594, 836, 1056, -4104, -209, 4104, -594, 4256, -6480, -4752, -298, 5016, 17226, -12100, -5346, -1296, -9063, -7128, 19494, 29160, -10032, -7668, -34738, 8712, -22572, 21812, 49248, -46872, 67562, 2508, -47520, -76912, -25191, 67716, 32076, 7128, 29754, 36784, -51072, 45144, -122398, -53460, 11286]]
[13, [1, -13, 65, -130, -65, 728, -871, -715, 1560, 845, 78, -6513, 2730, 8605, -4355, 2483, -13299, -2275, 11440, 10010, 19734, -41834, -11375, 12870, -2730, 14911, 33201, 25155, -70070, -36595, -28925, 64389, 13650, 52780, 72215, -173693, 87867, -62920, -111865, -25870, 89908, 284505, -37895, -88660, -59995, -57759, -172081, 117390, -121550, 61490, 301041]]
[14, [1, -14, 77, -182, 0, 924, -1547, -506, 3003, 0, -1729, -8372, 9177, 13090, -15625, 0, -17017, 10556, 30107, 0, 7084, -89206, 11571, 69160, 0, 27132, 0, -19096, -153502, 0, 93093, 165242, 0, -38962, 0, -420838, 257439, 0, -76153, 218750, 168245, 397320, -638066, -399126, 0, 67158, 92092, 530348, 0, 0, 424879]]
[15, [1, -15, 90, -245, 105, 1107, -2485, 195, 4860, -2420, -3990, -8190, 19695, 13755, -38475, 3990, -9750, 34020, 43015, -46605, -13860, -127385, 106485, 165240, -79275, -16380, -92340, -35840, -151995, 188550, 315783, 90090, -271215, -307485, 20475, -505440, 915385, 209340, -284130, 337645, -294225, 269325, -1707970, -70305, 1297620, 574210, 492765, 251370, -847245, -1102725, 438129]]
[16, [1, -16, 104, -320, 260, 1248, -3712, 1664, 6890, -7280, -5568, -4160, 33176, 4640, -74240, 29824, 14035, 54288, 27040, -142720, 1508, -110240, 289536, 222720, -380770, -83200, -123904, 142912, 7640, 408000, 386048, -530816, -755943, -294320, 716560, -194688, 1843200, -250432, -1688960, 324480, -988858, 1025440, -2283008, 1963520, 3857360, -1118240, -965120, -2204800, -2004730, -976720, 3450304]]
[17, [1, -17, 119, -408, 476, 1309, -5236, 4233, 8602, -15470, -4250, 5236, 45815, -21182, -117776, 101065, 46767, 36685, -36771, -267036, 143514, -18241, 486285, 81753, -1007250, 104006, 165767, 579292, 78829, 187510, 60214, -1706885, -616539, 956879, 2210985, -450109, 1609730, -2449615, -4158149, 2521015, -86275, 3856314, -3279895, 3835982, 4922435, -9624346, -2911454, -2670955, 2759372, 4788186, 8763296]]
[18, [1, -18, 135, -510, 765, 1242, -7038, 8280, 9180, -27710, 3519, 20196, 50370, -68850, -153765, 244782, 52785, -71010, -130525, -343620, 517293, 54978, 498780, -390150, -1835865, 1161270, 896751, 793730, -633420, -906660, -75582, -2589984, 1523745, 3589380, 2472615, -3740850, -767039, -4649670, -4222800, 11166210, 1718937, 4728294, -10403235, 2349450, 5331285, -23826622, 6799950, 7601040, 14132100, 7375230, -989604]]
[19, [1, -19, 152, -627, 1140, 988, -9063, 14212, 7410, -44270, 22781, 38114, 36176, -137256, -154850, 480605, -46493, -316065, -153406, -254525, 1156948, -184927, 88483, -1051042, -2381650, 3838874, 1417039, -542146, -2649911, -2171510, 2131306, -2282489, 5694509, 5022973, -2849050, -10735551, -1364789, -88825, 1790369, 24936550, -6189326, -6533150, -25397471, 6233254, 19679725, -38263549, 39975430, 19318117, 5441714, -16667750, -38728042]]
[20, [1, -20, 170, -760, 1615, 476, -11210, 22440, 1615, -64600, 60002, 51680, -9520, -213180, -83980, 803528, -379525, -692360, 119700, 80920, 1899830, -1235360, -755990, -1200040, -1981435, 8388956, -361760, -5068440, -4585935, -788120, 9421910, -2949160, 8315255, 768740, -16070560, -13715512, 10200340, 16428540, 5608780, 28549800, -40127031, -28504580, -23992440, 43014080, 60146875, -77059100, 80840440, -5335960, -56174545, -45601520, -56122066]]
[21, [1, -21, 189, -910, 2205, -378, -13321, 33345, -10395, -86870, 122703, 46683, -98287, -264915, 96390, 1163064, -1113588, -1066527, 1042055, 536025, 2287467, -3603805, -1391733, 478170, -562555, 13742379, -7889805, -12745348, -1009470, 6926850, 21064883, -13691664, 4004343, -8355270, -30343950, 5444712, 39441969, 30902949, -22027005, 4899895, -91000161, -20752011, 44496424, 116926740, 78003135, -226108554, 116695530, -60695838, -129044790, 45585540, 12284811]]
[22, [1, -22, 209, -1078, 2926, -1672, -15169, 47234, -31350, -107426, 218680, -266, -234707, -237006, 405878, 1444806, -2415413, -1091398, 3018169, 523050, 1618309, -7344304, -134905, 5365866, 5852, 17297588, -24278276, -18767364, 17865419, 19729952, 27154743, -49645442, -3483403, -4925446, -31064495, 61081922, 61961867, -55594, -108218187, -18341400, -88377696, 77121660, 185417067, 120639398, -58813391, -545883338, 294675997, 2967910, -128962680, 344990030, 286748]]
[23, [1, -23, 230, -1265, 3795, -3519, -16445, 64285, -64515, -120175, 354706, -123763, -407560, -48530, 817190, 1464341, -4376693, -135355, 6303955, -1282710, -682088, -11372603, 5678585, 13479425, -5451115, 16579596, -48805655, -11515065, 61570080, 21234520, 7731427, -119019296, 17214120, 46163645, -22347260, 134763417, 9991982, -115146395, -208431980, 72814665, 62601078, 221269499, 248467505, -164778900, -396525635, -820862617, 1040502519, 303756860, -310026775, 615008615, -577640492]]
[24, [1, -24, 252, -1472, 4830, -6048, -16744, 84480, -113643, -115920, 534612, -370944, -577738, 401856, 1217160, 987136, -6905934, 2727432, 10661420, -7109760, -4219488, -12830688, 18643272, 21288960, -25499225, 13865712, -73279080, 24647168, 128406630, -29211840, -52843168, -196706304, 134722224, 165742416, -80873520, 167282496, -182213314, -255874080, -145589976, 408038400, 308120442, 101267712, -17125708, -786948864, -548895690, -447438528, 2687348496, 248758272, -1696965207, 611981400, -1740295368]]
[25, [1, -25, 275, -1700, 6050, -9405, -15550, 107525, -182875, -81675, 756655, -801550, -662975, 1220175, 1361350, -209440, -9601900, 8608900, 14889050, -19948500, -6262465, -7057550, 38788925, 19716425, -69119875, 23579969, -82427400, 98068850, 191984400, -192983175, -128640655, -199535875, 424794500, 284736850, -398127725, 141193525, -454458725, -190957250, 306041450, 867327675, 248309215, -781592900, -498119600, -1140582625, 331248600, 951687880, 4441237625, -2000633400, -5357206250, 1875749425, -1810005816]]
[26, [1, -26, 299, -1950, 7475, -13754, -12220, 132756, -276575, 0, 1010100, -1486030, -519961, 2486300, 829725, -2215486, -11643060, 18523050, 16317925, -42861650, 0, 11010090, 59644221, -5743400, -138219900, 79631474, -64447293, 190305726, 197368275, -523231800, -99201921, 0, 873014519, 160509700, -1222259675, 305612684, -511748120, 355081636, 1089106200, 759784300, -698434100, -2494548030, 0, 0, 2468263525, 2158297050, 3767134280, -8192279446, -9594939900, 9772308650, 1157638599]]
[27, [1, -27, 324, -2223, 9126, -19278, -5967, 159030, -399087, 151593, 1270971, -2500875, 74970, 4203522, -1004157, -4796037, -11750778, 32885190, 10452375, -77533092, 27104868, 43070625, 63798840, -69960267, -215939061, 236414349, -37046646, 237487433, 85921371, -1008703449, 286178139, 474257484, 1224628470, -608265126, -2606289075, 1473758712, 10716732, 1192052160, 1464312006, -1064732643, -2341040562, -3747291822, 3750796530, 2904349500, 3309301413, -30203550, -1508652000, -15903743310, -7320117141, 31078702161, 1804201776]]
[28, [1, -28, 350, -2520, 11025, -26180, 4158, 184600, -554400, 401100, 1496964, -3920280, 1444625, 6224400, -4972350, -7121296, -8308965, 50796900, -8971200, -121968000, 94011435, 80598288, 20282500, -175228200, -254651775, 554394204, -88470242, 133725200, -133867445, -1515976700, 1369368000, 1033213272, 879369575, -2314141200, -3980458300, 5107622936, 781936407, 910872900, 222868800, -5087226200, -2187994564, -1973664000, 11996468950, 3892051800, -3360359625, -6947241084, -7654070088, -15374268000, 9869832000, 62945277200, -22144800636]]
[29, [1, -29, 377, -2842, 13195, -34684, 19285, 206973, -745706, 782275, 1621564, -5803161, 4026360, 8149841, -12056025, -7428263, 254504, 69194580, -49156653, -167517050, 224634319, 94868280, -112333182, -288914501, -172722550, 1061590530, -420678727, -212254364, -271663242, -1795846200, 3413927270, 967351840, -978399506, -4524424502, -3825362450, 12725565255, -657413528, -3315667498, -2494031813, -9144119775, 5035400442, 3578388387, 20759047670, -5893341662, -22777727375, -8797952807, -1616838769, 3681888314, 36274904939, 80118476175, -103728485744]]
[30, [1, -30, 405, -3190, 15660, -45036, 40745, 222750, -974835, 1334580, 1547469, -8174520, 8380245, 9200250, -23243355, -2643380, 14704740, 82050570, -116275500, -195804810, 442809990, 25147930, -371898000, -313802910, 125394405, 1688931000, -1364323095, -737497840, 158838945, -1653918750, 6309965146, -1076120370, -4802530500, -5257026620, -47508120, 24290828532, -10318690855, -13910780610, -1364146515, -7675874280, 24023587500, 5245892100, 18578165165, -33913100250, -47491260255, 23066963660, 27308816280, 29296187730, 36536324105, 44794138050, -245483273862]]
[31, [1, -31, 434, -3565, 18445, -57505, 70091, 227447, -1241550, 2102730, 1139498, -11000164, 15185009, 8060465, -39266925, 11975548, 33735905, 79961555, -212042635, -176681400, 762467041, -231771190, -762218948, -59474275, 687626655, 2193123086, -3317871844, -996975686, 1948141060, -1380351105, 9298132746, -6788705842, -9608214462, -500684100, 8195740630, 35945695112, -37464288578, -27703334946, 18233392140, 3452352820, 50110166442, -18648267155, -5426442244, -68394536935, -47776054550, 125566716471, 51003097355, 3739338358, -34904617090, -37022572120, -360301225363]]
[32, [1, -32, 464, -3968, 21576, -72384, 109120, 215296, -1542684, 3135712, 217248, -14153856, 25215616, 2704192, -60182656, 43083520, 52111434, 50631680, -328746320, -68928128, 1172526144, -825260672, -1202344640, 768450816, 1395312728, 2106191584, -6556788640, 100803072, 5930017280, -2446579520, 11062835584, -17191741952, -11762712973, 14959546528, 16880156208, 38804082816, -90268764128, -27924752384, 79537896320, 11907174400, 59476916292, -96945887328, -36151163360, -58860723712, 11806125312, 301046180224, -41929489920, -152538292480, -142811793922, -40571481632, -282758291200]]
[33, [1, -33, 495, -4400, 25080, -89991, 159896, 179025, -1871100, 4485140, -1452132, -17376120, 39295135, -9791100, -84751920, 99240515, 58170882, -19058490, -443044250, 173982600, 1617603372, -1940174742, -1456327455, 2535117750, 1782559240, 783282456, -10878123663, 4453210080, 12274486950, -8274669480, 10738181916, -30949593906, -4649643405, 44427298525, 12632491905, 22022095887, -166221342056, 21965133795, 201364886250, -36031327805, 13370409459, -232741171476, 2257921270, 73994101500, 103475478645, 461792586948, -436927039032, -414115099695, -36601699750, 242404463730, 31750490970]]
[34, [1, -34, 527, -4862, 28985, -110670, 224774, 109616, -2214454, 6202790, -4160563, -20224152, 58212420, -33421286, -109592285, 190464702, 30766260, -138537388, -509479358, 590424450, 1978075528, -3762986788, -1052300952, 5565993766, 814913275, -2348596580, -15108004380, 14570701530, 19246124150, -24572149690, 10398722367, -42736429098, 19198424003, 83788921020, -29646853725, -16183052760, -240028781751, 173007827374, 367539275460, -257643143340, -99099230160, -344243246886, 252100115707, 356338645124, 24177692825, 446603464544, -1249233123069, -441921135810, 765164623614, 771325632000, 152306691108]]
[35, [1, -35, 560, -5355, 33320, -134792, 306425, -3960, -2553740, 8337140, -8264431, -22012620, 82596080, -73399200, -128071540, 327108117, -64156470, -305606350, -455573580, 1186922730, 2056498976, -6416740355, 788588570, 9925006980, -3311307160, -7223330464, -16617037990, 32704289240, 21589314305, -58378128620, 19258974280, -43471191470, 61914761755, 115717397495, -142117772440, -48251561329, -258673133355, 462387945810, 485243715915, -824196278360, -158905982564, -216715690380, 829306675115, 595583270100, -665090670370, 246500217957, -2246704399660, 504524131615, 2608529471870, 601239063870, -912722944252]]
500次までに現れる0の個数
[1, 464]
[2, 243]
[3, 469]
[4, 158]
[5, 0]
[6, 212]
[7, 0]
[8, 250]
[9, 0]
[10, 151]
[11, 0]
[12, 0]
[13, 0]
[14, 172]
[15, 2]
[16, 0]
[17, 0]
[18, 0]
[19, 0]
[20, 0]
[21, 0]
[22, 0]
[23, 0]
[24, 0]
[25, 0]
[26, 80]
[27, 0]
[28, 0]
[29, 0]
[30, 0]
[31, 0]
[32, 0]
[33, 0]
[34, 0]
[35, 0]