190629

Ruby

sigma_{n-1}(n)

紛らわしいものを出力してみた。 

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

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

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

n = 20
# A262843
p (1..n).map{|i| s(i)}
# A082245
p (1..n).map{|i| t(i)}
# A308814
p (1..n).map{|i| u(i)}

出力結果
[1, 3, 10, 67, 626, 7788, 117650, 2097219, 43046731, 1000000628, 25937424602, 743008378540, 23298085122482, 793714773371796, 29192926025391260, 1152921504608944195, 48661191875666868482, 2185911559738739586477, 104127350297911241532842, 5242880000000001000000692]
[1, 3, 10, 73, 626, 8052, 117650, 2113665, 43053283, 1001953638, 25937424602, 743375541244, 23298085122482, 793811662272744, 29192932133689220, 1152956690052710401, 48661191875666868482, 2185928253847184914509, 104127350297911241532842, 5242890000019348364759358]
[1, 3, 10, 69, 626, 7819, 117650, 2097673, 43046803, 1000010011, 25937424602, 743008621405, 23298085122482, 793714780783695, 29192926025441476, 1152921504875286545, 48661191875666868482, 2185911559749718382455, 104127350297911241532842, 5242880000000512000168021]

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]