190519

Ruby

F_2(q) and F_3(q)

B. Mazur, Perturbations, deformations and variations (and "near-misses") in geometry, physics, and number theory

に載っているF_2 およびF_3 を計算してみた。 

require 'prime'

def power0(a, n)
  return 1 if n == 0
  k = power0(a, n >> 1)
  k *= k
  return k if n & 1 == 0
  return k * a
end

# x > 0
def sigma(x, i)
  sum = 1
  pq = i.prime_division
  pq.each{|a, n| sum *= (power0(a, (n + 1) * x) - 1) / (power0(a, x) - 1)}
  sum
end

def bernoulli(n)
  ary = []
  a = []
  (0..n).each{|i|
    a << 1r / (i + 1)
    i.downto(1){|j| a[j - 1] = j * (a[j - 1] - a[j])}
    ary << a[0] # Bn = a[0]
  }
  ary
end

def E_2k(k, n)
  a = -4 * k / bernoulli(2 * k)[-1]
  b = a.denominator
  c = a.numerator
  [b] + (1..n).map{|i| c * sigma(2 * k - 1, i)}
end

# 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 A(a, b, c, s, t, u, n)
  mul(mul(power(a, s, n), power(b, t, n), n), power(c, u, n), n)
end

def A126858(a, b, c, n)
  a1 = A(a, b, c, 3, 0, 0, n)
  a2 = A(a, b, c, 1, 1, 0, n)
  a3 = A(a, b, c, 0, 0, 1, n)
  (0..n).map{|i| (5 * a1[i] - 3 * a2[i] - 2 * a3[i]) / 51840}
end

def F_3(a, b, c, n)
  a1 = A(a, b, c, 4, 1, 0, n)
  a2 = A(a, b, c, 6, 0, 0, n)
  a3 = A(a, b, c, 2, 2, 0, n)
  a4 = A(a, b, c, 0, 3, 0, n)
  a5 = A(a, b, c, 3, 0, 1, n)
  a6 = A(a, b, c, 1, 1, 1, n)
  a7 = A(a, b, c, 0, 0, 2, n)
  (0..n).map{|i| (15 * a1[i] - 6 * a2[i] - 12 * a3[i] + 7 * a4[i] + 4 * a5[i] - 12 * a6[i] + 4 * a7[i]) / 35831808r}
end

n = 100
a = E_2k(1, n)
b = E_2k(2, n)
c = E_2k(3, n)
p A126858(a, b, c, n)
p F_3(a, b, c, n)

出力結果
[0, 0, 1, 8, 30, 80, 180, 336, 620, 960, 1590, 2200, 3416, 4368, 6440, 7920, 11160, 13056, 18333, 20520, 27860, 31360, 41052, 44528, 59760, 62400, 80990, 87120, 109872, 113680, 147960, 148800, 188976, 196416, 240210, 243040, 311910, 303696, 376580, 385840, 467400, 459200, 578592, 556248, 685960, 689040, 814200, 795616, 1000928, 940800, 1142575, 1138320, 1346436, 1289808, 1597320, 1502160, 1815520, 1781440, 2071470, 1984760, 2474640, 2269200, 2709152, 2665488, 3108960, 2941120, 3587760, 3307656, 3968412, 3841920, 4433520, 4174800, 5145660, 4667328, 5518550, 5396600, 6208440, 5785472, 7030296, 6408480, 7665680, 7318080, 8336202, 7813288, 9580480, 8641440, 10093820, 9750960, 11196240, 10338240, 12560670, 11313120, 13383056, 12745216, 14427120, 13505200, 16390080, 14601216, 17071257, 16382520, 18802050]
[(0/1), (0/1), (1/12), (20/3), (102/1), (2288/3), (3773/1), (14232/1), (133616/3), (119904/1), (584517/2), (1927900/3), (4013432/3), (2569296/1), (14394518/3), (8365192/1), (14426496/1), (23381600/1), (151885575/4), (58125708/1), (269849564/3), (395149888/3), (195967551/1), (828880856/3), (398774464/1), (544543680/1), (4586626939/6), (1018905048/1), (1396485648/1), (5453010736/3), (2448671142/1), (3121442400/1), (4128375808/1), (5187906080/1), (13495484403/2), (25020191728/3), (10739989086/1), (13073496336/1), (49818496739/3), (60139107448/3), (25150090080/1), (89915259200/3), (37377803512/1), (44031127764/1), (163015794472/3), (63689848272/1), (77792286390/1), (270800856112/3), (329864101376/3), (126331201920/1), (1829900154535/12), (174829519992/1), (209303207172/1), (237830107920/1), (284352406578/1), (320567905752/1), (1141395757696/3), (1285519158688/3), (1009346752689/2), (1692885599372/3), (665140467376/1), (738055938000/1), (2591163670808/3), (959464286328/1), (1115821891584/1), (3692188459456/3), (1432795280676/1), (1570557014940/1), (1818030330092/1), (1995407460928/1), (2295038099676/1), (2504195399000/1), (2888008439184/1), (3131191652832/1), (21533911590655/6), (11708697709580/3), (4449903597384/1), (14425877365952/3), (5497041209758/1), (5909603218032/1), (20169906407168/3), (7246380240288/1), (16391092220607/2), (26370350052964/3), (29945483611456/3), (10645119258336/1), (36058977478421/3), (12870138877544/1), (14466994073664/1), (15402512851936/1), (34752009094569/2), (18413605256592/1), (62040662272400/3), (65985397699840/3), (24568961270988/1), (78053912323960/3), (29202477969408/1), (30753913227744/1), (137364461667811/4), (36345626985348/1), (40420330609290/1)]

190420

Ruby

Expansion of g.f. 1/((1-x)^k-x^k)

A306915 に書いたとおり第n 項は
Sum_{j=0..floor(n/k)} binomial(n+k-1,k*j+k-1)
で表される。

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

def A(k, n)
  (0..n / k).inject(0){|s, i| s + ncr(n + k - 1, k * i + k - 1)}
end

n = 50
(1..n).each{|i| p [i, (0..10).map{|j| A(i, j)}]}

出力結果
[1, [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]]
[2, [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]]
[3, [1, 3, 6, 11, 21, 42, 85, 171, 342, 683, 1365]]
[4, [1, 4, 10, 20, 36, 64, 120, 240, 496, 1024, 2080]]
[5, [1, 5, 15, 35, 70, 127, 220, 385, 715, 1430, 3004]]
[6, [1, 6, 21, 56, 126, 252, 463, 804, 1365, 2366, 4368]]
[7, [1, 7, 28, 84, 210, 462, 924, 1717, 3017, 5110, 8568]]
[8, [1, 8, 36, 120, 330, 792, 1716, 3432, 6436, 11456, 19584]]
[9, [1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24311, 43776]]
[10, [1, 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, 92379]]
[11, [1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758, 92378, 184756]]
[12, [1, 12, 78, 364, 1365, 4368, 12376, 31824, 75582, 167960, 352716]]
[13, [1, 13, 91, 455, 1820, 6188, 18564, 50388, 125970, 293930, 646646]]
[14, [1, 14, 105, 560, 2380, 8568, 27132, 77520, 203490, 497420, 1144066]]
[15, [1, 15, 120, 680, 3060, 11628, 38760, 116280, 319770, 817190, 1961256]]
[16, [1, 16, 136, 816, 3876, 15504, 54264, 170544, 490314, 1307504, 3268760]]
[17, [1, 17, 153, 969, 4845, 20349, 74613, 245157, 735471, 2042975, 5311735]]
[18, [1, 18, 171, 1140, 5985, 26334, 100947, 346104, 1081575, 3124550, 8436285]]
[19, [1, 19, 190, 1330, 7315, 33649, 134596, 480700, 1562275, 4686825, 13123110]]
[20, [1, 20, 210, 1540, 8855, 42504, 177100, 657800, 2220075, 6906900, 20030010]]
[21, [1, 21, 231, 1771, 10626, 53130, 230230, 888030, 3108105, 10015005, 30045015]]
[22, [1, 22, 253, 2024, 12650, 65780, 296010, 1184040, 4292145, 14307150, 44352165]]
[23, [1, 23, 276, 2300, 14950, 80730, 376740, 1560780, 5852925, 20160075, 64512240]]
[24, [1, 24, 300, 2600, 17550, 98280, 475020, 2035800, 7888725, 28048800, 92561040]]
[25, [1, 25, 325, 2925, 20475, 118755, 593775, 2629575, 10518300, 38567100, 131128140]]
[26, [1, 26, 351, 3276, 23751, 142506, 736281, 3365856, 13884156, 52451256, 183579396]]
[27, [1, 27, 378, 3654, 27405, 169911, 906192, 4272048, 18156204, 70607460, 254186856]]
[28, [1, 28, 406, 4060, 31465, 201376, 1107568, 5379616, 23535820, 94143280, 348330136]]
[29, [1, 29, 435, 4495, 35960, 237336, 1344904, 6724520, 30260340, 124403620, 472733756]]
[30, [1, 30, 465, 4960, 40920, 278256, 1623160, 8347680, 38608020, 163011640, 635745396]]
[31, [1, 31, 496, 5456, 46376, 324632, 1947792, 10295472, 48903492, 211915132, 847660528]]
[32, [1, 32, 528, 5984, 52360, 376992, 2324784, 12620256, 61523748, 273438880, 1121099408]]
[33, [1, 33, 561, 6545, 58905, 435897, 2760681, 15380937, 76904685, 350343565, 1471442973]]
[34, [1, 34, 595, 7140, 66045, 501942, 3262623, 18643560, 95548245, 445891810, 1917334783]]
[35, [1, 35, 630, 7770, 73815, 575757, 3838380, 22481940, 118030185, 563921995, 2481256778]]
[36, [1, 36, 666, 8436, 82251, 658008, 4496388, 26978328, 145008513, 708930508, 3190187286]]
[37, [1, 37, 703, 9139, 91390, 749398, 5245786, 32224114, 177232627, 886163135, 4076350421]]
[38, [1, 38, 741, 9880, 101270, 850668, 6096454, 38320568, 215553195, 1101716330, 5178066751]]
[39, [1, 39, 780, 10660, 111930, 962598, 7059052, 45379620, 260932815, 1362649145, 6540715896]]
[40, [1, 40, 820, 11480, 123410, 1086008, 8145060, 53524680, 314457495, 1677106640, 8217822536]]
[41, [1, 41, 861, 12341, 135751, 1221759, 9366819, 62891499, 377348994, 2054455634, 10272278170]]
[42, [1, 42, 903, 13244, 148995, 1370754, 10737573, 73629072, 450978066, 2505433700, 12777711870]]
[43, [1, 43, 946, 14190, 163185, 1533939, 12271512, 85900584, 536878650, 3042312350, 15820024220]]
[44, [1, 44, 990, 15180, 178365, 1712304, 13983816, 99884400, 636763050, 3679075400, 19499099620]]
[45, [1, 45, 1035, 16215, 194580, 1906884, 15890700, 115775100, 752538150, 4431613550, 23930713170]]
[46, [1, 46, 1081, 17296, 211876, 2118760, 18009460, 133784560, 886322710, 5317936260, 29248649430]]
[47, [1, 47, 1128, 18424, 230300, 2349060, 20358520, 154143080, 1040465790, 6358402050, 35607051480]]
[48, [1, 48, 1176, 19600, 249900, 2598960, 22957480, 177100560, 1217566350, 7575968400, 43183019880]]
[49, [1, 49, 1225, 20825, 270725, 2869685, 25827165, 202927725, 1420494075, 8996462475, 52179482355]]
[50, [1, 50, 1275, 22100, 292825, 3162510, 28989675, 231917400, 1652411475, 10648873950, 62828356305]]

190311(2)

Ruby

33

33 is the sum of three cubes

ということが示されたようだ。

def A(a, b, c)
  a ** 3 + b ** 3 + c ** 3
end

# OEIS A060465のデータ
ary0 =
[0,0,0,1,-1,0,0,0,1,-2,7,-1,-511,1,-1,0,1,-11,
 -2901096694,-1,0,0,0,1,-283059965,
 -2736111468807040,-1,0,1,0,1,117367]
# OEIS A060466のデータ
ary1 =
[0,0,1,1,-1,-1,0,1,1,-2,10,2,-1609,2,-2,-2,-2,-14,
 -15550555555,-1,-1,0,1,1,-2218888517,
 -8778405442862239,2,2,2,-3,-3,134476]
# OEIS A060467のデータ
ary2 =
[0,1,1,1,2,2,2,2,2,3,-11,2,1626,2,3,3,3,16,
 15584139827,3,3,3,3,3,2220422932,8866128975287528,
 3,3,3,4,4,-159380]

p (0..31).map{|i| A(ary0[i], ary1[i], ary2[i])}

出力結果
[0, 1, 2, 3, 6, 7, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 21, 24, 25, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 39]

190311

Ruby

A306646

Lucas数列, Perrin数列, ... , を出力してみた。

def A(k, n)
  a = [k + 1] + Array.new(k - 1, 0) + [k]
  ary = [k + 1]
  while ary.size < n + 1
    a = *a[1..-1], a[0] + a[1]
    ary << a[0]
  end
  ary
end

n = 30
(1..10).each{|i| p [i, A(i, n)]}

出力結果
[1, [2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498]]
[2, [3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853, 1130, 1497, 1983, 2627, 3480, 4610]]
[3, [4, 0, 0, 3, 4, 0, 3, 7, 4, 3, 10, 11, 7, 13, 21, 18, 20, 34, 39, 38, 54, 73, 77, 92, 127, 150, 169, 219, 277, 319, 388]]
[4, [5, 0, 0, 0, 4, 5, 0, 0, 4, 9, 5, 0, 4, 13, 14, 5, 4, 17, 27, 19, 9, 21, 44, 46, 28, 30, 65, 90, 74, 58, 95]]
[5, [6, 0, 0, 0, 0, 5, 6, 0, 0, 0, 5, 11, 6, 0, 0, 5, 16, 17, 6, 0, 5, 21, 33, 23, 6, 5, 26, 54, 56, 29, 11]]
[6, [7, 0, 0, 0, 0, 0, 6, 7, 0, 0, 0, 0, 6, 13, 7, 0, 0, 0, 6, 19, 20, 7, 0, 0, 6, 25, 39, 27, 7, 0, 6]]
[7, [8, 0, 0, 0, 0, 0, 0, 7, 8, 0, 0, 0, 0, 0, 7, 15, 8, 0, 0, 0, 0, 7, 22, 23, 8, 0, 0, 0, 7, 29, 45]]
[8, [9, 0, 0, 0, 0, 0, 0, 0, 8, 9, 0, 0, 0, 0, 0, 0, 8, 17, 9, 0, 0, 0, 0, 0, 8, 25, 26, 9, 0, 0, 0]]
[9, [10, 0, 0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0, 0, 0, 0, 9, 19, 10, 0, 0, 0, 0, 0, 0, 9, 28, 29, 10]]
[10, [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 11, 0, 0, 0, 0, 0, 0, 0, 0, 10, 21, 11, 0, 0, 0, 0, 0, 0, 0, 10]]

190225

Ruby

A076408

べき乗数を小さい順に足していくと、2019が出てくることを確認してみる。

# OEIS A001597のデータ
ary =
[1,4,8,9,16,25,27,32,36,49,64,81,100,121,125,128,
 144,169,196,216,225,243,256,289,324,343,361,400,
 441,484,512,529,576,625,676,729,784,841,900,961,
 1000,1024,1089,1156,1225,1296,1331,1369,1444,1521,
 1600,1681,1728,1764]
p ary[0..21].inject(:+)

出力結果
2019

190103

Ruby


A320843(1)

出力してみた。

def search(a, num, n)
  if num == n + 1
    @cnt += 1
  else
    (1..n).each{|i|
      if a[i] == 0
        if num % i == 0 || i % num == 0
          a[i] = num
          search(a, num + 1, n)
          a[i] = 0
        end
      end
    }
  end
end

def A(n)
  a = [0] * (n + 1)
  @cnt = 0
  search(a, 1, n)
  @cnt
end

p (0..20).map{|i| A(i)}

出力結果
 [1, 1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679, 87328, 90478, 435812, 449586, 1939684]

181224

Ruby


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

150927(2)分で

500次までに現れる0の個数を出力したが、

係数が0となる次数（<= 500）を出力してみた。

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

def A(m, n)
  ary = [1]
  a = [0] + (1..n).map{|i| s(i)}
  (1..n).each{|i| ary << (1..i).inject(0){|s, j| s - m * a[j] * ary[-j]} / i}
  ary
end

def B(k, n)
  a = A(k, n)
  (0..n).select{|i| a[i] == 0}
end

n = 500
[1, 2, 3, 4, 5, 6, 8, 10, 14, 15, 26].each{|i|
  j = B(i, n)
  p [i, j.size, j]
}

出力結果
[1, 464, [3, 4, 6, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19, 20, 21, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 96, 97, 98, 99, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 118, 119, 120, 121, 122, 123, 124, 125, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 146, 147, 148, 149, 150, 151, 152, 153, 154, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 496, 497, 498, 499, 500]]
[2, 243, [7, 11, 12, 17, 18, 21, 22, 25, 32, 37, 39, 41, 42, 43, 46, 47, 49, 54, 57, 58, 60, 62, 65, 67, 68, 72, 74, 75, 76, 81, 82, 87, 88, 90, 92, 95, 97, 98, 99, 106, 107, 109, 111, 112, 113, 116, 117, 120, 122, 123, 125, 126, 128, 130, 132, 136, 137, 142, 143, 144, 147, 153, 157, 158, 159, 160, 162, 163, 164, 165, 167, 172, 173, 175, 177, 179, 181, 182, 186, 187, 192, 193, 194, 197, 201, 204, 205, 207, 208, 211, 212, 214, 215, 217, 219, 220, 221, 222, 228, 230, 231, 232, 235, 237, 239, 240, 241, 242, 244, 245, 247, 251, 256, 257, 258, 262, 263, 266, 267, 270, 272, 273, 274, 277, 278, 279, 282, 283, 284, 285, 287, 291, 292, 296, 297, 302, 304, 305, 307, 312, 315, 317, 318, 319, 320, 322, 325, 326, 328, 329, 330, 331, 332, 333, 334, 337, 340, 342, 343, 345, 347, 349, 351, 353, 354, 357, 359, 360, 361, 362, 364, 366, 367, 368, 369, 372, 375, 381, 382, 384, 386, 387, 389, 390, 392, 393, 395, 397, 398, 403, 406, 407, 408, 410, 412, 415, 417, 418, 419, 421, 422, 424, 427, 428, 429, 431, 432, 435, 437, 438, 439, 441, 442, 446, 447, 448, 449, 450, 452, 455, 457, 458, 459, 461, 462, 466, 467, 468, 472, 473, 476, 480, 481, 482, 483, 486, 487, 491, 492, 497, 498, 499, 500]]
[3, 469, [2, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 497, 498, 499, 500]]
[4, 158, [9, 14, 19, 24, 31, 34, 39, 42, 44, 49, 53, 59, 64, 65, 69, 74, 75, 82, 84, 86, 89, 94, 97, 99, 108, 109, 111, 114, 116, 119, 124, 130, 133, 134, 139, 144, 149, 150, 152, 157, 159, 163, 164, 167, 169, 174, 180, 184, 185, 189, 194, 196, 198, 199, 201, 203, 207, 209, 214, 218, 219, 224, 226, 227, 229, 234, 235, 239, 240, 244, 249, 251, 252, 256, 259, 264, 269, 272, 273, 274, 284, 285, 286, 289, 294, 295, 299, 303, 306, 309, 314, 317, 318, 319, 320, 321, 324, 328, 334, 339, 341, 343, 344, 349, 350, 354, 359, 361, 362, 364, 369, 371, 372, 374, 384, 387, 388, 389, 394, 399, 401, 403, 405, 409, 410, 414, 415, 416, 419, 422, 424, 427, 430, 433, 434, 438, 439, 444, 449, 456, 459, 460, 462, 464, 469, 471, 473, 474, 479, 482, 484, 485, 488, 489, 490, 493, 494, 499]]
[5, 0, []]
[6, 212, [5, 8, 14, 17, 19, 23, 26, 32, 33, 35, 40, 41, 44, 47, 50, 52, 53, 54, 59, 62, 63, 68, 71, 74, 75, 77, 80, 82, 85, 86, 89, 95, 96, 98, 103, 104, 107, 109, 113, 116, 117, 118, 122, 124, 125, 128, 129, 131, 134, 138, 140, 143, 145, 147, 149, 152, 155, 158, 161, 162, 166, 167, 170, 173, 176, 178, 179, 180, 184, 185, 187, 188, 194, 195, 197, 201, 203, 204, 206, 209, 212, 215, 217, 221, 222, 223, 224, 228, 229, 230, 233, 236, 239, 242, 243, 247, 248, 250, 251, 257, 260, 261, 264, 266, 269, 270, 271, 275, 278, 280, 283, 284, 285, 287, 290, 292, 293, 294, 296, 299, 302, 305, 311, 313, 314, 316, 317, 318, 320, 323, 327, 329, 332, 333, 334, 337, 338, 339, 341, 347, 348, 349, 350, 356, 359, 360, 362, 364, 365, 368, 369, 371, 374, 375, 376, 377, 382, 383, 385, 386, 390, 392, 394, 395, 397, 398, 401, 404, 408, 410, 411, 413, 415, 418, 419, 422, 425, 426, 428, 431, 432, 437, 439, 440, 446, 448, 449, 452, 454, 455, 457, 458, 459, 460, 464, 467, 470, 473, 474, 476, 477, 479, 481, 482, 485, 488, 489, 491, 492, 494, 495, 500]]
[8, 250, [3, 7, 11, 13, 15, 18, 19, 23, 27, 28, 29, 31, 35, 38, 39, 43, 45, 47, 48, 51, 53, 55, 59, 61, 62, 63, 67, 68, 71, 73, 75, 77, 78, 79, 83, 84, 87, 88, 91, 93, 95, 98, 99, 103, 106, 107, 109, 111, 113, 115, 117, 118, 119, 123, 125, 127, 128, 130, 131, 135, 138, 139, 141, 143, 147, 148, 150, 151, 153, 155, 157, 159, 163, 164, 167, 168, 171, 172, 173, 175, 178, 179, 181, 183, 187, 188, 189, 191, 193, 194, 195, 198, 199, 203, 205, 207, 211, 213, 215, 216, 218, 219, 221, 222, 223, 227, 228, 231, 232, 235, 237, 238, 239, 243, 245, 247, 248, 249, 251, 253, 255, 259, 260, 263, 266, 267, 268, 269, 271, 273, 275, 278, 279, 283, 285, 287, 288, 291, 293, 295, 298, 299, 300, 301, 303, 304, 307, 309, 311, 313, 314, 315, 317, 318, 319, 323, 326, 327, 328, 331, 333, 334, 335, 337, 338, 339, 343, 347, 348, 349, 351, 353, 355, 359, 360, 363, 365, 367, 368, 370, 371, 373, 375, 378, 379, 381, 383, 387, 388, 391, 392, 393, 395, 396, 397, 398, 399, 402, 403, 406, 407, 411, 413, 414, 415, 418, 419, 423, 425, 427, 428, 429, 431, 435, 436, 437, 438, 439, 443, 445, 447, 448, 451, 452, 453, 454, 455, 458, 459, 461, 463, 467, 468, 469, 470, 471, 473, 475, 477, 478, 479, 480, 483, 487, 488, 491, 493, 495, 498, 499]]
[10, 151, [6, 13, 17, 27, 28, 34, 36, 39, 41, 48, 55, 59, 61, 62, 72, 74, 76, 82, 83, 90, 93, 94, 97, 104, 105, 111, 112, 116, 121, 125, 127, 128, 131, 132, 138, 139, 146, 149, 151, 152, 153, 160, 168, 169, 174, 181, 182, 183, 188, 193, 195, 197, 202, 204, 207, 209, 211, 214, 215, 223, 226, 230, 237, 243, 244, 245, 248, 251, 254, 258, 259, 262, 264, 266, 270, 272, 276, 279, 281, 283, 286, 289, 293, 297, 300, 302, 303, 307, 309, 312, 314, 321, 325, 328, 329, 335, 336, 338, 340, 342, 347, 349, 356, 358, 359, 369, 370, 377, 378, 380, 381, 383, 384, 388, 391, 396, 397, 398, 402, 403, 404, 405, 416, 419, 424, 426, 427, 431, 433, 435, 440, 446, 447, 450, 454, 457, 462, 463, 467, 468, 469, 473, 475, 479, 482, 489, 490, 492, 493, 496, 497]]
[14, 172, [4, 9, 15, 19, 24, 26, 29, 32, 34, 37, 44, 48, 49, 54, 55, 59, 66, 69, 74, 78, 79, 81, 83, 84, 92, 94, 99, 100, 101, 103, 104, 109, 113, 114, 117, 119, 124, 125, 129, 134, 136, 142, 144, 147, 149, 151, 154, 158, 159, 160, 169, 170, 171, 174, 179, 180, 184, 185, 193, 194, 199, 200, 201, 202, 204, 207, 209, 213, 216, 219, 224, 229, 234, 235, 236, 239, 242, 244, 246, 249, 253, 254, 257, 258, 259, 260, 262, 268, 269, 270, 274, 279, 283, 284, 285, 287, 290, 294, 299, 301, 304, 309, 313, 316, 319, 321, 323, 324, 329, 331, 334, 338, 344, 345, 348, 349, 354, 355, 356, 359, 365, 366, 367, 369, 372, 374, 377, 378, 379, 384, 389, 394, 395, 399, 400, 403, 404, 406, 409, 411, 419, 422, 423, 424, 429, 432, 434, 437, 440, 442, 444, 446, 447, 449, 454, 455, 459, 461, 466, 469, 472, 474, 477, 479, 484, 488, 489, 491, 492, 494, 496, 499]]
[15, 2, [53, 482]]
[26, 80, [9, 20, 31, 42, 43, 53, 64, 66, 75, 86, 89, 97, 108, 112, 119, 135, 136, 141, 152, 158, 163, 171, 174, 181, 183, 185, 196, 204, 206, 207, 218, 227, 229, 230, 240, 241, 250, 262, 273, 277, 284, 289, 295, 296, 306, 311, 317, 319, 324, 328, 339, 342, 348, 350, 361, 365, 371, 381, 383, 388, 394, 405, 407, 411, 416, 418, 419, 427, 434, 438, 449, 457, 460, 465, 466, 471, 480, 482, 486, 490]]

181212

Ruby


1212

この記事は
日曜数学 Advent Calendar 2018
の12/12 分として書いております。
前回はだまさんの「初等的解法の存在する角度の問題」でした。

「1が2個, 2が2個」を一列に並べるとき、
同じ数字が並ばない並べ方は何通りあるでしょう。
解：1212、2121の2通り。

「1が9個, 2が9個, ... , 9が9個」を一列に並べるとき、
同じ数字が並ばない並べ方は何通りあるでしょう。
また、
「1がn個, 2がn個, ... , nがn個」を一列に並べるとき、
同じ数字が並ばない並べ方の個数を高速に求めるには
どうすればよいでしょうか？

数学の知識と初歩的なプログラミングの知識が必要になります。

①数学の知識
パスカルの三角形とは次のようなものです。
1,
1, 1,
1, 2, 1,
1, 3, 3, 1,
1, 4, 6, 4, 1,
...
さて次のように細工します。
 1/1,
-1/1,  1/2,
 1/1, -2/2,  1/6,
-1/1,  3/2, -3/6,  1/24,
 1/1, -4/2,  6/6, -4/24, 1/120,
...
これらを係数にもつ多項式q_i(x) を作ります。
q_1(x) =  x,
q_2(x) = -x + 1/2 * x^2,
q_3(x) =  x - 2/2 * x^2 + 1/6 * x^3,
q_4(x) = -x + 3/2 * x^2 - 3/6 * x^3 + 1/24 * x^4,
q_5(x) =  x - 4/2 * x^2 + 6/6 * x^3 - 4/24 * x^4 + 1/120 * x^5,
...
さて、q_i(x) は次のような驚くべき性質を持っています。

「1がm_1個, 2がm_2個, ... , kがm_k個」を一列に並べるとき、同じ数字が並ばない並べ方は
Integral_{0..infinity} Product_{i=1..k} q_{m_i}(x) * exp(-x) dx.

ちなみに、Integral_{0..infinity} x^m * exp(-x) dx = m! ですので、
多項式の掛け算をして、係数を求めることが重要であることがわかります。

今回の場合に当てはめると
Integral_{0..infinity} (q_n(x))^n * exp(-x) dx
となります。

②プログラミングの知識
 (q_n(x))^n の計算はバイナリ法を用いると計算回数が少なくてすみます。

これらをもとに実装すると次のようになり、
n = 9 のときは、
11655577382287102750765311537460065620507094071664576111302628243840
通りと求まります。

def mul(f_ary, b_ary)
  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
end

def power(ary, n)
  return [1] if n == 0
  k = power(ary, n >> 1)
  k = mul(k, k)
  return k if n & 1 == 0
  return mul(k, ary)
end

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

def f(n)
  return 1 if n < 2
  (1..n).inject(:*)
end

def A(n)
  ary = power([0] + (1..n).map{|i| (-1) ** (n - i) * ncr(n - 1, n - i) / f(i).to_r}, n)
  (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end

n = 20
(0..n).each{|i| p [i, A(i)]}

出力結果
[0, 1]
[1, 1]
[2, 2]
[3, 174]
[4, 2265024]
[5, 7946203275000]
[6, 12229789732207993835280]
[7, 12202002913678756821228939869239920]
[8, 10937192762438008527903830198163831816546577931520]
[9, 11655577382287102750765311537460065620507094071664576111302628243840]
[10, 18877545858631350177544126730326118579042534510881427013497201905522243828084277155584000]
[11, 57814365142525615345822290635367980031764472894406481579410336826627768364093502411683595510203294058889662636800]
[12, 407658789636795392873224914660821849906640854496041813132347715886561006703544292229875155619913436614371595102735557393480894068396031590400]
[13, 7916240618568924952784422376897285074349407297177155333772267175236361650837449810625502710956077916339020347009688544252921894901829502808023567304468717311128650695552000]
[14, 498961977012237615935915814835809945218689415847045000987626530145354117671508674820161361629165453542631518534948206591419638038499418413317775100822845509486513888639232738104669714232846642736185909196800]
[15, 118813418570954352257626152461870566748175083811925094869482044671635443619567119146472438369570944844793864117533983401043281073111768900013398219072288449242647438928900346234820007048719066622523886248828693230918893944171625097165388804864000]
[16, 123074415490344199979921662196075276052024358457569576638878274700296813263968616812171263108052043597819537373317572776761453007104704321107605953901687032805754242905638392434082191822082575494722399225216595810131347324670136983012576738242197768842539749995881462695930820212498432000]
[17, 632673322223167150563381180449202895810656486275138980768979126849568078803929001026198717240246438492208986017127366607503113807961453674908153743390688559089518342608243133491125088605989422356306262511591012413333743083156845181593352662535492648478551130685710723664924508871843351853059474256064874854425780258865548135985152000]
[18, 18262485268060395471719629462211789200248188118212907564935177446312080481434798754251346826458783843905735671916454235952642336679346522571446273991105431911451246995478453093531740103567375709740164836196952627498127365568349243885731021363958900889615826228391994012608680368231380597695100532416438065107000126490501124888837506361583551279679270162874801672720230508095201280000]
[19, 3325346401901827184405264043746239777213987165498607952527099919169429535191502889521807119252816036721707694000409416885917354468125596599265774644403590455801186699549289399295618384982739223055026353093870119637734650695671402196886800379294232694826306609192327108837847109423774316242807710788886545902961566935329488725575424433775416001359407137834222431223588069183910836336963435557633128490071733441789088652042060740714496000]
[20, 4263374507224750254652747946709751036907009890731720806160330060792101908200442231854976249703550510732440932255817411768387265800055035356279767743465046586935783799213627064605070089606422958689740675558147647400901384320375900390925397265681026115099056542471222575925955266135626206309095922246090256122147265738804913109253904934843458466990632702917971742764047620310632779114398031596958284411852848038321222991793804098769489620905040225884507551867559309764993380559572463906816000000]

181202

Ruby


A060963 とA322178

出力してみた。

def search(a, num, d, k, n)
  if num == 0
    @cnt += 1
  else
    (2 * n - 1).times{|i|
      if a[i] == 0
        (i + d + 1..2 * n - 1).each{|j|
          if a[j] == 0
            a[i], a[j] = num, num
            search(a, num - 1, j - i - k, k, n)
            a[i], a[j] = 0, 0
          end
        }
      end
    }
  end
end

def A(k, n)
  a = [0] * 2 * n
  @cnt = 0
  search(a, n, 0, k, n)
  @cnt
end

puts "A060963"
p (0..9).map{|i| A(0, i)}
puts "A322178"
p (0..7).map{|i| A(1, i)}

出力結果
A060963
[1, 1, 1, 5, 29, 145, 957, 8397, 85169, 944221]
A322178
[1, 1, 5, 33, 329, 3825, 57293, 977581]

181123

Ruby


A321686

n=4 の場合
4             | 1111 |
3+1         | 1112 |
2+2         | 1122 | 1212, 2121.
2+1+1     | 1123 | 1213, 1231, 2131, 1312, 1321, 3121.
1+1+1+1 | 1234 | 1234, 1243, ... (24 terms)
より、T(4,1) = 0, T(4,2) = 0+2 = 2, T(4,3) = 6, T(4,4) = 24

となっているが、

要素の数が同じもの同士は区別しないとすると、

4             | 1111 |
3+1         | 1112 |
2+2         | 1122 | 1212.
2+1+1     | 1123 | 1213, 1231, 2131.
1+1+1+1 | 1234 | 1234.

T(4,1) = 0, T(4,2) = 0+1 = 1, T(4,3) = 3, T(4,4) = 1
となる。

このように要素の数が同じもの同士は区別しないとした場合について

出力してみた。

def partition(n, min, max)
  return [[]] if n == 0
  [max, n].min.downto(min).flat_map{|i| partition(n - i, min, i).map{|rest| [i, *rest]}}
end

def mul(f_ary, b_ary)
  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
end

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

def f(n)
  return 1 if n < 2
  (1..n).inject(:*)
end

def A(a)
  ary = [1]
  a.each{|i|
    ary = mul(ary, [0] + (1..i).map{|j| (-1) ** (i - j) * ncr(i - 1, i - j) / f(j).to_r})
  }
  (0..ary.size - 1).inject(0){|s, i| s + f(i) * ary[i]}.to_i
end

def B(n)
  a = Array.new(n + 1, 0)
  partition(n, 1, n).each{|ary|
    a[ary.size] += A(ary) / ary.group_by(&:to_i).inject(1){|s, i| s * f(i.last.size)}
  }
  a[1..-1]
end

n = 40
(1..n).each{|i| p B(i)}
# Row sums
p (1..n).map{|i| B(i).inject(:+)}

出力結果
[1]
[0, 1]
[0, 1, 1]
[0, 1, 3, 1]
[0, 1, 7, 6, 1]
[0, 1, 15, 25, 10, 1]
[0, 1, 31, 90, 65, 15, 1]
[0, 1, 63, 301, 350, 140, 21, 1]
[0, 1, 127, 966, 1701, 1050, 266, 28, 1]
[0, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1]
[0, 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1]
[0, 1, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1]
[0, 1, 2047, 86526, 611501, 1379400, 1323652, 627396, 159027, 22275, 1705, 66, 1]
[0, 1, 4095, 261625, 2532530, 7508501, 9321312, 5715424, 1899612, 359502, 39325, 2431, 78, 1]
[0, 1, 8191, 788970, 10391745, 40075035, 63436373, 49329280, 20912320, 5135130, 752752, 66066, 3367, 91, 1]
[0, 1, 16383, 2375101, 42355950, 210766920, 420693273, 408741333, 216627840, 67128490, 12662650, 1479478, 106470, 4550, 105, 1]
[0, 1, 32767, 7141686, 171798901, 1096190550, 2734926558, 3281882604, 2141764053, 820784250, 193754990, 28936908, 2757118, 165620, 6020, 120, 1]
[0, 1, 65535, 21457825, 694337290, 5652751651, 17505749898, 25708104786, 20415995028, 9528822303, 2758334150, 512060978, 62022324, 4910178, 249900, 7820, 136, 1]
[0, 1, 131071, 64439010, 2798806985, 28958095545, 110687251039, 197462483400, 189036065010, 106175395755, 37112163803, 8391004908, 1256328866, 125854638, 8408778, 367200, 9996, 153, 1]
[0, 1, 262143, 193448101, 11259666950, 147589284710, 693081601779, 1492924634839, 1709751003480, 1144614626805, 477297033785, 129413217791, 23466951300, 2892439160, 243577530, 13916778, 527136, 12597, 171, 1]
[0, 1, 524287, 580606446, 45232115901, 749206090500, 4306078895384, 11143554045652, 15170932662679, 12011282644725, 5917584964655, 1900842429486, 411016633391, 61068660380, 6302524580, 452329200, 22350954, 741285, 15675, 190, 1]
[0, 1, 1048575, 1742343625, 181509070050, 3791262568401, 26585679462804, 82310957214948, 132511015347084, 123272476465204, 71187132291275, 26826851689001, 6833042030178, 1204909218331, 149304004500, 13087462580, 809944464, 34952799, 1023435, 19285, 210, 1]
[0, 1, 2097151, 5228079450, 727778623825, 19137821912055, 163305339345225, 602762379967440, 1142399079991620, 1241963303533920, 835143799377954, 366282500870286, 108823356051137, 22496861868481, 3295165281331, 345615943200, 26046574004, 1404142047, 53374629, 1389850, 23485, 231, 1]
[0, 1, 4194303, 15686335501, 2916342574750, 96416888184100, 998969857983405, 4382641999117305, 9741955019900400, 12320068811796900, 9593401297313460, 4864251308951100, 1672162773483930, 401282560341390, 68629175807115, 8479404429331, 762361127264, 49916988803, 2364885369, 79781779, 1859550, 28336, 253, 1]
[0, 1, 8388607, 47063200806, 11681056634501, 485000783495250, 6090236036084530, 31677463851804540, 82318282158320505, 120622574326072500, 108254081784931500, 63100165695775560, 24930204590758260, 6888836057922000, 1362091021641000, 195820242247080, 20677182465555, 1610949936915, 92484925445, 3880739170, 116972779, 2454606, 33902, 276, 1]
[0, 1, 16777215, 141197991025, 46771289738810, 2436684974110751, 37026417000002430, 227832482998716310, 690223721118368580, 1167921451092973005, 1203163392175387500, 802355904438462660, 362262620784874680, 114485073343744260, 25958110360896000, 4299394655347200, 526655161695960, 48063331393110, 3275678594925, 166218969675, 6220194750, 168519505, 3200450, 40250, 300, 1]
[0, 1, 33554431, 423610750290, 187226356946265, 12230196160292565, 224595186974125331, 1631853797991016600, 5749622251945664950, 11201516780955125625, 13199555372846848005, 10029078340998476760, 5149507353856958820, 1850568574253550060, 477898618396288260, 90449030191104000, 12725877242482560, 1343731795378830, 107025546101760, 6433839018750, 290622864675, 9759104355, 238929405, 4126200, 47450, 325, 1]
[0, 1, 67108863, 1270865805301, 749329038535350, 61338207158409090, 1359801318005044551, 11647571772911241531, 47628831813556336200, 106563273280541795575, 143197070509423605675, 123519417123830092365, 71823166587281982600, 29206898819153109600, 8541149231801585700, 1834634071262848260, 294063066070824960, 35569317763922670, 3270191625210510, 229268487458010, 12246296312250, 495564056130, 15015551265, 333832005, 5265000, 55575, 351, 1]
[0, 1, 134217727, 3812664524766, 2998587019946701, 307440364830580800, 8220146115188676396, 82892803728383735268, 392678226281361931131, 1006698291338432496375, 1538533978374777852325, 1501910658871554621690, 985397416171213883565, 451512851236272407400, 148782988064375309400, 36060660300744309600, 6539643128396047620, 898741468057510350, 94432767017711850, 7626292886912700, 474194413703010, 22653141490980, 825906183960, 22693687380, 460192005, 6654375, 64701, 378, 1]
[0, 1, 268435455, 11438127792025, 11998160744311570, 1540200411172850701, 49628317055962639176, 588469772213874823272, 3224318613979279184316, 9452962848327254398506, 16392038075086211019625, 18059551225961878690915, 13326679652926121224470, 6855064482242755179765, 2534474684137526739000, 689692892575539953400, 140694950355081071520, 21818248085373723570, 2598531274376323650, 239332331869053150, 17110181160972900, 949910385013590, 40823077538100, 1347860993700, 33738295500, 626551380, 8336601, 74907, 406, 1]
[0, 1, 536870911, 34314651811530, 48004081105038305, 7713000216608565075, 299310102746948685757, 4168916722553086402080, 26383018684048108297800, 88300984248924568770870, 173373343599189364594756, 215047101560666876619690, 177979707061075333384555, 102442517922081938561415, 42337710060168129525765, 12879868072770626040000, 2940812098256837097720, 511605167806434372210, 68591811024147549270, 7145845579888333500, 581535955088511150, 37058299246258290, 1848018090851790, 71823880393200, 2157580085700, 49402080000, 843303006, 10359090, 86275, 435, 1]
[0, 1, 1073741823, 102944492305501, 192050639071964750, 38613005164147863680, 1803573616698300679617, 29481727160618553500317, 215233066194937952784480, 821091876924369227235630, 1822034420240818214718430, 2538891460766525007411346, 2350803586293570877234350, 1509732440048140534682950, 695170458764435751922125, 235535731151727520125765, 59932861644880019603520, 11638099950966221425290, 1746257766241090259070, 204362877042025885770, 18776564681658556500, 1359760239259935240, 77714697244997670, 3499967339895390, 123605802450000, 3392632085700, 71327958156, 1122998436, 12774790, 98890, 465, 1]
[0, 1, 2147483647, 308834550658326, 768305500780164501, 193257076459811283150, 10860054705353951941382, 208175663741028175181836, 1751346256720122175776157, 7605059958514260997905150, 19041436079332551374419930, 29749840488672593296243236, 30748534496289375534223546, 21977325306919397828112700, 11242118862750241061592700, 4228206426040348553808600, 1194461517469807833782085, 257780560811305783833450, 43070739743305846088550, 5629152430039582088700, 579894170675197015770, 47331529706117196540, 3069483578649883980, 158213946062591640, 6466506598695390, 208421604592500, 5247158997756, 101648915928, 1480692556, 15642600, 112840, 496, 1]
[0, 1, 4294967295, 926505799458625, 3073530837671316330, 967053687799836580251, 65353585308583522931442, 1468089700892551178214234, 14218945717502005581391092, 70196885883348471156922507, 198019420751839774742104450, 346289681454731077633095526, 398732254444145099706925788, 316453763486241547299688646, 179366989385422772690410500, 74665215253355469368721700, 23339590705557273894321960, 5576731051262006158950735, 1033053876190811013427350, 150024635914057905773850, 17227035843543522404100, 1573856294503658143110, 114860168436414644100, 6708404338089491700, 313410104431281000, 11677046713507890, 344847738534156, 7991679727812, 143108307496, 1934327956, 19027800, 128216, 528, 1]
[0, 1, 8589934591, 2779521693343170, 12295049856484723945, 4838341969836854217585, 393088565539300974168903, 10341981491556441770431080, 115219655440908595829342970, 645990918667638245993693655, 2050391093401746218577967007, 4007205916753881628706155236, 5131076734784472274116204982, 4512631179765285214602878186, 2827591614882160364965435646, 1299345218185754813221236000, 448098666542271851677873060, 118144018577011378596484455, 24171700822696604400643035, 3883521958557911223130500, 494565352784928353855850, 50278018028120343409410, 4100780000104780313310, 269153468212472953200, 14230246844440235700, 605336272268978250, 20643087915395946, 560623091185080, 11998712337700, 199203818220, 2505161956, 23002496, 145112, 561, 1]
[0, 1, 17179869183, 8338573669964101, 49182978947632238950, 24204004899040755811870, 2363369735205642699231003, 72786959006434393367186463, 932099225018825208405174840, 5929137923449652809772585865, 21149901852685100431773363725, 46129656177694444134345674603, 65580126734167548918100615020, 63795282071733180063953621400, 44098913788115530324118977230, 22317769887668482563283975646, 8468923882862104440067204960, 2456546982351465287818108795, 553234633385550257808059085, 97958618035296917640122535, 13774829014256478300247500, 1550403731375455565453460, 140495178030425510302230, 10291309768991658236910, 610679392479038610000, 29363653651164691950, 1142056558069272846, 35779911377393106, 896587036640680, 17775623066080, 274358676900, 3218239332, 27646080, 163625, 595, 1]
[0, 1, 34359738367, 25015738189761486, 196740254364198919901, 121069207474151411298300, 14204422416132896951197888, 511872082780246396269536244, 7529580759157036060608585183, 54294340536065700496358447625, 217428156450300657127506223115, 528576119807323985909575784358, 833091176987705031151553054843, 894918793666698889749497693220, 681180075105350604601619302620, 378865462103142768773378611920, 157820552013462153604359255006, 50230222582837014332975054475, 12414770383291369928363172325, 2414448376056191692970387250, 373455198320426483645072535, 46333307373141045174770160, 4641297648044816792102520, 377195302717233649751160, 24947615188488584876910, 1344770733758155908750, 59057124160965785946, 2108114165258886708, 60884348403332146, 1412080105557000, 26006383373080, 374124096192, 4102913892, 33045705, 183855, 630, 1]
[0, 1, 68719476735, 75047248929022825, 786986033194985441090, 605542777625121255411401, 85347603704271533118485628, 3597309001877857670837951596, 60748518156036534881138217708, 496178645583748340527834613808, 2228575905039072271771420678775, 6031765474330864502132839851053, 10525670243659784359728212442474, 12467035494654790597895023066703, 10431439845141607354172167929900, 6364162006652492136202298481420, 2903994294318537226443126692016, 1011734335921691397264935181081, 273696089482081673043512156325, 58289289528359012094800530075, 9883552342464721365871837950, 1346454653156388432315245895, 148441855630127014601025600, 13316789610541190736379200, 975938067240959686797000, 58566883532442482595660, 2880255961943266343346, 115976206622955727062, 3812875920552186796, 101834671464485146, 2192271606749400, 37604230355032, 505417340736, 5193422157, 39296775, 205905, 666, 1]
[0, 1, 137438953471, 225141815506545210, 3148019180028870787185, 3028500874158801262498095, 512691165003254319966325169, 25266510616849275228984146800, 489585454250170136719943693260, 4526356328409771599631649741980, 22781937695974471058242041401558, 68577996122678581795232659040358, 132339808398248276818871389160741, 172597131674172062132363512309613, 158507193326637293556305374085303, 105893869944928989397206645151200, 52828070715749087759292325553676, 20103478004987290979947024770393, 5938263946599161512048153994931, 1381192590520902902844722227750, 255960336377653439412237289075, 38159100058748878444492001745, 4612175477019182753537809095, 454728016672574401537747200, 36739303224324223219507200, 2440110155552021751688500, 133453538542967407522656, 6011613540763070974020, 222736732398416957350, 6766081393022256030, 167602819666967146, 3358002747755392, 53777585258584, 676800271917, 6529512507, 46503450, 229881, 703, 1]
[0, 1, 274877906943, 675425583958589101, 12592301861930989693950, 15145652389974035183277660, 3079175490893684721060449109, 177378265482948180922855352769, 3941950144618210368988533692880, 41226792409938114533404791371080, 232345733288154482182052063757560, 777139895045438870805801290845496, 1656655696901657903621689328969250, 2376102520162485084539597049185710, 2391697838247094171920638749503855, 1746915242500572134514405051353303, 951143001396914393545883854010016, 394587196800533034418391746650357, 126992229043772198196813796679151, 32180923166496316666097876322181, 6500399318073971691089468009250, 1057301437611379886746569325720, 139626960553170899022323801835, 15070919860488393988905994695, 1336471294056355758805920000, 97742057113124767011719700, 5909902157669174347277556, 295767104143570323821196, 12248242047918745779820, 418953092796062382220, 11794165983031270410, 271700904847384298, 5078885476030080, 76111994231845, 898803697155, 8157133257, 54779166, 255892, 741, 1]
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274, 545717047936059989389, 6160539404599934652455, 71339801938860275191172, 846749014511809332450147, 10293358946226376485095653, 128064670049908713818925644, 1629595892846007606764728147, 21195039388640360462388656799, 281600203019560266563340426570, 3819714729894818339975525681317, 52868366208550447901945575624941, 746289892095625330523099540639146, 10738823330774692832768857986425209]