2015年10月31日土曜日

151031

Ruby


Alternating permutation

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

def A000111(n)
  e_ary = [1]
  ary = [1]
  n.times{|i|
    new_ary = ary.unshift(0)
    (1..i + 1).each{|i| new_ary[i] += new_ary[i - 1]}
    ary = new_ary.reverse
    e_ary << ary[0]
  }
  e_ary
end
ary = A000111(26)

# OEIS A000111のデータ
ary0 =
[1,1,1,2,5,16,61,272,1385,7936,50521,353792,
 2702765,22368256,199360981,1903757312,19391512145,
 209865342976,2404879675441,29088885112832,
 370371188237525,4951498053124096,
 69348874393137901,1015423886506852352,
 15514534163557086905,246921480190207983616,
 4087072509293123892361]
# 一致の確認
p ary == ary0

2015年10月25日日曜日

151025

Ruby


線対称に分割

線対称に分割すると、
0 = 0,
1 = 1,
2 = 2
2 = 1 + 1,
3 = 3
3 = 1 ++ 1,
4 = 4
4 = 1 + 2 + 1
4 = 1 + 1 + 1 + 1
4 = 2 + 2,
5 = 5
5 = 1 + + 1
5 = 1 + 1 + 1 + 1 + 1
5 = 2 + + 2,

のようになり、それぞれ
1, 1, 2, 2, 4, 4, …
通りの分割の仕方がある。
このコードを書いてみた。

@memo = [1, 1]
n = 30
(2..n).each{|i|
  # まずi = iの1通り
  @memo[i] = 1
  # jとjで挟んだもの
  (1..i / 2).each{|j| @memo[i] += @memo[i - 2 * j]}
}
p @memo

出力結果
[1, 1, 2, 2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 16384, 16384, 32768]

2015年10月24日土曜日

151024(2)

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

Number of times k is used in writing out all the numbers 0 through n(2)
のコードを見れば、
「m進法で0からm0 0…0 (s桁) までの0の個数」
= 「m進法で0からm0 0…0 (s - 1桁) までの桁数の合計」
を示すには、次を示せばよいことが分かる。

m0(s - 1)m^(s - 2) + m^(s - 1) + s - 1 - (m^s - m) / (m - 1)
= ((m0 - 1)m^(s - 2) + 1)(s - 1) + ((s - 2)m^(s - 1) - (s - 1)m^(s- 2) + 1) / (m - 1) + 1

これを示すのは易しい。

151024

Ruby


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

f0(m, k, m0 * m ** i) を調べてみた。
total と f0(m, 0, m0 * m ** i) に面白い関係がある。

# 高速化(ただし、k = 0のときは余分なものも数えている)
def g0(m, k, str, s)
  if s == 1
    return 0 if str.to_i < k
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  if a < k
    b = 0
  elsif a == k
    b = 1 + str1.to_i(m)
  else
    b = m ** (s - 1)
  end
  return a * (s - 1) * m ** (s - 2) + b + g0(m, k, str1, s - 1)
end

# 余分に数えた0の個数
def diff(m, s)
  # (n + 1) * s - ((n - m ** (s - 1) + 1) * s + ((s - 1) * m ** s - s * m ** (s - 1) + 1) / (m - 1) + 1)
  (m ** s - m) / (m - 1)
end

# 0 ≦ k ≦ m - 1
def f0(m, k, n)
  str = n.to_s(m)
  return g0(m, k, str, str.size) if k > 0
  return g0(m, k, str, str.size) - diff(m, str.size)
end

def f0_ary(m, k, ary)
  ary.map{|i| f0(m, k, i)}
end

# 0からnまでをm進法で表したときの桁数の合計
def g0_total(m, n)
  s = n.to_s(m).size
  (n - m ** (s - 1) + 1) * s + ((s - 1) * m ** s - s * m ** (s - 1) + 1) / (m - 1) + 1
end

(2..10).each{|m|
  ary = []
  (0..8).each{|i|
    (1..m - 1).each{|m0|
      ary << m0 * m ** i
    }
  }
  p [m, 'total']
  p ary.map{|n| g0_total(m, n)}
  (0..m - 1).each{|k|
    p [m, k]
    p f0_ary(m, k, ary)
  }
}

出力結果
[2, "total"]
[2, 4, 9, 22, 55, 136, 329, 778, 1803]
[2, 0]
[1, 2, 4, 9, 22, 55, 136, 329, 778]
[2, 1]
[1, 2, 5, 13, 33, 81, 193, 449, 1025]
[3, "total"]
[2, 3, 5, 11, 18, 45, 73, 181, 290, 695, 1101, 2559, 4018, 9121, 14225, 31721, 49218, 108267]
[3, 0]
[1, 1, 2, 3, 5, 11, 18, 45, 73, 181, 290, 695, 1101, 2559, 4018, 9121, 14225, 31721]
[3, 1]
[1, 1, 2, 5, 7, 21, 28, 81, 109, 297, 406, 1053, 1459, 3645, 5104, 12393, 17497, 41553]
[3, 2]
[0, 1, 1, 3, 6, 13, 27, 55, 108, 217, 405, 811, 1458, 2917, 5103, 10207, 17496, 34993]
[4, "total"]
[2, 3, 4, 6, 14, 22, 31, 79, 127, 176, 432, 688, 945, 2225, 3505, 4786, 10930, 17074, 23219, 51891, 80563, 109236, 240308, 371380, 502453, 1092277, 1682101]
[4, 0]
[1, 1, 1, 2, 3, 4, 6, 14, 22, 31, 79, 127, 176, 432, 688, 945, 2225, 3505, 4786, 10930, 17074, 23219, 51891, 80563, 109236, 240308, 371380]
[4, 1]
[1, 1, 1, 2, 6, 7, 9, 32, 40, 49, 160, 208, 257, 768, 1024, 1281, 3584, 4864, 6145, 16384, 22528, 28673, 73728, 102400, 131073, 327680, 458752]
[4, 2]
[0, 1, 1, 1, 3, 7, 8, 17, 40, 48, 97, 208, 256, 513, 1024, 1280, 2561, 4864, 6144, 12289, 22528, 28672, 57345, 102400, 131072, 262145, 458752]
[4, 3]
[0, 0, 1, 1, 2, 4, 8, 16, 25, 48, 96, 145, 256, 512, 769, 1280, 2560, 3841, 6144, 12288, 18433, 28672, 57344, 86017, 131072, 262144, 393217]
[5, "total"]
[2, 3, 4, 5, 7, 17, 27, 37, 48, 123, 198, 273, 349, 849, 1349, 1849, 2350, 5475, 8600, 11725, 14851, 33601, 52351, 71101, 89852, 199227, 308602, 417977, 527353, 1152353, 1777353, 2402353, 3027354, 6542979, 10058604, 13574229]
[5, 0]
[1, 1, 1, 1, 2, 3, 4, 5, 7, 17, 27, 37, 48, 123, 198, 273, 349, 849, 1349, 1849, 2350, 5475, 8600, 11725, 14851, 33601, 52351, 71101, 89852, 199227, 308602, 417977, 527353, 1152353, 1777353, 2402353]
[5, 1]
[1, 1, 1, 1, 2, 7, 8, 9, 11, 45, 55, 65, 76, 275, 350, 425, 501, 1625, 2125, 2625, 3126, 9375, 12500, 15625, 18751, 53125, 71875, 90625, 109376, 296875, 406250, 515625, 625001, 1640625, 2265625, 2890625]
[5, 2]
[0, 1, 1, 1, 1, 3, 8, 9, 10, 21, 55, 65, 75, 151, 350, 425, 500, 1001, 2125, 2625, 3125, 6251, 12500, 15625, 18750, 37501, 71875, 90625, 109375, 218751, 406250, 515625, 625000, 1250001, 2265625, 2890625]
[5, 3]
[0, 0, 1, 1, 1, 2, 4, 9, 10, 20, 31, 65, 75, 150, 226, 425, 500, 1000, 1501, 2625, 3125, 6250, 9376, 15625, 18750, 37500, 56251, 90625, 109375, 218750, 328126, 515625, 625000, 1250000, 1875001, 2890625]
[5, 4]
[0, 0, 0, 1, 1, 2, 3, 5, 10, 20, 30, 41, 75, 150, 225, 301, 500, 1000, 1500, 2001, 3125, 6250, 9375, 12501, 18750, 37500, 56250, 75001, 109375, 218750, 328125, 437501, 625000, 1250000, 1875000, 2500001]
[6, "total"]
[2, 3, 4, 5, 6, 8, 20, 32, 44, 56, 69, 177, 285, 393, 501, 610, 1474, 2338, 3202, 4066, 4931, 11411, 17891, 24371, 30851, 37332, 83988, 130644, 177300, 223956, 270613, 597205, 923797, 1250389, 1576981, 1903574, 4143062, 6382550, 8622038, 10861526, 13101015, 28217559, 43334103, 58450647, 73567191]
[6, 0]
[1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 20, 32, 44, 56, 69, 177, 285, 393, 501, 610, 1474, 2338, 3202, 4066, 4931, 11411, 17891, 24371, 30851, 37332, 83988, 130644, 177300, 223956, 270613, 597205, 923797, 1250389, 1576981, 1903574, 4143062, 6382550, 8622038, 10861526]
[6, 1]
[1, 1, 1, 1, 1, 2, 8, 9, 10, 11, 13, 60, 72, 84, 96, 109, 432, 540, 648, 756, 865, 3024, 3888, 4752, 5616, 6481, 20736, 27216, 33696, 40176, 46657, 139968, 186624, 233280, 279936, 326593, 933120, 1259712, 1586304, 1912896, 2239489, 6158592, 8398080, 10637568, 12877056]
[6, 2]
[0, 1, 1, 1, 1, 1, 3, 9, 10, 11, 12, 25, 72, 84, 96, 108, 217, 540, 648, 756, 864, 1729, 3888, 4752, 5616, 6480, 12961, 27216, 33696, 40176, 46656, 93313, 186624, 233280, 279936, 326592, 653185, 1259712, 1586304, 1912896, 2239488, 4478977, 8398080, 10637568, 12877056]
[6, 3]
[0, 0, 1, 1, 1, 1, 2, 4, 10, 11, 12, 24, 37, 84, 96, 108, 216, 325, 648, 756, 864, 1728, 2593, 4752, 5616, 6480, 12960, 19441, 33696, 40176, 46656, 93312, 139969, 233280, 279936, 326592, 653184, 979777, 1586304, 1912896, 2239488, 4478976, 6718465, 10637568, 12877056]
[6, 4]
[0, 0, 0, 1, 1, 1, 2, 3, 5, 11, 12, 24, 36, 49, 96, 108, 216, 324, 433, 756, 864, 1728, 2592, 3457, 5616, 6480, 12960, 19440, 25921, 40176, 46656, 93312, 139968, 186625, 279936, 326592, 653184, 979776, 1306369, 1912896, 2239488, 4478976, 6718464, 8957953, 12877056]
[6, 5]
[0, 0, 0, 0, 1, 1, 2, 3, 4, 6, 12, 24, 36, 48, 61, 108, 216, 324, 432, 541, 864, 1728, 2592, 3456, 4321, 6480, 12960, 19440, 25920, 32401, 46656, 93312, 139968, 186624, 233281, 326592, 653184, 979776, 1306368, 1632961, 2239488, 4478976, 6718464, 8957952, 11197441]
[7, "total"]
[2, 3, 4, 5, 6, 7, 9, 23, 37, 51, 65, 79, 94, 241, 388, 535, 682, 829, 977, 2349, 3721, 5093, 6465, 7837, 9210, 21215, 33220, 45225, 57230, 69235, 81241, 182083, 282925, 383767, 484609, 585451, 686294, 1509837, 2333380, 3156923, 3980466, 4804009, 5627553, 12215897, 18804241, 25392585, 31980929, 38569273, 45157618, 97040827, 148924036, 200807245, 252690454, 304573663]
[7, 0]
[1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 23, 37, 51, 65, 79, 94, 241, 388, 535, 682, 829, 977, 2349, 3721, 5093, 6465, 7837, 9210, 21215, 33220, 45225, 57230, 69235, 81241, 182083, 282925, 383767, 484609, 585451, 686294, 1509837, 2333380, 3156923, 3980466, 4804009, 5627553, 12215897, 18804241, 25392585, 31980929, 38569273]
[7, 1]
[1, 1, 1, 1, 1, 1, 2, 9, 10, 11, 12, 13, 15, 77, 91, 105, 119, 133, 148, 637, 784, 931, 1078, 1225, 1373, 5145, 6517, 7889, 9261, 10633, 12006, 40817, 52822, 64827, 76832, 88837, 100843, 319333, 420175, 521017, 621859, 722701, 823544, 2470629, 3294172, 4117715, 4941258, 5764801, 6588345, 18941489, 25529833, 32118177, 38706521, 45294865]
[7, 2]
[0, 1, 1, 1, 1, 1, 1, 3, 10, 11, 12, 13, 14, 29, 91, 105, 119, 133, 147, 295, 784, 931, 1078, 1225, 1372, 2745, 6517, 7889, 9261, 10633, 12005, 24011, 52822, 64827, 76832, 88837, 100842, 201685, 420175, 521017, 621859, 722701, 823543, 1647087, 3294172, 4117715, 4941258, 5764801, 6588344, 13176689, 25529833, 32118177, 38706521, 45294865]
[7, 3]
[0, 0, 1, 1, 1, 1, 1, 2, 4, 11, 12, 13, 14, 28, 43, 105, 119, 133, 147, 294, 442, 931, 1078, 1225, 1372, 2744, 4117, 7889, 9261, 10633, 12005, 24010, 36016, 64827, 76832, 88837, 100842, 201684, 302527, 521017, 621859, 722701, 823543, 1647086, 2470630, 4117715, 4941258, 5764801, 6588344, 13176688, 19765033, 32118177, 38706521, 45294865]
[7, 4]
[0, 0, 0, 1, 1, 1, 1, 2, 3, 5, 12, 13, 14, 28, 42, 57, 119, 133, 147, 294, 441, 589, 1078, 1225, 1372, 2744, 4116, 5489, 9261, 10633, 12005, 24010, 36015, 48021, 76832, 88837, 100842, 201684, 302526, 403369, 621859, 722701, 823543, 1647086, 2470629, 3294173, 4941258, 5764801, 6588344, 13176688, 19765032, 26353377, 38706521, 45294865]
[7, 5]
[0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 6, 13, 14, 28, 42, 56, 71, 133, 147, 294, 441, 588, 736, 1225, 1372, 2744, 4116, 5488, 6861, 10633, 12005, 24010, 36015, 48020, 60026, 88837, 100842, 201684, 302526, 403368, 504211, 722701, 823543, 1647086, 2470629, 3294172, 4117716, 5764801, 6588344, 13176688, 19765032, 26353376, 32941721, 45294865]
[7, 6]
[0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 14, 28, 42, 56, 70, 85, 147, 294, 441, 588, 735, 883, 1372, 2744, 4116, 5488, 6860, 8233, 12005, 24010, 36015, 48020, 60025, 72031, 100842, 201684, 302526, 403368, 504210, 605053, 823543, 1647086, 2470629, 3294172, 4117715, 4941259, 6588344, 13176688, 19765032, 26353376, 32941720, 39530065]
[8, "total"]
[2, 3, 4, 5, 6, 7, 8, 10, 26, 42, 58, 74, 90, 106, 123, 315, 507, 699, 891, 1083, 1275, 1468, 3516, 5564, 7612, 9660, 11708, 13756, 15805, 36285, 56765, 77245, 97725, 118205, 138685, 159166, 355774, 552382, 748990, 945598, 1142206, 1338814, 1535423, 3370431, 5205439, 7040447, 8875455, 10710463, 12545471, 14380480, 31157696, 47934912, 64712128, 81489344, 98266560, 115043776, 131820993, 282815937, 433810881, 584805825, 735800769, 886795713, 1037790657]
[8, 0]
[1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 26, 42, 58, 74, 90, 106, 123, 315, 507, 699, 891, 1083, 1275, 1468, 3516, 5564, 7612, 9660, 11708, 13756, 15805, 36285, 56765, 77245, 97725, 118205, 138685, 159166, 355774, 552382, 748990, 945598, 1142206, 1338814, 1535423, 3370431, 5205439, 7040447, 8875455, 10710463, 12545471, 14380480, 31157696, 47934912, 64712128, 81489344, 98266560, 115043776]
[8, 1]
[1, 1, 1, 1, 1, 1, 1, 2, 10, 11, 12, 13, 14, 15, 17, 96, 112, 128, 144, 160, 176, 193, 896, 1088, 1280, 1472, 1664, 1856, 2049, 8192, 10240, 12288, 14336, 16384, 18432, 20481, 73728, 94208, 114688, 135168, 155648, 176128, 196609, 655360, 851968, 1048576, 1245184, 1441792, 1638400, 1835009, 5767168, 7602176, 9437184, 11272192, 13107200, 14942208, 16777217, 50331648, 67108864, 83886080, 100663296, 117440512, 134217728]
[8, 2]
[0, 1, 1, 1, 1, 1, 1, 1, 3, 11, 12, 13, 14, 15, 16, 33, 112, 128, 144, 160, 176, 192, 385, 1088, 1280, 1472, 1664, 1856, 2048, 4097, 10240, 12288, 14336, 16384, 18432, 20480, 40961, 94208, 114688, 135168, 155648, 176128, 196608, 393217, 851968, 1048576, 1245184, 1441792, 1638400, 1835008, 3670017, 7602176, 9437184, 11272192, 13107200, 14942208, 16777216, 33554433, 67108864, 83886080, 100663296, 117440512, 134217728]
[8, 3]
[0, 0, 1, 1, 1, 1, 1, 1, 2, 4, 12, 13, 14, 15, 16, 32, 49, 128, 144, 160, 176, 192, 384, 577, 1280, 1472, 1664, 1856, 2048, 4096, 6145, 12288, 14336, 16384, 18432, 20480, 40960, 61441, 114688, 135168, 155648, 176128, 196608, 393216, 589825, 1048576, 1245184, 1441792, 1638400, 1835008, 3670016, 5505025, 9437184, 11272192, 13107200, 14942208, 16777216, 33554432, 50331649, 83886080, 100663296, 117440512, 134217728]
[8, 4]
[0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 5, 13, 14, 15, 16, 32, 48, 65, 144, 160, 176, 192, 384, 576, 769, 1472, 1664, 1856, 2048, 4096, 6144, 8193, 14336, 16384, 18432, 20480, 40960, 61440, 81921, 135168, 155648, 176128, 196608, 393216, 589824, 786433, 1245184, 1441792, 1638400, 1835008, 3670016, 5505024, 7340033, 11272192, 13107200, 14942208, 16777216, 33554432, 50331648, 67108865, 100663296, 117440512, 134217728]
[8, 5]
[0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 6, 14, 15, 16, 32, 48, 64, 81, 160, 176, 192, 384, 576, 768, 961, 1664, 1856, 2048, 4096, 6144, 8192, 10241, 16384, 18432, 20480, 40960, 61440, 81920, 102401, 155648, 176128, 196608, 393216, 589824, 786432, 983041, 1441792, 1638400, 1835008, 3670016, 5505024, 7340032, 9175041, 13107200, 14942208, 16777216, 33554432, 50331648, 67108864, 83886081, 117440512, 134217728]
[8, 6]
[0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 7, 15, 16, 32, 48, 64, 80, 97, 176, 192, 384, 576, 768, 960, 1153, 1856, 2048, 4096, 6144, 8192, 10240, 12289, 18432, 20480, 40960, 61440, 81920, 102400, 122881, 176128, 196608, 393216, 589824, 786432, 983040, 1179649, 1638400, 1835008, 3670016, 5505024, 7340032, 9175040, 11010049, 14942208, 16777216, 33554432, 50331648, 67108864, 83886080, 100663297, 134217728]
[8, 7]
[0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 8, 16, 32, 48, 64, 80, 96, 113, 192, 384, 576, 768, 960, 1152, 1345, 2048, 4096, 6144, 8192, 10240, 12288, 14337, 20480, 40960, 61440, 81920, 102400, 122880, 143361, 196608, 393216, 589824, 786432, 983040, 1179648, 1376257, 1835008, 3670016, 5505024, 7340032, 9175040, 11010048, 12845057, 16777216, 33554432, 50331648, 67108864, 83886080, 100663296, 117440513]
[9, "total"]
[2, 3, 4, 5, 6, 7, 8, 9, 11, 29, 47, 65, 83, 101, 119, 137, 156, 399, 642, 885, 1128, 1371, 1614, 1857, 2101, 5017, 7933, 10849, 13765, 16681, 19597, 22513, 25430, 58235, 91040, 123845, 156650, 189455, 222260, 255065, 287871, 642165, 996459, 1350753, 1705047, 2059341, 2413635, 2767929, 3122224, 6842311, 10562398, 14282485, 18002572, 21722659, 25442746, 29162833, 32882921, 71146673, 109410425, 147674177, 185937929, 224201681, 262465433, 300729185, 338992938, 726413427, 1113833916, 1501254405, 1888674894, 2276095383, 2663515872, 3050936361]
[9, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 29, 47, 65, 83, 101, 119, 137, 156, 399, 642, 885, 1128, 1371, 1614, 1857, 2101, 5017, 7933, 10849, 13765, 16681, 19597, 22513, 25430, 58235, 91040, 123845, 156650, 189455, 222260, 255065, 287871, 642165, 996459, 1350753, 1705047, 2059341, 2413635, 2767929, 3122224, 6842311, 10562398, 14282485, 18002572, 21722659, 25442746, 29162833, 32882921, 71146673, 109410425, 147674177, 185937929, 224201681, 262465433, 300729185]
[9, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 11, 12, 13, 14, 15, 16, 17, 19, 117, 135, 153, 171, 189, 207, 225, 244, 1215, 1458, 1701, 1944, 2187, 2430, 2673, 2917, 12393, 15309, 18225, 21141, 24057, 26973, 29889, 32806, 124659, 157464, 190269, 223074, 255879, 288684, 321489, 354295, 1240029, 1594323, 1948617, 2302911, 2657205, 3011499, 3365793, 3720088, 12223143, 15943230, 19663317, 23383404, 27103491, 30823578, 34543665, 38263753, 119574225, 157837977, 196101729, 234365481, 272629233, 310892985, 349156737]
[9, 2]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 3, 12, 13, 14, 15, 16, 17, 18, 37, 135, 153, 171, 189, 207, 225, 243, 487, 1458, 1701, 1944, 2187, 2430, 2673, 2916, 5833, 15309, 18225, 21141, 24057, 26973, 29889, 32805, 65611, 157464, 190269, 223074, 255879, 288684, 321489, 354294, 708589, 1594323, 1948617, 2302911, 2657205, 3011499, 3365793, 3720087, 7440175, 15943230, 19663317, 23383404, 27103491, 30823578, 34543665, 38263752, 76527505, 157837977, 196101729, 234365481, 272629233, 310892985, 349156737]
[9, 3]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 4, 13, 14, 15, 16, 17, 18, 36, 55, 153, 171, 189, 207, 225, 243, 486, 730, 1701, 1944, 2187, 2430, 2673, 2916, 5832, 8749, 18225, 21141, 24057, 26973, 29889, 32805, 65610, 98416, 190269, 223074, 255879, 288684, 321489, 354294, 708588, 1062883, 1948617, 2302911, 2657205, 3011499, 3365793, 3720087, 7440174, 11160262, 19663317, 23383404, 27103491, 30823578, 34543665, 38263752, 76527504, 114791257, 196101729, 234365481, 272629233, 310892985, 349156737]
[9, 4]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 5, 14, 15, 16, 17, 18, 36, 54, 73, 171, 189, 207, 225, 243, 486, 729, 973, 1944, 2187, 2430, 2673, 2916, 5832, 8748, 11665, 21141, 24057, 26973, 29889, 32805, 65610, 98415, 131221, 223074, 255879, 288684, 321489, 354294, 708588, 1062882, 1417177, 2302911, 2657205, 3011499, 3365793, 3720087, 7440174, 11160261, 14880349, 23383404, 27103491, 30823578, 34543665, 38263752, 76527504, 114791256, 153055009, 234365481, 272629233, 310892985, 349156737]
[9, 5]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 4, 6, 15, 16, 17, 18, 36, 54, 72, 91, 189, 207, 225, 243, 486, 729, 972, 1216, 2187, 2430, 2673, 2916, 5832, 8748, 11664, 14581, 24057, 26973, 29889, 32805, 65610, 98415, 131220, 164026, 255879, 288684, 321489, 354294, 708588, 1062882, 1417176, 1771471, 2657205, 3011499, 3365793, 3720087, 7440174, 11160261, 14880348, 18600436, 27103491, 30823578, 34543665, 38263752, 76527504, 114791256, 153055008, 191318761, 272629233, 310892985, 349156737]
[9, 6]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 16, 17, 18, 36, 54, 72, 90, 109, 207, 225, 243, 486, 729, 972, 1215, 1459, 2430, 2673, 2916, 5832, 8748, 11664, 14580, 17497, 26973, 29889, 32805, 65610, 98415, 131220, 164025, 196831, 288684, 321489, 354294, 708588, 1062882, 1417176, 1771470, 2125765, 3011499, 3365793, 3720087, 7440174, 11160261, 14880348, 18600435, 22320523, 30823578, 34543665, 38263752, 76527504, 114791256, 153055008, 191318760, 229582513, 310892985, 349156737]
[9, 7]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 17, 18, 36, 54, 72, 90, 108, 127, 225, 243, 486, 729, 972, 1215, 1458, 1702, 2673, 2916, 5832, 8748, 11664, 14580, 17496, 20413, 29889, 32805, 65610, 98415, 131220, 164025, 196830, 229636, 321489, 354294, 708588, 1062882, 1417176, 1771470, 2125764, 2480059, 3365793, 3720087, 7440174, 11160261, 14880348, 18600435, 22320522, 26040610, 34543665, 38263752, 76527504, 114791256, 153055008, 191318760, 229582512, 267846265, 349156737]
[9, 8]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 9, 18, 36, 54, 72, 90, 108, 126, 145, 243, 486, 729, 972, 1215, 1458, 1701, 1945, 2916, 5832, 8748, 11664, 14580, 17496, 20412, 23329, 32805, 65610, 98415, 131220, 164025, 196830, 229635, 262441, 354294, 708588, 1062882, 1417176, 1771470, 2125764, 2480058, 2834353, 3720087, 7440174, 11160261, 14880348, 18600435, 22320522, 26040609, 29760697, 38263752, 76527504, 114791256, 153055008, 191318760, 229582512, 267846264, 306110017]
[10, "total"]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 32, 52, 72, 92, 112, 132, 152, 172, 193, 493, 793, 1093, 1393, 1693, 1993, 2293, 2593, 2894, 6894, 10894, 14894, 18894, 22894, 26894, 30894, 34894, 38895, 88895, 138895, 188895, 238895, 288895, 338895, 388895, 438895, 488896, 1088896, 1688896, 2288896, 2888896, 3488896, 4088896, 4688896, 5288896, 5888897, 12888897, 19888897, 26888897, 33888897, 40888897, 47888897, 54888897, 61888897, 68888898, 148888898, 228888898, 308888898, 388888898, 468888898, 548888898, 628888898, 708888898, 788888899, 1688888899, 2588888899, 3488888899, 4388888899, 5288888899, 6188888899, 7088888899, 7988888899]
[10, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 32, 52, 72, 92, 112, 132, 152, 172, 193, 493, 793, 1093, 1393, 1693, 1993, 2293, 2593, 2894, 6894, 10894, 14894, 18894, 22894, 26894, 30894, 34894, 38895, 88895, 138895, 188895, 238895, 288895, 338895, 388895, 438895, 488896, 1088896, 1688896, 2288896, 2888896, 3488896, 4088896, 4688896, 5288896, 5888897, 12888897, 19888897, 26888897, 33888897, 40888897, 47888897, 54888897, 61888897, 68888898, 148888898, 228888898, 308888898, 388888898, 468888898, 548888898, 628888898, 708888898]
[10, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 12, 13, 14, 15, 16, 17, 18, 19, 21, 140, 160, 180, 200, 220, 240, 260, 280, 301, 1600, 1900, 2200, 2500, 2800, 3100, 3400, 3700, 4001, 18000, 22000, 26000, 30000, 34000, 38000, 42000, 46000, 50001, 200000, 250000, 300000, 350000, 400000, 450000, 500000, 550000, 600001, 2200000, 2800000, 3400000, 4000000, 4600000, 5200000, 5800000, 6400000, 7000001, 24000000, 31000000, 38000000, 45000000, 52000000, 59000000, 66000000, 73000000, 80000001, 260000000, 340000000, 420000000, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 2]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 13, 14, 15, 16, 17, 18, 19, 20, 41, 160, 180, 200, 220, 240, 260, 280, 300, 601, 1900, 2200, 2500, 2800, 3100, 3400, 3700, 4000, 8001, 22000, 26000, 30000, 34000, 38000, 42000, 46000, 50000, 100001, 250000, 300000, 350000, 400000, 450000, 500000, 550000, 600000, 1200001, 2800000, 3400000, 4000000, 4600000, 5200000, 5800000, 6400000, 7000000, 14000001, 31000000, 38000000, 45000000, 52000000, 59000000, 66000000, 73000000, 80000000, 160000001, 340000000, 420000000, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 3]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 14, 15, 16, 17, 18, 19, 20, 40, 61, 180, 200, 220, 240, 260, 280, 300, 600, 901, 2200, 2500, 2800, 3100, 3400, 3700, 4000, 8000, 12001, 26000, 30000, 34000, 38000, 42000, 46000, 50000, 100000, 150001, 300000, 350000, 400000, 450000, 500000, 550000, 600000, 1200000, 1800001, 3400000, 4000000, 4600000, 5200000, 5800000, 6400000, 7000000, 14000000, 21000001, 38000000, 45000000, 52000000, 59000000, 66000000, 73000000, 80000000, 160000000, 240000001, 420000000, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 4]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 15, 16, 17, 18, 19, 20, 40, 60, 81, 200, 220, 240, 260, 280, 300, 600, 900, 1201, 2500, 2800, 3100, 3400, 3700, 4000, 8000, 12000, 16001, 30000, 34000, 38000, 42000, 46000, 50000, 100000, 150000, 200001, 350000, 400000, 450000, 500000, 550000, 600000, 1200000, 1800000, 2400001, 4000000, 4600000, 5200000, 5800000, 6400000, 7000000, 14000000, 21000000, 28000001, 45000000, 52000000, 59000000, 66000000, 73000000, 80000000, 160000000, 240000000, 320000001, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 5]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 4, 6, 16, 17, 18, 19, 20, 40, 60, 80, 101, 220, 240, 260, 280, 300, 600, 900, 1200, 1501, 2800, 3100, 3400, 3700, 4000, 8000, 12000, 16000, 20001, 34000, 38000, 42000, 46000, 50000, 100000, 150000, 200000, 250001, 400000, 450000, 500000, 550000, 600000, 1200000, 1800000, 2400000, 3000001, 4600000, 5200000, 5800000, 6400000, 7000000, 14000000, 21000000, 28000000, 35000001, 52000000, 59000000, 66000000, 73000000, 80000000, 160000000, 240000000, 320000000, 400000001, 580000000, 660000000, 740000000, 820000000]
[10, 6]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 4, 5, 7, 17, 18, 19, 20, 40, 60, 80, 100, 121, 240, 260, 280, 300, 600, 900, 1200, 1500, 1801, 3100, 3400, 3700, 4000, 8000, 12000, 16000, 20000, 24001, 38000, 42000, 46000, 50000, 100000, 150000, 200000, 250000, 300001, 450000, 500000, 550000, 600000, 1200000, 1800000, 2400000, 3000000, 3600001, 5200000, 5800000, 6400000, 7000000, 14000000, 21000000, 28000000, 35000000, 42000001, 59000000, 66000000, 73000000, 80000000, 160000000, 240000000, 320000000, 400000000, 480000001, 660000000, 740000000, 820000000]
[10, 7]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 18, 19, 20, 40, 60, 80, 100, 120, 141, 260, 280, 300, 600, 900, 1200, 1500, 1800, 2101, 3400, 3700, 4000, 8000, 12000, 16000, 20000, 24000, 28001, 42000, 46000, 50000, 100000, 150000, 200000, 250000, 300000, 350001, 500000, 550000, 600000, 1200000, 1800000, 2400000, 3000000, 3600000, 4200001, 5800000, 6400000, 7000000, 14000000, 21000000, 28000000, 35000000, 42000000, 49000001, 66000000, 73000000, 80000000, 160000000, 240000000, 320000000, 400000000, 480000000, 560000001, 740000000, 820000000]
[10, 8]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 19, 20, 40, 60, 80, 100, 120, 140, 161, 280, 300, 600, 900, 1200, 1500, 1800, 2100, 2401, 3700, 4000, 8000, 12000, 16000, 20000, 24000, 28000, 32001, 46000, 50000, 100000, 150000, 200000, 250000, 300000, 350000, 400001, 550000, 600000, 1200000, 1800000, 2400000, 3000000, 3600000, 4200000, 4800001, 6400000, 7000000, 14000000, 21000000, 28000000, 35000000, 42000000, 49000000, 56000001, 73000000, 80000000, 160000000, 240000000, 320000000, 400000000, 480000000, 560000000, 640000001, 820000000]
[10, 9]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 20, 40, 60, 80, 100, 120, 140, 160, 181, 300, 600, 900, 1200, 1500, 1800, 2100, 2400, 2701, 4000, 8000, 12000, 16000, 20000, 24000, 28000, 32000, 36001, 50000, 100000, 150000, 200000, 250000, 300000, 350000, 400000, 450001, 600000, 1200000, 1800000, 2400000, 3000000, 3600000, 4200000, 4800000, 5400001, 7000000, 14000000, 21000000, 28000000, 35000000, 42000000, 49000000, 56000000, 63000001, 80000000, 160000000, 240000000, 320000000, 400000000, 480000000, 560000000, 640000000, 720000001]

2015年10月23日金曜日

151023

Ruby


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

0からnまでをm進法で表したとき、'k'が現れる回数をf0(m, k, n)と表す。
0 ≦ k ≦ m - 1 のとき、f0(m, k, n)を計算してみた。
(1からではなく0から始めることで
Number of times k is used in writing out all the numbers 1 through n(4)
より簡単なコードになっている。)

# 高速化(ただし、k = 0のときは余分なものも数えている)
def g0(m, k, str, s)
  if s == 1
    return 0 if str.to_i < k
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  if a < k
    b = 0
  elsif a == k
    b = 1 + str1.to_i(m)
  else
    b = m ** (s - 1)
  end
  return a * (s - 1) * m ** (s - 2) + b + g0(m, k, str1, s - 1)
end

# 余分に数えた0の個数
def diff(m, s)
  # (n + 1) * s - ((n - m ** (s - 1) + 1) * s + ((s - 1) * m ** s - s * m ** (s - 1) + 1) / (m - 1) + 1)
  (m ** s - m) / (m - 1)
end

# 0 ≦ k ≦ m - 1
def f0(m, k, n)
  str = n.to_s(m)
  return g0(m, k, str, str.size) if k > 0
  return g0(m, k, str, str.size) - diff(m, str.size)
end

def f0_ary(m, k, ary)
  ary.map{|i| f0(m, k, i)}
end

ary = (0..30).map{|i| 10 ** i}
(2..10).each{|m|
  (0..m - 1).each{|k|
    p [m, k]
    p f0_ary(m, k, ary)
  }
}

出力結果
[2, 0]
[1, 13, 262, 4050, 59019, 753917, 9066447, 108788178, 1251335185, 14079330067, 158527003673, 1752835390488, 19090546253853, 208098347208736, 2252849861951520, 24089352692482080, 257698738277646372, 2751668512654557223, 29085855711963906086, 307321301701485658159, 3250747955772179611691, 34097225207936917176363, 356740182741316423122995, 3749253699468361851732020, 39095688742747483198718004, 406175259971825928562016323, 4246828189080603640098455610, 44083505748384265246265573435, 455434943536948705659874967619, 4742841005020882211549522952255, 49074610463753249371476157530177]
[2, 1]
[1, 17, 319, 4938, 64613, 815030, 9884999, 114434632, 1314447116, 14846928141, 164293127179, 1809725656079, 19809942118413, 214309466746894, 2306412649693201, 24784747400675348, 264286863212871700, 2804216299269586964, 29761222783429247000, 314231954224804790291, 3301678091638143975450, 34722183171345671520285, 364370351327204996022297, 3799630573079809501429787, 39695385437637887626575902, 414481926914340004642684947, 4298429306008723825539153951, 44678554212330354478835302433, 464758015834485209941739044893, 4798702669950589113263389147172, 49657738936018521227027139264549]
[3, 0]
[1, 6, 113, 1831, 24857, 312300, 3780510, 44933596, 521626140, 5880056823, 65288716801, 729403871261, 8069935693755, 87955158771472, 950747326623766, 10126147772237069, 108084168326741433, 1141785638343655930, 12192227578518173961, 129047966872781701146, 1353915031388354912699, 14214508943285390237647, 150454979304746373557150, 1577741974974853061914469, 16498568363160802749548695, 171387305141808329923338625, 1780108108035447213226908092, 18447384842421533898610566004, 191772211443386288986141603860, 1989535564536715272236693308178, 20537857501872708600844155839528]
[3, 1]
[1, 9, 150, 2194, 30374, 379432, 4508710, 51180200, 572158742, 6417405502, 70402455152, 769364418852, 8452692931320, 91673681872620, 993534122918024, 10779360089419044, 114661242594171254, 1216758202087170334, 12767569182895088152, 133862436956018539886, 1405771200630725286006, 14663860400505783919608, 153796494936787179989436, 1614986483014523055902106, 16887592497038459726705624, 177308495497250974401699424, 1846007098588454905102196728, 19172094511757798531897719532, 197677440096181467378574033316, 2037819660431890371250386506764, 21087982689937490731566483680876]
[3, 2]
[0, 6, 122, 1890, 24938, 319707, 3913633, 46711767, 541645055, 6121406962, 69078651468, 760016941672, 8206438460788, 88932763128457, 952772984410917, 10167982043918000, 108915998229254064, 1166408841920674213, 12364777379750241882, 131010763441671294609, 1385604273415163621734, 14644474302933408993470, 152454118578987694809569, 1587621877395315117388434, 16536992158262958640590360, 171612576527100685726563644, 1786660187871537792135309983, 18595499196279626763671447241, 193485155414562876382901957351, 2009058037618570051241478535319, 20801879171474381920146385631447]
[4, 0]
[1, 3, 66, 931, 14295, 187919, 2187937, 26908112, 311721393, 3432994225, 39525887924, 438139377843, 4694047261365, 51963626752694, 563444246338231, 5950299292388022, 64318496246508217, 689832613531986616, 7196883791014767288, 76667563571579759293, 815418493853503761082, 8458340839333464550073, 89018412185597045811901, 941665524969631256324798, 9715438621335639516949184, 101390308675072882998160067, 1065852289025381734728510146, 10953847619079715832472447684, 113561946913550953876808182469, 1189758972766744231851042974402, 12191516113782136523161864940227]
[4, 1]
[1, 7, 119, 1270, 19482, 242178, 2520434, 31973411, 366171397, 3790564097, 44245876996, 488164976133, 5056725669893, 56692742610948, 610964919316485, 6310200205451268, 69321688173772803, 732713250404499465, 7571981434117226501, 82037556623093661699, 854087328285483073545, 8814800381086001004552, 94722289936057215483909, 973215603996092086091784, 10042775926285679481323524, 107193424611029871262433293, 1094927512861631153262559239, 11294729851272492427228741634, 119893894654631361202345738248, 1216129526537655672735115771912, 12564494019293974745563833303049]
[4, 2]
[0, 6, 70, 1260, 16409, 192212, 2519665, 28590949, 316981761, 3780691462, 40955973891, 442578674180, 5012229937156, 53342413107206, 568083953840132, 6253853871202310, 65744857114017797, 691251639160799237, 7504413864019427335, 78097532626468995080, 816632322249796878341, 8759273688423124172807, 90277557077891309633546, 942335136382397704044551, 10025010846995401075064838, 102648822381928313568362502, 1068615263197984839258079238, 11293727338714134579058311175, 115019501931404131503374860295, 1194374757940228516716625264650, 12549634416971078046754162081800]
[4, 3]
[0, 2, 65, 1204, 14361, 190320, 2422450, 26935136, 315646979, 3637836291, 39545638146, 439491002883, 4870493255682, 52137155514370, 563681888268292, 6110346662010885, 64610158962540550, 690125704852144131, 7342413742646296582, 77048432487621066756, 815479220551432011782, 8574054550918273171463, 89685252156628235452421, 942039916350659855646726, 9813799332178403535093770, 102319839960690909905944576, 1067443264974553916509257737, 11045048511171863736274124812, 114922309624224858618009223175, 1194099192736352461905824055305, 12271805249876734217354571939850]
[5, 0]
[1, 3, 37, 698, 9724, 133600, 1539851, 17964854, 211464854, 2363964855, 27106933606, 297575683606, 3329870605482, 35417419433609, 383416442871111, 4130332946777362, 43783256530761737, 470461692810058612, 4967175102233886739, 53233740806579589864, 554061484336853027367, 5848109316825866699244, 61451171278953552246120, 638078004717826843261743, 6697390648722648620605494, 69689764007925987243652372, 731683334037661552429199247, 7532112069055438041687011748, 78680840184912085533142089875, 815907630762085318565368652375, 8370816258480772376060485839875]
[5, 1]
[1, 7, 65, 1226, 13001, 165627, 2028125, 20171876, 268203127, 2645703125, 32294921876, 331865234377, 3689306640628, 40104003906250, 403492431640629, 4679504394531250, 46297943115234377, 525622406005859377, 5326352691650390626, 57214763641357421878, 600465202331542968751, 6073609542846679687504, 66583832740783691406250, 664710590839385986328129, 7260833132266998291015627, 73223027288913726806640626, 775132898688316345214843753, 7986859233677387237548828126, 80951736219227313995361328129, 863699755929410457611083984377, 8654589133337140083312988281252]
[5, 2]
[0, 3, 65, 850, 13000, 134376, 1840627, 19937500, 221328126, 2637890627, 28398437500, 328398437500, 3360693359376, 38648925781253, 397962646484375, 4234832763671878, 46295654296875001, 482975616455078127, 5279622650146484376, 53592174530029296877, 587362003326416015628, 5973327350616455078127, 62607814311981201171878, 661748609542846679687501, 6841735947132110595703127, 72742526531219482421875006, 734739064872264862060546876, 7895457209646701812744140627, 79807786367833614349365234378, 827261740826070308685302734379, 8609556240960955619812011718752]
[5, 3]
[0, 2, 65, 726, 10501, 134375, 1559375, 19859376, 218984375, 2633984375, 27412109376, 306279296877, 3336279296876, 35572753906252, 397962646484375, 4179687500000002, 46295501708984375, 475630035400390627, 5086095428466796878, 53411624908447265628, 557347488403320312503, 5973314476013183593750, 61840394973754882812502, 661399910449981689453127, 6771569001674652099609381, 70993635952472686767578126, 734738297462463378906250001, 7598587559163570404052734380, 79595554493367671966552734377, 818210961408913135528564453127, 8609467113390564918518066406252]
[5, 4]
[0, 2, 41, 725, 9875, 134375, 1543751, 19859375, 218984375, 2413281251, 27158203127, 297734375001, 3330175781251, 35488525390625, 397956542968751, 4179595947265625, 44347412109375003, 470804443359375002, 4968225097656250002, 53234470367431640626, 554197692871093750000, 5967486095428466796876, 61696020603179931640627, 644959053993225097656253, 6700875508785247802734376, 69713067412376403808593751, 732756934762001037597656256, 7532236577570438385009765628, 79595398962497711181640625002, 818076492212712764739990234379, 8471354159526526927947998046882]
[6, 0]
[1, 2, 29, 473, 7793, 96603, 1135661, 13028619, 158363050, 1781669669, 19745872649, 227909003890, 2459990037721, 26379763779106, 280500235869853, 3085218547843455, 32833258280691483, 347683017078293948, 3782653531545490551, 39534227235118387854, 413735974024774674040, 4307326759431044312456, 45870435722012457184614, 478528913697009862151536, 4977878570157856366073922, 52862340470486562513187628, 544934333327418440419736975, 5634687330082765057385572667, 58051923646208511391050595230, 609025632944260003625107643690, 6286448314756728197548186447324]
[6, 1]
[1, 7, 71, 731, 11198, 145691, 1471583, 15044020, 209959005, 2215950297, 22357576982, 260732117894, 2964571630298, 29734482337166, 300804840123645, 3596403661788849, 37220596165405190, 373942198480119148, 4097855055721481385, 44696639571507276727, 447357911583038454820, 4507221089612289882735, 50957678725204529674292, 522423493113073904971028, 5237942923211234920118775, 55861845725776606242564250, 597738819735637161095723198, 5978498177859560689393554348, 60114808605080898875434217157, 659222499890635670519267561691, 6722194098228926259163478574015]
[6, 2]
[0, 2, 64, 731, 8015, 105724, 1468480, 15036280, 170401845, 2126695994, 22349164466, 230521001428, 2553734780882, 29686729820416, 300655135938110, 3205679939605408, 36193990212721421, 373397802196303303, 3808925198520288348, 40481495552137836674, 447357910133301379941, 4506949179057162814305, 47098247702572249166961, 511150472996604417121406, 5237921416451673325535601, 53086650812786108689970093, 554300469172884983148693418, 5975675931659730378512521836, 60110711489062580279483779095, 621101636832399682997748155321, 6608209287937450403786033573638]
[6, 3]
[0, 2, 35, 724, 8015, 99035, 1317036, 15036215, 169406949, 1844445489, 22150503153, 230377772246, 2492643173066, 28053573741924, 300332901443709, 3189692886768142, 33445910414365065, 370957646611641398, 3797461074214285846, 39955008728061630146, 429356627553235346921, 4506931335876576179484, 46855356118085672416370, 484840463353143769132156, 5206242491098553003089692, 52914044231686680108760939, 548919206520818064857594777, 5784519881662083425823771238, 60105516962177037905394679990, 617957240997791333903390950104, 6350842080307719441451087214751]
[6, 4]
[0, 2, 34, 615, 7863, 99034, 1135666, 15005175, 160043362, 1814212292, 21038871313, 228282586508, 2486112825675, 26380129900105, 300261067622732, 3103725613575301, 33085595600958522, 359974948542551848, 3782714438353511379, 39826535380747513568, 414043307158573756000, 4506927171526374932207, 45978714519912057008219, 480312952883968590039808, 5095703161752445949084183, 52862369054840906489032458, 548402468946989137626886645, 5642867165502977095645810854, 60077582327775786557191105797, 609361800623766461960919687325, 6298555665517553486725726717854]
[6, 5]
[0, 1, 28, 472, 7792, 97934, 1135660, 14834162, 159266390, 1781669805, 19745872648, 228140521135, 2478725570884, 26379988532354, 297133827668287, 3088047662406271, 32833259197782770, 347720046322636951, 3782714433980619137, 39820035926441414782, 414031923911160746654, 4459946390681058028934, 45870436554855255952915, 478528920012052785004142, 4979022733663356406618128, 52862356372487454895214343, 548402342304638126483743083, 5639937353283198835033037458, 59476572009997077882211232957, 609067330162014991061127968705, 6288167401956831075730859273239]
[7, 0]
[1, 2, 25, 381, 5648, 68893, 965001, 10787086, 125460793, 1401841016, 15507485038, 173892889696, 1948876827702, 21107004750064, 223612551309581, 2415999343094933, 25641007828765981, 281441739005408224, 2929553616259257874, 31040583783058389626, 325626422693525097265, 3419989862276212884295, 36231992403695785354267, 379802209504203819698307, 3985666563610435351361982, 41209487992549182629422360, 426827900061226562301244734, 4419434315728507640192059543, 46701381739032900063117854893, 478020105145490965428324945803, 4961212352330991515437316183935]
[7, 1]
[1, 6, 78, 780, 8110, 88500, 1219870, 15865600, 172539968, 1731378357, 17700998204, 189189870494, 2383125982820, 26133698711472, 261771343230968, 2684380968983890, 27311303300643582, 312355937793457211, 3463944584394735456, 35601953767056758691, 357533815140350476230, 3630857630320495382668, 37779610844512699452723, 425041907065853528823289, 4466458203133567081386951, 44618338243477807545984051, 452940874938696904182501635, 4603505594762070258781889621, 50198736040249262034751004601, 532922641777229881768673946230, 5403147555399084356218382285511]
[7, 2]
[0, 2, 32, 752, 8051, 88500, 984600, 11630400, 151004956, 1731277200, 17693302672, 184945218049, 2049485093130, 21884202483741, 261771115832026, 2654159875976645, 27310892224213832, 283308244555221459, 3022490448478019193, 33862717664619078382, 357524905452287316162, 3616096044778082900587, 37155361718610826104304, 390754201533875335193348, 4067256720922519257062602, 44615002147323622393703377, 452926620881024031796277066, 4587844591618134507244906377, 46877981882897401112520582002, 487039597815156850879822720337, 5266080005736790770523241933164]
[7, 3]
[0, 2, 28, 430, 8051, 88492, 974738, 11630383, 127478384, 1591931287, 17660643600, 184945215113, 1980278392686, 21377898645382, 228752947068295, 2651059378227450, 27310527974405944, 283106134049192629, 3019387088183460063, 31625362502476074870, 348049734186983053933, 3615136257368942300470, 36998957507338517202370, 387486491649978060196670, 3986792603742625997814037, 41735379124070902004799090, 449837181933079970582104805, 4577735618037681059390970224, 46802753335038656499854386178, 487010005604531183489215431665, 5018057105178001109563306330253]
[7, 4]
[0, 1, 28, 430, 6047, 88296, 965000, 11630347, 125480000, 1407624801, 17660299864, 184666031090, 1949167908510, 21377239972530, 228441196782410, 2487517888462580, 27310527973598975, 283106054946074662, 3011076142524411632, 31120620488588141543, 327962317935941536555, 3612131317529933102576, 36960930792918110573472, 380594594233042078452575, 3985834697584601982285263, 41395096385504451603020184, 436957019354299011196766828, 4577286361550304008838349551, 46801617430924682807097416459, 486881184665268733846506432674, 4987113481566397526370865404541]
[7, 5]
[0, 1, 28, 430, 5649, 87266, 965000, 10924285, 125480000, 1404549428, 15793795402, 184661800871, 1948922950960, 21300782832428, 228439874081111, 2417740139508408, 27310527942304340, 282144405942988784, 2972279068997955805, 31120608681853113819, 325686674703165126747, 3462287588768112743296, 36960543171334196001997, 379831996450583231248461, 3985670485000432091737956, 41340947588645677371268945, 427109540750639968151691298, 4577285016667239708602472127, 46799030528549538811232959217, 486368401788157409062497692827, 4961218635023759683623964907660]
[7, 6]
[0, 1, 28, 402, 5649, 70452, 965000, 10806308, 125476702, 1401843466, 15676594033, 184661795894, 1948882592551, 21280350842800, 228439219364426, 2417740139427705, 25905396891838509, 281446506360443052, 2929632209731661992, 31066695222334957036, 325685924657652990733, 3419989862347559869333, 36960543167667485287638, 379824176805007286224579, 3985669766703621617211638, 41329191803312980103824816, 427104965075225917353573209, 4472837222595409375898469390, 46799006370315540059932519877, 478621614493220845244505892843, 4961215723788366126299752391373]
[8, 0]
[1, 2, 21, 310, 4739, 59654, 721098, 8542810, 97787707, 1115927419, 13521667388, 145372195516, 1563478173116, 17331793272252, 183326684061117, 1978416700882365, 21105930005745086, 223633326877388221, 2356801045758897599, 25671791008780217794, 270629757607314419136, 2818137674520461798847, 29820969440903708241345, 309307602792579861278146, 3235625752192776180297153, 33690523215566065324748228, 349442639807443869875531202, 3614157720517912072269032900, 37511422923515704670137576903, 396882258644508108750218554820, 4071732851123961229203258174915]
[8, 1]
[1, 5, 66, 870, 9418, 95404, 1020178, 10910114, 116961408, 1269319104, 15420668802, 186335569154, 2092258707459, 22324231147523, 223533368487937, 2300102388453377, 23678250753204227, 244218428740583426, 2521303233634959362, 26987371554266808324, 307381704052157972481, 3312167967401039364099, 34662251320016253747201, 352132946710859256692738, 3580993929556662847275012, 36151550056345656205770756, 369998943087644997308121092, 3791006228343139484888465411, 38829724147853438538318086146, 428005188847297506828343050243, 4528454022449639996752494854147]
[8, 2]
[0, 2, 29, 381, 7124, 95373, 1020112, 10902625, 116961408, 1269319104, 13607942531, 155047253248, 1641958131714, 18648704704515, 217975554600962, 2300096106074114, 23675007796813825, 244187609128878083, 2521303226531643392, 26210740265861906435, 279711585926283001859, 2902447824095134089218, 30494440078365576134661, 338547063815532455133187, 3560961916499477187788801, 36125179996591085238353924, 369092248722919565681491969, 3791005696884324459807244289, 38733214357050152443388624898, 398277592615671175209692430339, 4162275061228438708256216449026]
[8, 3]
[0, 1, 29, 381, 5075, 63918, 971537, 10902241, 116953473, 1262686145, 13539799424, 151967442178, 1641152821249, 17340401500161, 188344290390017, 2170897047359490, 23541908635230209, 243975985889525762, 2521303173503582210, 26194734692110041089, 271945273057034108929, 2901583130260266549252, 29939173041882216792066, 314049571512541934256131, 3333146630949991994097667, 36125178266081207951294465, 368828628825374481058889731, 3785179414964811973682790403, 38733213799036144213674688513, 397312795729494474951145553921, 4162259662471593636724647919620]
[8, 4]
[0, 1, 26, 381, 4755, 62053, 754449, 10416353, 116928577, 1252198850, 13523801473, 146455220993, 1635778152450, 17333126389762, 188343491354627, 1993331687067651, 22106987706359810, 242568603890958340, 2519252240709910530, 26192725864872542208, 271945272702129668099, 2895818520444168568834, 29931803566205061038083, 314030922173988236951554, 3236253103937606641516546, 34035718740737068781010949, 368828607838599311056175107, 3771578999494112416582598658, 38732979413418482214763495429, 397312795683377614743652007939, 4132037974362306941130373070854]
[8, 5]
[0, 1, 20, 374, 4738, 62052, 753872, 8804960, 116126274, 1250426306, 13523022208, 145523411715, 1632197982209, 17331810058241, 188287656763393, 1978494012395521, 21106490375577602, 233561403058503682, 2519039379033489411, 26104662699562631169, 271929331982013300738, 2858925012230660161539, 29929803302553834225665, 310138859550804502642690, 3236251086324973562757121, 33704710365076977753260034, 352771673583441351882571780, 3770361747262021455231057923, 38713870975677183393735376897, 397312795351332306645457829892, 4073127952114241036450256650241]
[8, 6]
[0, 1, 20, 373, 4738, 62052, 738065, 8581345, 99885377, 1250328001, 13523019137, 145381182209, 1601405499393, 17331800784897, 186638389207042, 1978494010724353, 21105998742265857, 223633395596869632, 2510204908743884802, 26048610146534424577, 271496986414564507650, 2818155688920055808001, 29929803278063834234882, 309308555691062882992130, 3235699557423071344197638, 33701940171669964601688064, 349484656471512754788761603, 3685703883323617320787509251, 38713867991782628793121767426, 397194394407746599290968997892, 4073025465266024431629950255109]
[8, 7]
[0, 1, 20, 350, 4738, 62052, 721104, 8542816, 99221825, 1176403393, 13523010945, 145381180160, 1563478173696, 17331793272832, 183339854176257, 1978482359373826, 21105940483448834, 223633362806456321, 2366089719996940290, 26048367154463113218, 270632115350116499459, 2818140398861121486850, 29894765705872778199042, 309308555623536970956802, 3235660646082689049296897, 33701940171669964601688064, 349446529532967592010973185, 3614157732169292206051426307, 38713397461057074648068390916, 397155707275698684902185631747, 4072715239424805790426115080194]
[9, 0]
[1, 2, 21, 301, 4001, 50811, 608101, 7581484, 86847741, 973625119, 10737984611, 121300162063, 1313025375091, 14165121658939, 154499378091128, 1645112030235001, 17682729924089026, 186827442950568116, 1987010557675808585, 21038961724893534431, 221795974919858695488, 2346479788820259967782, 25406697032946060893098, 264068487953027095437341, 2740806474946690930412742, 28417913827559426332313787, 294976925719955238471230857, 3056240187510650316378020874, 32142942436719416631968001090, 331494841849074186723261611914, 3415123974957782402342373243177]
[9, 1]
[1, 4, 50, 663, 8260, 99109, 1143090, 12527839, 135246289, 1409108421, 14660616984, 155444059591, 1630739921525, 17024720710829, 180215825517231, 1876739468499213, 19764853172536251, 205589163931606489, 2155867004951010588, 22558669798425164931, 235436287048196113944, 2460489043375692066252, 26752599254052604541911, 294272850260761602792780, 3112641278712249425091604, 32764467158341991897094435, 344095897737184879884337351, 3596843315781575484981559027, 36918489296419678748627212344, 379144290872420566267722670492, 3844334443631408268993122982013]
[9, 2]
[0, 1, 22, 390, 4819, 57508, 674529, 8178624, 105633660, 1242423463, 14199075590, 153071555631, 1630715025092, 17024720656758, 180215824612925, 1876739161047531, 19764535935738235, 205586904471988091, 2155866990727562950, 22558667365361933382, 234107582597019724440, 2441125857514994917013, 25420374302574773229657, 267236552503520584934116, 2830531561546103452320004, 29225200535877994572766137, 302218510988585783455384456, 3115197559749843710226384131, 32731708232200714434912562688, 351487752411994433553171503806, 3699655842625692803369545185276]
[9, 3]
[0, 1, 20, 331, 4819, 57380, 674342, 7739021, 87386480, 1016904960, 11169049600, 127547317174, 1500996867498, 16846699323194, 178278702091218, 1876653379729479, 19675870461406530, 205586448024278969, 2155866471471885592, 22502308898588165141, 234066991172760885451, 2440686588940689581005, 25414615527610074979580, 264190116304149410041220, 2793567789065871849266524, 29218305796612380576979975, 302165862893741196261707763, 3115197175008560184091297139, 32151965626693078225755968892, 332606235726771923174016205804, 3462290670661743000787618401932]
[9, 4]
[0, 1, 20, 300, 4607, 57380, 673800, 7737919, 87383719, 1016904960, 11169049600, 121690305913, 1344091521661, 14451473763834, 163007533442700, 1846997584246844, 19558644769844894, 205586447702642454, 2155864445646470642, 22408549852548766899, 234066991172760885431, 2440672691108770710675, 25407861254740594065985, 264181110626031307898742, 2749163537805585922689463, 29165128158590512477703952, 301660051405389833359031578, 3115196566311102165705274967, 32151965626693076923945885883, 331518938368943064707369883211, 3462290670661743000781431864531]
[9, 5]
[0, 1, 20, 300, 4081, 57373, 673800, 7737919, 87379345, 983783657, 11169049600, 121689951619, 1316900342867, 14451375693401, 154513713187433, 1670562112625439, 18420485086740073, 205523340066526863, 2155220314806458544, 22401358570244415690, 234066972050708120133, 2440669705836476759690, 25406860612697208395304, 264080647702880377275629, 2741792344418841077925563, 28497781743220895660131277, 301447324585452093842925624, 3115191197388674116190203739, 32151885957474788074193197808, 331518859574732990492685688448, 3441645389499140982549347451612]
[9, 6]
[0, 1, 20, 300, 4038, 52396, 673768, 7737919, 87379190, 973804376, 11168917106, 121347998860, 1316899586541, 14447972876554, 154511001243799, 1669046749703805, 17682744333799008, 188891894838895930, 2088318925434345684, 22389813725383601031, 234066968013538887691, 2440669699175785313154, 25406792564877423197861, 264080647692712890874152, 2741791293174306720467394, 28497692578937105237671325, 298061682223744831915224183, 3115155692089733483645150320, 32151566891699300686718654991, 331514233120967823159538879349, 3415188276680590349287635359848]
[9, 7]
[0, 1, 20, 300, 4000, 50810, 669878, 7699583, 87379190, 973798544, 11065639768, 121302478642, 1315872756108, 14447938617528, 154510815236742, 1661409960071225, 17682744333798612, 188886354659473105, 1988886500372792144, 21582999983663260326, 234066968013538395616, 2440669680135384091311, 25406697032946103940671, 264080647494669049994993, 2741264009230325529043007, 28497684481894681312085833, 294977910561297068395162834, 3114469690956784415224109693, 32151167962207768482105882506, 331512397520078761901222175598, 3415130844821712477673531116257]
[9, 8]
[0, 1, 20, 300, 4000, 50810, 610829, 7678861, 86936835, 973798461, 10737984702, 121302478460, 1313025375090, 14280377642108, 154510815065009, 1645112030235000, 17682744269589068, 188760173941895112, 1988242324204541280, 21038961898509042090, 224647891370179246927, 2440669680135383956151, 25406697032946093023038, 264071691000766107154772, 2740806474946690930417196, 28447108593585004471954536, 294977379756229007263306443, 3067742528047295519192799679, 32149413185490152352485829679, 331512397495398021067430144059, 3415129408923622653633163259227]
[10, 0]
[1, 2, 12, 193, 2894, 38895, 488896, 5888897, 68888898, 788888899, 8888888900, 98888888901, 1088888888902, 11888888888903, 128888888888904, 1388888888888905, 14888888888888906, 158888888888888907, 1688888888888888908, 17888888888888888909, 188888888888888888910, 1988888888888888888911, 20888888888888888888912, 218888888888888888888913, 2288888888888888888888914, 23888888888888888888888915, 248888888888888888888888916, 2588888888888888888888888917, 26888888888888888888888888918, 278888888888888888888888888919, 2888888888888888888888888888920]
[10, 1]
[1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 110000000001, 1200000000001, 13000000000001, 140000000000001, 1500000000000001, 16000000000000001, 170000000000000001, 1800000000000000001, 19000000000000000001, 200000000000000000001, 2100000000000000000001, 22000000000000000000001, 230000000000000000000001, 2400000000000000000000001, 25000000000000000000000001, 260000000000000000000000001, 2700000000000000000000000001, 28000000000000000000000000001, 290000000000000000000000000001, 3000000000000000000000000000001]
[10, 2]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 3]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 4]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 5]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 6]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 7]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 8]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]
[10, 9]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000, 260000000000000000000000000, 2700000000000000000000000000, 28000000000000000000000000000, 290000000000000000000000000000, 3000000000000000000000000000000]

2015年10月22日木曜日

151022(2)

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

Number of times k is used in writing out all the numbers 1 through n(11)
のコードを見れば、
Number of times k is used in writing out all the numbers 1 through n(10)
で気づいた
「m進法で1からm0 0…0 (s桁) までの0の個数」
= 「m進法で1からm0 0…0 (s - 1桁) までの桁数の合計」
を示すには、次を示せばよいことが分かる。

((m0 - 1)m^(s - 1) + 1)s + ((s - 1)m^s - sm^(s- 1) + 1) / (m - 1) - ((m - 1)m0(s - 1)m^(s - 2) + 1 + (m0 - 1)m^(s - 1))
= ((m0 - 1)m^(s - 2) + 1)(s - 1) + ((s - 2)m^(s - 1) - (s - 1)m^(s- 2) + 1) / (m - 1)

すなわち次を示せばよい。

(m - 1)^2 (s - 1)m^(s - 2)
= (s - 1)m^s - sm^(s- 1) - ((s - 2)m^(s - 1) - (s - 1)m^(s- 2))

これを示そう。

(右辺)
= m^(s - 2) ((s - 1)m^2 - sm - (s - 2)m + (s - 1))
= m^(s - 2) (s - 1)(m^2 - 2m + 1)
= (左辺)

151022

Ruby


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

f(m, k, m0 * m ** i) を調べてみた。
total と f(m, 0, m0 * m ** i) に面白い関係がある。

# 高速化(ただし、0 < k ≦ m - 1)
def g(m, k, str, s)
  if s == 1
    return 0 if str.to_i < k
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  if a < k
    b = 0
  elsif a == k
    b = 1 + str1.to_i(m)
  else
    b = m ** (s - 1)
  end
  return a * (s - 1) * m ** (s - 2) + b + g(m, k, str1, s - 1)
end

# 0 < k ≦ m - 1におけるg(m, k, str, s)の和
def g_sum(m, str, s)
  return str.to_i if s == 1
  a = str[0].to_i
  str1 = str[1..-1]
  b = 0
  b += 1 + str1.to_i(m) + (a - 1) * m ** (s - 1) if a > 0
  return (m - 1) * a * (s - 1) * m ** (s - 2) + b + g_sum(m, str1, s - 1)
end

# 1からnまでをm進法で表したときの桁数の合計
def g_total(m, n)
  s = n.to_s(m).size
  (n - m ** (s - 1) + 1) * s + ((s - 1) * m ** s - s * m ** (s - 1) + 1) / (m - 1)
end

# 0 ≦ k ≦ m - 1
def f(m, k, n)
  str = n.to_s(m)
  return g(m, k, str, str.size) if k > 0
  # k = 0のときは、桁数の合計から0以外の数字が現れた回数を除く
  return g_total(m, n) - g_sum(m, str, str.size)
end

def f_ary(m, k, ary)
  ary.map{|i| f(m, k, i)}
end

(2..10).each{|m|
  ary = []
  (0..8).each{|i|
    (1..m - 1).each{|m0|
      ary << m0 * m ** i
    }
  }
  p [m, 'total']
  p ary.map{|n| g_total(m, n)}
  (0..m - 1).each{|k|
    p [m, k]
    p f_ary(m, k, ary)
  }
}

出力結果
[2, "total"]
[1, 3, 8, 21, 54, 135, 328, 777, 1802]
[2, 0]
[0, 1, 3, 8, 21, 54, 135, 328, 777]
[2, 1]
[1, 2, 5, 13, 33, 81, 193, 449, 1025]
[3, "total"]
[1, 2, 4, 10, 17, 44, 72, 180, 289, 694, 1100, 2558, 4017, 9120, 14224, 31720, 49217, 108266]
[3, 0]
[0, 0, 1, 2, 4, 10, 17, 44, 72, 180, 289, 694, 1100, 2558, 4017, 9120, 14224, 31720]
[3, 1]
[1, 1, 2, 5, 7, 21, 28, 81, 109, 297, 406, 1053, 1459, 3645, 5104, 12393, 17497, 41553]
[3, 2]
[0, 1, 1, 3, 6, 13, 27, 55, 108, 217, 405, 811, 1458, 2917, 5103, 10207, 17496, 34993]
[4, "total"]
[1, 2, 3, 5, 13, 21, 30, 78, 126, 175, 431, 687, 944, 2224, 3504, 4785, 10929, 17073, 23218, 51890, 80562, 109235, 240307, 371379, 502452, 1092276, 1682100]
[4, 0]
[0, 0, 0, 1, 2, 3, 5, 13, 21, 30, 78, 126, 175, 431, 687, 944, 2224, 3504, 4785, 10929, 17073, 23218, 51890, 80562, 109235, 240307, 371379]
[4, 1]
[1, 1, 1, 2, 6, 7, 9, 32, 40, 49, 160, 208, 257, 768, 1024, 1281, 3584, 4864, 6145, 16384, 22528, 28673, 73728, 102400, 131073, 327680, 458752]
[4, 2]
[0, 1, 1, 1, 3, 7, 8, 17, 40, 48, 97, 208, 256, 513, 1024, 1280, 2561, 4864, 6144, 12289, 22528, 28672, 57345, 102400, 131072, 262145, 458752]
[4, 3]
[0, 0, 1, 1, 2, 4, 8, 16, 25, 48, 96, 145, 256, 512, 769, 1280, 2560, 3841, 6144, 12288, 18433, 28672, 57344, 86017, 131072, 262144, 393217]
[5, "total"]
[1, 2, 3, 4, 6, 16, 26, 36, 47, 122, 197, 272, 348, 848, 1348, 1848, 2349, 5474, 8599, 11724, 14850, 33600, 52350, 71100, 89851, 199226, 308601, 417976, 527352, 1152352, 1777352, 2402352, 3027353, 6542978, 10058603, 13574228]
[5, 0]
[0, 0, 0, 0, 1, 2, 3, 4, 6, 16, 26, 36, 47, 122, 197, 272, 348, 848, 1348, 1848, 2349, 5474, 8599, 11724, 14850, 33600, 52350, 71100, 89851, 199226, 308601, 417976, 527352, 1152352, 1777352, 2402352]
[5, 1]
[1, 1, 1, 1, 2, 7, 8, 9, 11, 45, 55, 65, 76, 275, 350, 425, 501, 1625, 2125, 2625, 3126, 9375, 12500, 15625, 18751, 53125, 71875, 90625, 109376, 296875, 406250, 515625, 625001, 1640625, 2265625, 2890625]
[5, 2]
[0, 1, 1, 1, 1, 3, 8, 9, 10, 21, 55, 65, 75, 151, 350, 425, 500, 1001, 2125, 2625, 3125, 6251, 12500, 15625, 18750, 37501, 71875, 90625, 109375, 218751, 406250, 515625, 625000, 1250001, 2265625, 2890625]
[5, 3]
[0, 0, 1, 1, 1, 2, 4, 9, 10, 20, 31, 65, 75, 150, 226, 425, 500, 1000, 1501, 2625, 3125, 6250, 9376, 15625, 18750, 37500, 56251, 90625, 109375, 218750, 328126, 515625, 625000, 1250000, 1875001, 2890625]
[5, 4]
[0, 0, 0, 1, 1, 2, 3, 5, 10, 20, 30, 41, 75, 150, 225, 301, 500, 1000, 1500, 2001, 3125, 6250, 9375, 12501, 18750, 37500, 56250, 75001, 109375, 218750, 328125, 437501, 625000, 1250000, 1875000, 2500001]
[6, "total"]
[1, 2, 3, 4, 5, 7, 19, 31, 43, 55, 68, 176, 284, 392, 500, 609, 1473, 2337, 3201, 4065, 4930, 11410, 17890, 24370, 30850, 37331, 83987, 130643, 177299, 223955, 270612, 597204, 923796, 1250388, 1576980, 1903573, 4143061, 6382549, 8622037, 10861525, 13101014, 28217558, 43334102, 58450646, 73567190]
[6, 0]
[0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 7, 19, 31, 43, 55, 68, 176, 284, 392, 500, 609, 1473, 2337, 3201, 4065, 4930, 11410, 17890, 24370, 30850, 37331, 83987, 130643, 177299, 223955, 270612, 597204, 923796, 1250388, 1576980, 1903573, 4143061, 6382549, 8622037, 10861525]
[6, 1]
[1, 1, 1, 1, 1, 2, 8, 9, 10, 11, 13, 60, 72, 84, 96, 109, 432, 540, 648, 756, 865, 3024, 3888, 4752, 5616, 6481, 20736, 27216, 33696, 40176, 46657, 139968, 186624, 233280, 279936, 326593, 933120, 1259712, 1586304, 1912896, 2239489, 6158592, 8398080, 10637568, 12877056]
[6, 2]
[0, 1, 1, 1, 1, 1, 3, 9, 10, 11, 12, 25, 72, 84, 96, 108, 217, 540, 648, 756, 864, 1729, 3888, 4752, 5616, 6480, 12961, 27216, 33696, 40176, 46656, 93313, 186624, 233280, 279936, 326592, 653185, 1259712, 1586304, 1912896, 2239488, 4478977, 8398080, 10637568, 12877056]
[6, 3]
[0, 0, 1, 1, 1, 1, 2, 4, 10, 11, 12, 24, 37, 84, 96, 108, 216, 325, 648, 756, 864, 1728, 2593, 4752, 5616, 6480, 12960, 19441, 33696, 40176, 46656, 93312, 139969, 233280, 279936, 326592, 653184, 979777, 1586304, 1912896, 2239488, 4478976, 6718465, 10637568, 12877056]
[6, 4]
[0, 0, 0, 1, 1, 1, 2, 3, 5, 11, 12, 24, 36, 49, 96, 108, 216, 324, 433, 756, 864, 1728, 2592, 3457, 5616, 6480, 12960, 19440, 25921, 40176, 46656, 93312, 139968, 186625, 279936, 326592, 653184, 979776, 1306369, 1912896, 2239488, 4478976, 6718464, 8957953, 12877056]
[6, 5]
[0, 0, 0, 0, 1, 1, 2, 3, 4, 6, 12, 24, 36, 48, 61, 108, 216, 324, 432, 541, 864, 1728, 2592, 3456, 4321, 6480, 12960, 19440, 25920, 32401, 46656, 93312, 139968, 186624, 233281, 326592, 653184, 979776, 1306368, 1632961, 2239488, 4478976, 6718464, 8957952, 11197441]
[7, "total"]
[1, 2, 3, 4, 5, 6, 8, 22, 36, 50, 64, 78, 93, 240, 387, 534, 681, 828, 976, 2348, 3720, 5092, 6464, 7836, 9209, 21214, 33219, 45224, 57229, 69234, 81240, 182082, 282924, 383766, 484608, 585450, 686293, 1509836, 2333379, 3156922, 3980465, 4804008, 5627552, 12215896, 18804240, 25392584, 31980928, 38569272, 45157617, 97040826, 148924035, 200807244, 252690453, 304573662]
[7, 0]
[0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 22, 36, 50, 64, 78, 93, 240, 387, 534, 681, 828, 976, 2348, 3720, 5092, 6464, 7836, 9209, 21214, 33219, 45224, 57229, 69234, 81240, 182082, 282924, 383766, 484608, 585450, 686293, 1509836, 2333379, 3156922, 3980465, 4804008, 5627552, 12215896, 18804240, 25392584, 31980928, 38569272]
[7, 1]
[1, 1, 1, 1, 1, 1, 2, 9, 10, 11, 12, 13, 15, 77, 91, 105, 119, 133, 148, 637, 784, 931, 1078, 1225, 1373, 5145, 6517, 7889, 9261, 10633, 12006, 40817, 52822, 64827, 76832, 88837, 100843, 319333, 420175, 521017, 621859, 722701, 823544, 2470629, 3294172, 4117715, 4941258, 5764801, 6588345, 18941489, 25529833, 32118177, 38706521, 45294865]
[7, 2]
[0, 1, 1, 1, 1, 1, 1, 3, 10, 11, 12, 13, 14, 29, 91, 105, 119, 133, 147, 295, 784, 931, 1078, 1225, 1372, 2745, 6517, 7889, 9261, 10633, 12005, 24011, 52822, 64827, 76832, 88837, 100842, 201685, 420175, 521017, 621859, 722701, 823543, 1647087, 3294172, 4117715, 4941258, 5764801, 6588344, 13176689, 25529833, 32118177, 38706521, 45294865]
[7, 3]
[0, 0, 1, 1, 1, 1, 1, 2, 4, 11, 12, 13, 14, 28, 43, 105, 119, 133, 147, 294, 442, 931, 1078, 1225, 1372, 2744, 4117, 7889, 9261, 10633, 12005, 24010, 36016, 64827, 76832, 88837, 100842, 201684, 302527, 521017, 621859, 722701, 823543, 1647086, 2470630, 4117715, 4941258, 5764801, 6588344, 13176688, 19765033, 32118177, 38706521, 45294865]
[7, 4]
[0, 0, 0, 1, 1, 1, 1, 2, 3, 5, 12, 13, 14, 28, 42, 57, 119, 133, 147, 294, 441, 589, 1078, 1225, 1372, 2744, 4116, 5489, 9261, 10633, 12005, 24010, 36015, 48021, 76832, 88837, 100842, 201684, 302526, 403369, 621859, 722701, 823543, 1647086, 2470629, 3294173, 4941258, 5764801, 6588344, 13176688, 19765032, 26353377, 38706521, 45294865]
[7, 5]
[0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 6, 13, 14, 28, 42, 56, 71, 133, 147, 294, 441, 588, 736, 1225, 1372, 2744, 4116, 5488, 6861, 10633, 12005, 24010, 36015, 48020, 60026, 88837, 100842, 201684, 302526, 403368, 504211, 722701, 823543, 1647086, 2470629, 3294172, 4117716, 5764801, 6588344, 13176688, 19765032, 26353376, 32941721, 45294865]
[7, 6]
[0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 14, 28, 42, 56, 70, 85, 147, 294, 441, 588, 735, 883, 1372, 2744, 4116, 5488, 6860, 8233, 12005, 24010, 36015, 48020, 60025, 72031, 100842, 201684, 302526, 403368, 504210, 605053, 823543, 1647086, 2470629, 3294172, 4117715, 4941259, 6588344, 13176688, 19765032, 26353376, 32941720, 39530065]
[8, "total"]
[1, 2, 3, 4, 5, 6, 7, 9, 25, 41, 57, 73, 89, 105, 122, 314, 506, 698, 890, 1082, 1274, 1467, 3515, 5563, 7611, 9659, 11707, 13755, 15804, 36284, 56764, 77244, 97724, 118204, 138684, 159165, 355773, 552381, 748989, 945597, 1142205, 1338813, 1535422, 3370430, 5205438, 7040446, 8875454, 10710462, 12545470, 14380479, 31157695, 47934911, 64712127, 81489343, 98266559, 115043775, 131820992, 282815936, 433810880, 584805824, 735800768, 886795712, 1037790656]
[8, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 9, 25, 41, 57, 73, 89, 105, 122, 314, 506, 698, 890, 1082, 1274, 1467, 3515, 5563, 7611, 9659, 11707, 13755, 15804, 36284, 56764, 77244, 97724, 118204, 138684, 159165, 355773, 552381, 748989, 945597, 1142205, 1338813, 1535422, 3370430, 5205438, 7040446, 8875454, 10710462, 12545470, 14380479, 31157695, 47934911, 64712127, 81489343, 98266559, 115043775]
[8, 1]
[1, 1, 1, 1, 1, 1, 1, 2, 10, 11, 12, 13, 14, 15, 17, 96, 112, 128, 144, 160, 176, 193, 896, 1088, 1280, 1472, 1664, 1856, 2049, 8192, 10240, 12288, 14336, 16384, 18432, 20481, 73728, 94208, 114688, 135168, 155648, 176128, 196609, 655360, 851968, 1048576, 1245184, 1441792, 1638400, 1835009, 5767168, 7602176, 9437184, 11272192, 13107200, 14942208, 16777217, 50331648, 67108864, 83886080, 100663296, 117440512, 134217728]
[8, 2]
[0, 1, 1, 1, 1, 1, 1, 1, 3, 11, 12, 13, 14, 15, 16, 33, 112, 128, 144, 160, 176, 192, 385, 1088, 1280, 1472, 1664, 1856, 2048, 4097, 10240, 12288, 14336, 16384, 18432, 20480, 40961, 94208, 114688, 135168, 155648, 176128, 196608, 393217, 851968, 1048576, 1245184, 1441792, 1638400, 1835008, 3670017, 7602176, 9437184, 11272192, 13107200, 14942208, 16777216, 33554433, 67108864, 83886080, 100663296, 117440512, 134217728]
[8, 3]
[0, 0, 1, 1, 1, 1, 1, 1, 2, 4, 12, 13, 14, 15, 16, 32, 49, 128, 144, 160, 176, 192, 384, 577, 1280, 1472, 1664, 1856, 2048, 4096, 6145, 12288, 14336, 16384, 18432, 20480, 40960, 61441, 114688, 135168, 155648, 176128, 196608, 393216, 589825, 1048576, 1245184, 1441792, 1638400, 1835008, 3670016, 5505025, 9437184, 11272192, 13107200, 14942208, 16777216, 33554432, 50331649, 83886080, 100663296, 117440512, 134217728]
[8, 4]
[0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 5, 13, 14, 15, 16, 32, 48, 65, 144, 160, 176, 192, 384, 576, 769, 1472, 1664, 1856, 2048, 4096, 6144, 8193, 14336, 16384, 18432, 20480, 40960, 61440, 81921, 135168, 155648, 176128, 196608, 393216, 589824, 786433, 1245184, 1441792, 1638400, 1835008, 3670016, 5505024, 7340033, 11272192, 13107200, 14942208, 16777216, 33554432, 50331648, 67108865, 100663296, 117440512, 134217728]
[8, 5]
[0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 6, 14, 15, 16, 32, 48, 64, 81, 160, 176, 192, 384, 576, 768, 961, 1664, 1856, 2048, 4096, 6144, 8192, 10241, 16384, 18432, 20480, 40960, 61440, 81920, 102401, 155648, 176128, 196608, 393216, 589824, 786432, 983041, 1441792, 1638400, 1835008, 3670016, 5505024, 7340032, 9175041, 13107200, 14942208, 16777216, 33554432, 50331648, 67108864, 83886081, 117440512, 134217728]
[8, 6]
[0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 7, 15, 16, 32, 48, 64, 80, 97, 176, 192, 384, 576, 768, 960, 1153, 1856, 2048, 4096, 6144, 8192, 10240, 12289, 18432, 20480, 40960, 61440, 81920, 102400, 122881, 176128, 196608, 393216, 589824, 786432, 983040, 1179649, 1638400, 1835008, 3670016, 5505024, 7340032, 9175040, 11010049, 14942208, 16777216, 33554432, 50331648, 67108864, 83886080, 100663297, 134217728]
[8, 7]
[0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 8, 16, 32, 48, 64, 80, 96, 113, 192, 384, 576, 768, 960, 1152, 1345, 2048, 4096, 6144, 8192, 10240, 12288, 14337, 20480, 40960, 61440, 81920, 102400, 122880, 143361, 196608, 393216, 589824, 786432, 983040, 1179648, 1376257, 1835008, 3670016, 5505024, 7340032, 9175040, 11010048, 12845057, 16777216, 33554432, 50331648, 67108864, 83886080, 100663296, 117440513]
[9, "total"]
[1, 2, 3, 4, 5, 6, 7, 8, 10, 28, 46, 64, 82, 100, 118, 136, 155, 398, 641, 884, 1127, 1370, 1613, 1856, 2100, 5016, 7932, 10848, 13764, 16680, 19596, 22512, 25429, 58234, 91039, 123844, 156649, 189454, 222259, 255064, 287870, 642164, 996458, 1350752, 1705046, 2059340, 2413634, 2767928, 3122223, 6842310, 10562397, 14282484, 18002571, 21722658, 25442745, 29162832, 32882920, 71146672, 109410424, 147674176, 185937928, 224201680, 262465432, 300729184, 338992937, 726413426, 1113833915, 1501254404, 1888674893, 2276095382, 2663515871, 3050936360]
[9, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 28, 46, 64, 82, 100, 118, 136, 155, 398, 641, 884, 1127, 1370, 1613, 1856, 2100, 5016, 7932, 10848, 13764, 16680, 19596, 22512, 25429, 58234, 91039, 123844, 156649, 189454, 222259, 255064, 287870, 642164, 996458, 1350752, 1705046, 2059340, 2413634, 2767928, 3122223, 6842310, 10562397, 14282484, 18002571, 21722658, 25442745, 29162832, 32882920, 71146672, 109410424, 147674176, 185937928, 224201680, 262465432, 300729184]
[9, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 11, 12, 13, 14, 15, 16, 17, 19, 117, 135, 153, 171, 189, 207, 225, 244, 1215, 1458, 1701, 1944, 2187, 2430, 2673, 2917, 12393, 15309, 18225, 21141, 24057, 26973, 29889, 32806, 124659, 157464, 190269, 223074, 255879, 288684, 321489, 354295, 1240029, 1594323, 1948617, 2302911, 2657205, 3011499, 3365793, 3720088, 12223143, 15943230, 19663317, 23383404, 27103491, 30823578, 34543665, 38263753, 119574225, 157837977, 196101729, 234365481, 272629233, 310892985, 349156737]
[9, 2]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 3, 12, 13, 14, 15, 16, 17, 18, 37, 135, 153, 171, 189, 207, 225, 243, 487, 1458, 1701, 1944, 2187, 2430, 2673, 2916, 5833, 15309, 18225, 21141, 24057, 26973, 29889, 32805, 65611, 157464, 190269, 223074, 255879, 288684, 321489, 354294, 708589, 1594323, 1948617, 2302911, 2657205, 3011499, 3365793, 3720087, 7440175, 15943230, 19663317, 23383404, 27103491, 30823578, 34543665, 38263752, 76527505, 157837977, 196101729, 234365481, 272629233, 310892985, 349156737]
[9, 3]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 4, 13, 14, 15, 16, 17, 18, 36, 55, 153, 171, 189, 207, 225, 243, 486, 730, 1701, 1944, 2187, 2430, 2673, 2916, 5832, 8749, 18225, 21141, 24057, 26973, 29889, 32805, 65610, 98416, 190269, 223074, 255879, 288684, 321489, 354294, 708588, 1062883, 1948617, 2302911, 2657205, 3011499, 3365793, 3720087, 7440174, 11160262, 19663317, 23383404, 27103491, 30823578, 34543665, 38263752, 76527504, 114791257, 196101729, 234365481, 272629233, 310892985, 349156737]
[9, 4]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 5, 14, 15, 16, 17, 18, 36, 54, 73, 171, 189, 207, 225, 243, 486, 729, 973, 1944, 2187, 2430, 2673, 2916, 5832, 8748, 11665, 21141, 24057, 26973, 29889, 32805, 65610, 98415, 131221, 223074, 255879, 288684, 321489, 354294, 708588, 1062882, 1417177, 2302911, 2657205, 3011499, 3365793, 3720087, 7440174, 11160261, 14880349, 23383404, 27103491, 30823578, 34543665, 38263752, 76527504, 114791256, 153055009, 234365481, 272629233, 310892985, 349156737]
[9, 5]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 4, 6, 15, 16, 17, 18, 36, 54, 72, 91, 189, 207, 225, 243, 486, 729, 972, 1216, 2187, 2430, 2673, 2916, 5832, 8748, 11664, 14581, 24057, 26973, 29889, 32805, 65610, 98415, 131220, 164026, 255879, 288684, 321489, 354294, 708588, 1062882, 1417176, 1771471, 2657205, 3011499, 3365793, 3720087, 7440174, 11160261, 14880348, 18600436, 27103491, 30823578, 34543665, 38263752, 76527504, 114791256, 153055008, 191318761, 272629233, 310892985, 349156737]
[9, 6]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 16, 17, 18, 36, 54, 72, 90, 109, 207, 225, 243, 486, 729, 972, 1215, 1459, 2430, 2673, 2916, 5832, 8748, 11664, 14580, 17497, 26973, 29889, 32805, 65610, 98415, 131220, 164025, 196831, 288684, 321489, 354294, 708588, 1062882, 1417176, 1771470, 2125765, 3011499, 3365793, 3720087, 7440174, 11160261, 14880348, 18600435, 22320523, 30823578, 34543665, 38263752, 76527504, 114791256, 153055008, 191318760, 229582513, 310892985, 349156737]
[9, 7]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 17, 18, 36, 54, 72, 90, 108, 127, 225, 243, 486, 729, 972, 1215, 1458, 1702, 2673, 2916, 5832, 8748, 11664, 14580, 17496, 20413, 29889, 32805, 65610, 98415, 131220, 164025, 196830, 229636, 321489, 354294, 708588, 1062882, 1417176, 1771470, 2125764, 2480059, 3365793, 3720087, 7440174, 11160261, 14880348, 18600435, 22320522, 26040610, 34543665, 38263752, 76527504, 114791256, 153055008, 191318760, 229582512, 267846265, 349156737]
[9, 8]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 9, 18, 36, 54, 72, 90, 108, 126, 145, 243, 486, 729, 972, 1215, 1458, 1701, 1945, 2916, 5832, 8748, 11664, 14580, 17496, 20412, 23329, 32805, 65610, 98415, 131220, 164025, 196830, 229635, 262441, 354294, 708588, 1062882, 1417176, 1771470, 2125764, 2480058, 2834353, 3720087, 7440174, 11160261, 14880348, 18600435, 22320522, 26040609, 29760697, 38263752, 76527504, 114791256, 153055008, 191318760, 229582512, 267846264, 306110017]
[10, "total"]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 31, 51, 71, 91, 111, 131, 151, 171, 192, 492, 792, 1092, 1392, 1692, 1992, 2292, 2592, 2893, 6893, 10893, 14893, 18893, 22893, 26893, 30893, 34893, 38894, 88894, 138894, 188894, 238894, 288894, 338894, 388894, 438894, 488895, 1088895, 1688895, 2288895, 2888895, 3488895, 4088895, 4688895, 5288895, 5888896, 12888896, 19888896, 26888896, 33888896, 40888896, 47888896, 54888896, 61888896, 68888897, 148888897, 228888897, 308888897, 388888897, 468888897, 548888897, 628888897, 708888897, 788888898, 1688888898, 2588888898, 3488888898, 4388888898, 5288888898, 6188888898, 7088888898, 7988888898]
[10, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 31, 51, 71, 91, 111, 131, 151, 171, 192, 492, 792, 1092, 1392, 1692, 1992, 2292, 2592, 2893, 6893, 10893, 14893, 18893, 22893, 26893, 30893, 34893, 38894, 88894, 138894, 188894, 238894, 288894, 338894, 388894, 438894, 488895, 1088895, 1688895, 2288895, 2888895, 3488895, 4088895, 4688895, 5288895, 5888896, 12888896, 19888896, 26888896, 33888896, 40888896, 47888896, 54888896, 61888896, 68888897, 148888897, 228888897, 308888897, 388888897, 468888897, 548888897, 628888897, 708888897]
[10, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 12, 13, 14, 15, 16, 17, 18, 19, 21, 140, 160, 180, 200, 220, 240, 260, 280, 301, 1600, 1900, 2200, 2500, 2800, 3100, 3400, 3700, 4001, 18000, 22000, 26000, 30000, 34000, 38000, 42000, 46000, 50001, 200000, 250000, 300000, 350000, 400000, 450000, 500000, 550000, 600001, 2200000, 2800000, 3400000, 4000000, 4600000, 5200000, 5800000, 6400000, 7000001, 24000000, 31000000, 38000000, 45000000, 52000000, 59000000, 66000000, 73000000, 80000001, 260000000, 340000000, 420000000, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 2]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 13, 14, 15, 16, 17, 18, 19, 20, 41, 160, 180, 200, 220, 240, 260, 280, 300, 601, 1900, 2200, 2500, 2800, 3100, 3400, 3700, 4000, 8001, 22000, 26000, 30000, 34000, 38000, 42000, 46000, 50000, 100001, 250000, 300000, 350000, 400000, 450000, 500000, 550000, 600000, 1200001, 2800000, 3400000, 4000000, 4600000, 5200000, 5800000, 6400000, 7000000, 14000001, 31000000, 38000000, 45000000, 52000000, 59000000, 66000000, 73000000, 80000000, 160000001, 340000000, 420000000, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 3]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 14, 15, 16, 17, 18, 19, 20, 40, 61, 180, 200, 220, 240, 260, 280, 300, 600, 901, 2200, 2500, 2800, 3100, 3400, 3700, 4000, 8000, 12001, 26000, 30000, 34000, 38000, 42000, 46000, 50000, 100000, 150001, 300000, 350000, 400000, 450000, 500000, 550000, 600000, 1200000, 1800001, 3400000, 4000000, 4600000, 5200000, 5800000, 6400000, 7000000, 14000000, 21000001, 38000000, 45000000, 52000000, 59000000, 66000000, 73000000, 80000000, 160000000, 240000001, 420000000, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 4]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5, 15, 16, 17, 18, 19, 20, 40, 60, 81, 200, 220, 240, 260, 280, 300, 600, 900, 1201, 2500, 2800, 3100, 3400, 3700, 4000, 8000, 12000, 16001, 30000, 34000, 38000, 42000, 46000, 50000, 100000, 150000, 200001, 350000, 400000, 450000, 500000, 550000, 600000, 1200000, 1800000, 2400001, 4000000, 4600000, 5200000, 5800000, 6400000, 7000000, 14000000, 21000000, 28000001, 45000000, 52000000, 59000000, 66000000, 73000000, 80000000, 160000000, 240000000, 320000001, 500000000, 580000000, 660000000, 740000000, 820000000]
[10, 5]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 4, 6, 16, 17, 18, 19, 20, 40, 60, 80, 101, 220, 240, 260, 280, 300, 600, 900, 1200, 1501, 2800, 3100, 3400, 3700, 4000, 8000, 12000, 16000, 20001, 34000, 38000, 42000, 46000, 50000, 100000, 150000, 200000, 250001, 400000, 450000, 500000, 550000, 600000, 1200000, 1800000, 2400000, 3000001, 4600000, 5200000, 5800000, 6400000, 7000000, 14000000, 21000000, 28000000, 35000001, 52000000, 59000000, 66000000, 73000000, 80000000, 160000000, 240000000, 320000000, 400000001, 580000000, 660000000, 740000000, 820000000]
[10, 6]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 4, 5, 7, 17, 18, 19, 20, 40, 60, 80, 100, 121, 240, 260, 280, 300, 600, 900, 1200, 1500, 1801, 3100, 3400, 3700, 4000, 8000, 12000, 16000, 20000, 24001, 38000, 42000, 46000, 50000, 100000, 150000, 200000, 250000, 300001, 450000, 500000, 550000, 600000, 1200000, 1800000, 2400000, 3000000, 3600001, 5200000, 5800000, 6400000, 7000000, 14000000, 21000000, 28000000, 35000000, 42000001, 59000000, 66000000, 73000000, 80000000, 160000000, 240000000, 320000000, 400000000, 480000001, 660000000, 740000000, 820000000]
[10, 7]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 18, 19, 20, 40, 60, 80, 100, 120, 141, 260, 280, 300, 600, 900, 1200, 1500, 1800, 2101, 3400, 3700, 4000, 8000, 12000, 16000, 20000, 24000, 28001, 42000, 46000, 50000, 100000, 150000, 200000, 250000, 300000, 350001, 500000, 550000, 600000, 1200000, 1800000, 2400000, 3000000, 3600000, 4200001, 5800000, 6400000, 7000000, 14000000, 21000000, 28000000, 35000000, 42000000, 49000001, 66000000, 73000000, 80000000, 160000000, 240000000, 320000000, 400000000, 480000000, 560000001, 740000000, 820000000]
[10, 8]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 19, 20, 40, 60, 80, 100, 120, 140, 161, 280, 300, 600, 900, 1200, 1500, 1800, 2100, 2401, 3700, 4000, 8000, 12000, 16000, 20000, 24000, 28000, 32001, 46000, 50000, 100000, 150000, 200000, 250000, 300000, 350000, 400001, 550000, 600000, 1200000, 1800000, 2400000, 3000000, 3600000, 4200000, 4800001, 6400000, 7000000, 14000000, 21000000, 28000000, 35000000, 42000000, 49000000, 56000001, 73000000, 80000000, 160000000, 240000000, 320000000, 400000000, 480000000, 560000000, 640000001, 820000000]
[10, 9]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 20, 40, 60, 80, 100, 120, 140, 160, 181, 300, 600, 900, 1200, 1500, 1800, 2100, 2400, 2701, 4000, 8000, 12000, 16000, 20000, 24000, 28000, 32000, 36001, 50000, 100000, 150000, 200000, 250000, 300000, 350000, 400000, 450001, 600000, 1200000, 1800000, 2400000, 3000000, 3600000, 4200000, 4800000, 5400001, 7000000, 14000000, 21000000, 28000000, 35000000, 42000000, 49000000, 56000000, 63000001, 80000000, 160000000, 240000000, 320000000, 400000000, 480000000, 560000000, 640000000, 720000001]

2015年10月21日水曜日

151021

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

Number of times k is used in writing out all the numbers 1 through n(9)
のコードを見れば、
Number of times k is used in writing out all the numbers 1 through n(7)
で気づいた
「m進法で1から10…0 (s桁) までの0の個数」
= 「m進法で1から10…0 (s - 1桁) までの桁数の合計」
を示すには、次を示せばよいことが分かる。

s + ((s - 1)m^s - sm^(s- 1) + 1) / (m - 1) - ((m - 1)(s - 1)m^(s - 2) + 1)
= (s - 1) + ((s - 2)m^(s - 1) - (s - 1)m^(s- 2) + 1) / (m - 1)

すなわち次を示せばよい。

(m - 1)^2 (s - 1)m^(s - 2)
= (s - 1)m^s - sm^(s- 1) - ((s - 2)m^(s - 1) - (s - 1)m^(s- 2))

これを示そう。

(右辺)
= m^(s - 2) ((s - 1)m^2 - sm - (s - 2)m + (s - 1))
= m^(s - 2) (s - 1)(m^2 - 2m + 1)
= (左辺)

2015年10月20日火曜日

151020

Ruby


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

Number of times k is used in writing out all the numbers 1 through n(4)
のコードを工夫してみた。

# 高速化(ただし、0 < k ≦ m - 1)
def g(m, k, str, s)
  if s == 1
    return 0 if str.to_i < k
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  if a < k
    b = 0
  elsif a == k
    b = 1 + str1.to_i(m)
  else
    b = m ** (s - 1)
  end
  return a * (s - 1) * m ** (s - 2) + b + g(m, k, str1, s - 1)
end

# 0 < k ≦ m - 1におけるg(m, k, str, s)の和
def g_sum(m, str, s)
  return str.to_i if s == 1
  a = str[0].to_i
  str1 = str[1..-1]
  b = 0
  b += 1 + str1.to_i(m) + (a - 1) * m ** (s - 1) if a > 0
  return (m - 1) * a * (s - 1) * m ** (s - 2) + b + g_sum(m, str1, s - 1)
end

# 1からnまでをm進法で表したときの桁数の合計
def g_total(m, n)
  s = n.to_s(m).size
  (n - m ** (s - 1) + 1) * s + ((s - 1) * m ** s - s * m ** (s - 1) + 1) / (m - 1)
end

# 0 ≦ k ≦ m - 1
def f(m, k, n)
  str = n.to_s(m)
  return g(m, k, str, str.size) if k > 0
  # k = 0のときは、桁数の合計から0以外の数字が現れた回数を除く
  return g_total(m, n) - g_sum(m, str, str.size)
end

def f_ary(m, k, ary)
  ary.map{|i| f(m, k, i)}
end

ary = (0..25).map{|i| 10 ** i}
(2..10).each{|m|
  p [m, 'total']
  p ary.map{|n| g_total(m, n)}
  (0..m - 1).each{|k|
    p [m, k]
    p f_ary(m, k, ary)
  }
}

出力結果
[2, "total"]
[1, 29, 580, 8987, 123631, 1568946, 18951445, 223222809, 2565782300, 28926258207, 322820130851, 3562561046566, 38900488372265, 422407813955629, 4559262511644720, 48874100093157427, 521985601490518071, 5555884811924144186, 58847078495393153085, 621553255926290448449, 6552426047410323587140, 68819408379282588696647, 721110534068521419145291, 7548884272548171353161806, 78791074180385370825293905, 820657186886165933204701269]
[2, 0]
[0, 12, 261, 4049, 59018, 753916, 9066446, 108788177, 1251335184, 14079330066, 158527003672, 1752835390487, 19090546253852, 208098347208735, 2252849861951519, 24089352692482079, 257698738277646371, 2751668512654557222, 29085855711963906085, 307321301701485658158, 3250747955772179611690, 34097225207936917176362, 356740182741316423122994, 3749253699468361851732019, 39095688742747483198718003, 406175259971825928562016322]
[2, 1]
[1, 17, 319, 4938, 64613, 815030, 9884999, 114434632, 1314447116, 14846928141, 164293127179, 1809725656079, 19809942118413, 214309466746894, 2306412649693201, 24784747400675348, 264286863212871700, 2804216299269586964, 29761222783429247000, 314231954224804790291, 3301678091638143975450, 34722183171345671520285, 364370351327204996022297, 3799630573079809501429787, 39695385437637887626575902, 414481926914340004642684947]
[3, "total"]
[1, 20, 384, 5914, 80168, 1011438, 12202852, 142825562, 1635429936, 18418869286, 204769823420, 2258785231784, 24729067085862, 268561603772548, 2897054433952706, 31073489905574112, 331661409150166750, 3524952682351500476, 37324574141163503994, 393921167270471535640, 4145290505434243820438, 43522843646724583150724, 456705592820521248356154, 4780350335384691235205008, 49923153018462221116844678, 520308377166159990051601692]
[3, 0]
[0, 5, 112, 1830, 24856, 312299, 3780509, 44933595, 521626139, 5880056822, 65288716800, 729403871260, 8069935693754, 87955158771471, 950747326623765, 10126147772237068, 108084168326741432, 1141785638343655929, 12192227578518173960, 129047966872781701145, 1353915031388354912698, 14214508943285390237646, 150454979304746373557149, 1577741974974853061914468, 16498568363160802749548694, 171387305141808329923338624]
[3, 1]
[1, 9, 150, 2194, 30374, 379432, 4508710, 51180200, 572158742, 6417405502, 70402455152, 769364418852, 8452692931320, 91673681872620, 993534122918024, 10779360089419044, 114661242594171254, 1216758202087170334, 12767569182895088152, 133862436956018539886, 1405771200630725286006, 14663860400505783919608, 153796494936787179989436, 1614986483014523055902106, 16887592497038459726705624, 177308495497250974401699424]
[3, 2]
[0, 6, 122, 1890, 24938, 319707, 3913633, 46711767, 541645055, 6121406962, 69078651468, 760016941672, 8206438460788, 88932763128457, 952772984410917, 10167982043918000, 108915998229254064, 1166408841920674213, 12364777379750241882, 131010763441671294609, 1385604273415163621734, 14644474302933408993470, 152454118578987694809569, 1587621877395315117388434, 16536992158262958640590360, 171612576527100685726563644]
[4, "total"]
[1, 17, 319, 4664, 64546, 812628, 9650485, 114407607, 1310521529, 14642086074, 164273376956, 1808374031038, 19633496124095, 214135937985217, 2306175007763139, 24624700031052484, 263995200496839366, 2803923207949429448, 29615692831797717705, 313851085308763482827, 3301617364940215724749, 34606469459760862898894, 363703511356173806381776, 3799256181698780902107858, 39597024726795123608431315, 413552395628721977734900437]
[4, 0]
[0, 2, 65, 930, 14294, 187918, 2187936, 26908111, 311721392, 3432994224, 39525887923, 438139377842, 4694047261364, 51963626752693, 563444246338230, 5950299292388021, 64318496246508216, 689832613531986615, 7196883791014767287, 76667563571579759292, 815418493853503761081, 8458340839333464550072, 89018412185597045811900, 941665524969631256324797, 9715438621335639516949183, 101390308675072882998160066]
[4, 1]
[1, 7, 119, 1270, 19482, 242178, 2520434, 31973411, 366171397, 3790564097, 44245876996, 488164976133, 5056725669893, 56692742610948, 610964919316485, 6310200205451268, 69321688173772803, 732713250404499465, 7571981434117226501, 82037556623093661699, 854087328285483073545, 8814800381086001004552, 94722289936057215483909, 973215603996092086091784, 10042775926285679481323524, 107193424611029871262433293]
[4, 2]
[0, 6, 70, 1260, 16409, 192212, 2519665, 28590949, 316981761, 3780691462, 40955973891, 442578674180, 5012229937156, 53342413107206, 568083953840132, 6253853871202310, 65744857114017797, 691251639160799237, 7504413864019427335, 78097532626468995080, 816632322249796878341, 8759273688423124172807, 90277557077891309633546, 942335136382397704044551, 10025010846995401075064838, 102648822381928313568362502]
[4, 3]
[0, 2, 65, 1204, 14361, 190320, 2422450, 26935136, 315646979, 3637836291, 39545638146, 439491002883, 4870493255682, 52137155514370, 563681888268292, 6110346662010885, 64610158962540550, 690125704852144131, 7342413742646296582, 77048432487621066756, 815479220551432011782, 8574054550918273171463, 89685252156628235452421, 942039916350659855646726, 9813799332178403535093770, 102319839960690909905944576]
[5, "total"]
[1, 16, 272, 4224, 56100, 702352, 8511728, 97792980, 1138964856, 12694824232, 142370605484, 1561853027360, 17046325683612, 185231628417988, 1980790710449240, 21403953552246116, 227019767761230492, 2425494194030761744, 25627470970153808620, 270686774253845214872, 2853433871269226074248, 29835846781730651855500, 314179233908653259277376, 3270896169543266296386752, 34272404238581657409668004, 356362021192908287048339880]
[5, 0]
[0, 2, 36, 697, 9723, 133599, 1539850, 17964853, 211464853, 2363964854, 27106933605, 297575683605, 3329870605481, 35417419433608, 383416442871110, 4130332946777361, 43783256530761736, 470461692810058611, 4967175102233886738, 53233740806579589863, 554061484336853027366, 5848109316825866699243, 61451171278953552246119, 638078004717826843261742, 6697390648722648620605493, 69689764007925987243652371]
[5, 1]
[1, 7, 65, 1226, 13001, 165627, 2028125, 20171876, 268203127, 2645703125, 32294921876, 331865234377, 3689306640628, 40104003906250, 403492431640629, 4679504394531250, 46297943115234377, 525622406005859377, 5326352691650390626, 57214763641357421878, 600465202331542968751, 6073609542846679687504, 66583832740783691406250, 664710590839385986328129, 7260833132266998291015627, 73223027288913726806640626]
[5, 2]
[0, 3, 65, 850, 13000, 134376, 1840627, 19937500, 221328126, 2637890627, 28398437500, 328398437500, 3360693359376, 38648925781253, 397962646484375, 4234832763671878, 46295654296875001, 482975616455078127, 5279622650146484376, 53592174530029296877, 587362003326416015628, 5973327350616455078127, 62607814311981201171878, 661748609542846679687501, 6841735947132110595703127, 72742526531219482421875006]
[5, 3]
[0, 2, 65, 726, 10501, 134375, 1559375, 19859376, 218984375, 2633984375, 27412109376, 306279296877, 3336279296876, 35572753906252, 397962646484375, 4179687500000002, 46295501708984375, 475630035400390627, 5086095428466796878, 53411624908447265628, 557347488403320312503, 5973314476013183593750, 61840394973754882812502, 661399910449981689453127, 6771569001674652099609381, 70993635952472686767578126]
[5, 4]
[0, 2, 41, 725, 9875, 134375, 1543751, 19859375, 218984375, 2413281251, 27158203127, 297734375001, 3330175781251, 35488525390625, 397956542968751, 4179595947265625, 44347412109375003, 470804443359375002, 4968225097656250002, 53234470367431640626, 554197692871093750000, 5967486095428466796876, 61696020603179931640627, 644959053993225097656253, 6700875508785247802734376, 69713067412376403808593751]
[6, "total"]
[1, 15, 260, 3745, 50675, 644020, 7664085, 87984470, 1027440600, 11564643545, 127387861210, 1405963003100, 15435778018525, 166614668111070, 1779688008666335, 19268768311987425, 205612609871924450, 2173675659231546595, 23052323732335676645, 244313942394014059750, 2565883654364084358375, 26795301926184506150120, 282630869342642221403370, 2955785216055853328420075, 30734711296335119970520300, 320449606668064318938729710]
[6, 0]
[0, 1, 28, 472, 7792, 96602, 1135660, 13028618, 158363049, 1781669668, 19745872648, 227909003889, 2459990037720, 26379763779105, 280500235869852, 3085218547843454, 32833258280691482, 347683017078293947, 3782653531545490550, 39534227235118387853, 413735974024774674039, 4307326759431044312455, 45870435722012457184613, 478528913697009862151535, 4977878570157856366073921, 52862340470486562513187627]
[6, 1]
[1, 7, 71, 731, 11198, 145691, 1471583, 15044020, 209959005, 2215950297, 22357576982, 260732117894, 2964571630298, 29734482337166, 300804840123645, 3596403661788849, 37220596165405190, 373942198480119148, 4097855055721481385, 44696639571507276727, 447357911583038454820, 4507221089612289882735, 50957678725204529674292, 522423493113073904971028, 5237942923211234920118775, 55861845725776606242564250]
[6, 2]
[0, 2, 64, 731, 8015, 105724, 1468480, 15036280, 170401845, 2126695994, 22349164466, 230521001428, 2553734780882, 29686729820416, 300655135938110, 3205679939605408, 36193990212721421, 373397802196303303, 3808925198520288348, 40481495552137836674, 447357910133301379941, 4506949179057162814305, 47098247702572249166961, 511150472996604417121406, 5237921416451673325535601, 53086650812786108689970093]
[6, 3]
[0, 2, 35, 724, 8015, 99035, 1317036, 15036215, 169406949, 1844445489, 22150503153, 230377772246, 2492643173066, 28053573741924, 300332901443709, 3189692886768142, 33445910414365065, 370957646611641398, 3797461074214285846, 39955008728061630146, 429356627553235346921, 4506931335876576179484, 46855356118085672416370, 484840463353143769132156, 5206242491098553003089692, 52914044231686680108760939]
[6, 4]
[0, 2, 34, 615, 7863, 99034, 1135666, 15005175, 160043362, 1814212292, 21038871313, 228282586508, 2486112825675, 26380129900105, 300261067622732, 3103725613575301, 33085595600958522, 359974948542551848, 3782714438353511379, 39826535380747513568, 414043307158573756000, 4506927171526374932207, 45978714519912057008219, 480312952883968590039808, 5095703161752445949084183, 52862369054840906489032458]
[6, 5]
[0, 1, 28, 472, 7792, 97934, 1135660, 14834162, 159266390, 1781669805, 19745872648, 228140521135, 2478725570884, 26379988532354, 297133827668287, 3088047662406271, 32833259197782770, 347720046322636951, 3782714433980619137, 39820035926441414782, 414031923911160746654, 4459946390681058028934, 45870436554855255952915, 478528920012052785004142, 4979022733663356406618128, 52862356372487454895214343]
[7, "total"]
[1, 14, 246, 3604, 47204, 580398, 7039208, 83274408, 952920802, 10670445554, 117693118812, 1286962821206, 14208739748358, 154461178238416, 1661228247668816, 17728597733681610, 188100184135771162, 2006909022652786020, 21348363158569502014, 225438542109986513966, 2368069794769905597624, 24776488563389339183224, 259047939606077619976770, 2723335577242543339837228, 28463349040697803378860428, 296243443284884623652022822]
[7, 0]
[0, 1, 24, 380, 5647, 68892, 965000, 10787085, 125460792, 1401841015, 15507485037, 173892889695, 1948876827701, 21107004750063, 223612551309580, 2415999343094932, 25641007828765980, 281441739005408223, 2929553616259257873, 31040583783058389625, 325626422693525097264, 3419989862276212884294, 36231992403695785354266, 379802209504203819698306, 3985666563610435351361981, 41209487992549182629422359]
[7, 1]
[1, 6, 78, 780, 8110, 88500, 1219870, 15865600, 172539968, 1731378357, 17700998204, 189189870494, 2383125982820, 26133698711472, 261771343230968, 2684380968983890, 27311303300643582, 312355937793457211, 3463944584394735456, 35601953767056758691, 357533815140350476230, 3630857630320495382668, 37779610844512699452723, 425041907065853528823289, 4466458203133567081386951, 44618338243477807545984051]
[7, 2]
[0, 2, 32, 752, 8051, 88500, 984600, 11630400, 151004956, 1731277200, 17693302672, 184945218049, 2049485093130, 21884202483741, 261771115832026, 2654159875976645, 27310892224213832, 283308244555221459, 3022490448478019193, 33862717664619078382, 357524905452287316162, 3616096044778082900587, 37155361718610826104304, 390754201533875335193348, 4067256720922519257062602, 44615002147323622393703377]
[7, 3]
[0, 2, 28, 430, 8051, 88492, 974738, 11630383, 127478384, 1591931287, 17660643600, 184945215113, 1980278392686, 21377898645382, 228752947068295, 2651059378227450, 27310527974405944, 283106134049192629, 3019387088183460063, 31625362502476074870, 348049734186983053933, 3615136257368942300470, 36998957507338517202370, 387486491649978060196670, 3986792603742625997814037, 41735379124070902004799090]
[7, 4]
[0, 1, 28, 430, 6047, 88296, 965000, 11630347, 125480000, 1407624801, 17660299864, 184666031090, 1949167908510, 21377239972530, 228441196782410, 2487517888462580, 27310527973598975, 283106054946074662, 3011076142524411632, 31120620488588141543, 327962317935941536555, 3612131317529933102576, 36960930792918110573472, 380594594233042078452575, 3985834697584601982285263, 41395096385504451603020184]
[7, 5]
[0, 1, 28, 430, 5649, 87266, 965000, 10924285, 125480000, 1404549428, 15793795402, 184661800871, 1948922950960, 21300782832428, 228439874081111, 2417740139508408, 27310527942304340, 282144405942988784, 2972279068997955805, 31120608681853113819, 325686674703165126747, 3462287588768112743296, 36960543171334196001997, 379831996450583231248461, 3985670485000432091737956, 41340947588645677371268945]
[7, 6]
[0, 1, 28, 402, 5649, 70452, 965000, 10806308, 125476702, 1401843466, 15676594033, 184661795894, 1948882592551, 21280350842800, 228439219364426, 2417740139427705, 25905396891838509, 281446506360443052, 2929632209731661992, 31066695222334957036, 325685924657652990733, 3419989862347559869333, 36960543167667485287638, 379824176805007286224579, 3985669766703621617211638, 41329191803312980103824816]
[8, "total"]
[1, 13, 230, 3419, 45324, 562557, 6700414, 77603263, 880826048, 9846608321, 110182931907, 1221463455172, 13371707641285, 144973661130182, 1559789289041351, 16678314312330696, 177426514498645449, 1879412115989163466, 19835296927913307595, 209459003386451684813, 2215672027091613478350, 23325376216732907826639, 244603009733863262612944, 2556824077870906100903377, 26654592622967248807226834, 277236740983737990457814483]
[8, 0]
[0, 1, 20, 309, 4738, 59653, 721097, 8542809, 97787706, 1115927418, 13521667387, 145372195515, 1563478173115, 17331793272251, 183326684061116, 1978416700882364, 21105930005745085, 223633326877388220, 2356801045758897598, 25671791008780217793, 270629757607314419135, 2818137674520461798846, 29820969440903708241344, 309307602792579861278145, 3235625752192776180297152, 33690523215566065324748227]
[8, 1]
[1, 5, 66, 870, 9418, 95404, 1020178, 10910114, 116961408, 1269319104, 15420668802, 186335569154, 2092258707459, 22324231147523, 223533368487937, 2300102388453377, 23678250753204227, 244218428740583426, 2521303233634959362, 26987371554266808324, 307381704052157972481, 3312167967401039364099, 34662251320016253747201, 352132946710859256692738, 3580993929556662847275012, 36151550056345656205770756]
[8, 2]
[0, 2, 29, 381, 7124, 95373, 1020112, 10902625, 116961408, 1269319104, 13607942531, 155047253248, 1641958131714, 18648704704515, 217975554600962, 2300096106074114, 23675007796813825, 244187609128878083, 2521303226531643392, 26210740265861906435, 279711585926283001859, 2902447824095134089218, 30494440078365576134661, 338547063815532455133187, 3560961916499477187788801, 36125179996591085238353924]
[8, 3]
[0, 1, 29, 381, 5075, 63918, 971537, 10902241, 116953473, 1262686145, 13539799424, 151967442178, 1641152821249, 17340401500161, 188344290390017, 2170897047359490, 23541908635230209, 243975985889525762, 2521303173503582210, 26194734692110041089, 271945273057034108929, 2901583130260266549252, 29939173041882216792066, 314049571512541934256131, 3333146630949991994097667, 36125178266081207951294465]
[8, 4]
[0, 1, 26, 381, 4755, 62053, 754449, 10416353, 116928577, 1252198850, 13523801473, 146455220993, 1635778152450, 17333126389762, 188343491354627, 1993331687067651, 22106987706359810, 242568603890958340, 2519252240709910530, 26192725864872542208, 271945272702129668099, 2895818520444168568834, 29931803566205061038083, 314030922173988236951554, 3236253103937606641516546, 34035718740737068781010949]
[8, 5]
[0, 1, 20, 374, 4738, 62052, 753872, 8804960, 116126274, 1250426306, 13523022208, 145523411715, 1632197982209, 17331810058241, 188287656763393, 1978494012395521, 21106490375577602, 233561403058503682, 2519039379033489411, 26104662699562631169, 271929331982013300738, 2858925012230660161539, 29929803302553834225665, 310138859550804502642690, 3236251086324973562757121, 33704710365076977753260034]
[8, 6]
[0, 1, 20, 373, 4738, 62052, 738065, 8581345, 99885377, 1250328001, 13523019137, 145381182209, 1601405499393, 17331800784897, 186638389207042, 1978494010724353, 21105998742265857, 223633395596869632, 2510204908743884802, 26048610146534424577, 271496986414564507650, 2818155688920055808001, 29929803278063834234882, 309308555691062882992130, 3235699557423071344197638, 33701940171669964601688064]
[8, 7]
[0, 1, 20, 350, 4738, 62052, 721104, 8542816, 99221825, 1176403393, 13523010945, 145381180160, 1563478173696, 17331793272832, 183339854176257, 1978482359373826, 21105940483448834, 223633362806456321, 2366089719996940290, 26048367154463113218, 270632115350116499459, 2818140398861121486850, 29894765705872778199042, 309308555623536970956802, 3235660646082689049296897, 33701940171669964601688064]
[9, "total"]
[1, 12, 212, 3184, 42624, 533576, 6402136, 74619168, 851572448, 9564151960, 106077367560, 1164696307952, 12682266771472, 137140400943144, 1474263608488184, 15768372476393536, 167915352287541696, 1781238170587875128, 18831143535290876008, 198480291817617883920, 2086322626358560955120, 21892132735043437363032, 230029194615390936267104, 2410262751538518426403744, 25192364763846665837633496, 262731282874619992538701256]
[9, 0]
[0, 1, 20, 300, 4000, 50810, 608100, 7581483, 86847740, 973625118, 10737984610, 121300162062, 1313025375090, 14165121658938, 154499378091127, 1645112030235000, 17682729924089025, 186827442950568115, 1987010557675808584, 21038961724893534430, 221795974919858695487, 2346479788820259967781, 25406697032946060893097, 264068487953027095437340, 2740806474946690930412741, 28417913827559426332313786]
[9, 1]
[1, 4, 50, 663, 8260, 99109, 1143090, 12527839, 135246289, 1409108421, 14660616984, 155444059591, 1630739921525, 17024720710829, 180215825517231, 1876739468499213, 19764853172536251, 205589163931606489, 2155867004951010588, 22558669798425164931, 235436287048196113944, 2460489043375692066252, 26752599254052604541911, 294272850260761602792780, 3112641278712249425091604, 32764467158341991897094435]
[9, 2]
[0, 1, 22, 390, 4819, 57508, 674529, 8178624, 105633660, 1242423463, 14199075590, 153071555631, 1630715025092, 17024720656758, 180215824612925, 1876739161047531, 19764535935738235, 205586904471988091, 2155866990727562950, 22558667365361933382, 234107582597019724440, 2441125857514994917013, 25420374302574773229657, 267236552503520584934116, 2830531561546103452320004, 29225200535877994572766137]
[9, 3]
[0, 1, 20, 331, 4819, 57380, 674342, 7739021, 87386480, 1016904960, 11169049600, 127547317174, 1500996867498, 16846699323194, 178278702091218, 1876653379729479, 19675870461406530, 205586448024278969, 2155866471471885592, 22502308898588165141, 234066991172760885451, 2440686588940689581005, 25414615527610074979580, 264190116304149410041220, 2793567789065871849266524, 29218305796612380576979975]
[9, 4]
[0, 1, 20, 300, 4607, 57380, 673800, 7737919, 87383719, 1016904960, 11169049600, 121690305913, 1344091521661, 14451473763834, 163007533442700, 1846997584246844, 19558644769844894, 205586447702642454, 2155864445646470642, 22408549852548766899, 234066991172760885431, 2440672691108770710675, 25407861254740594065985, 264181110626031307898742, 2749163537805585922689463, 29165128158590512477703952]
[9, 5]
[0, 1, 20, 300, 4081, 57373, 673800, 7737919, 87379345, 983783657, 11169049600, 121689951619, 1316900342867, 14451375693401, 154513713187433, 1670562112625439, 18420485086740073, 205523340066526863, 2155220314806458544, 22401358570244415690, 234066972050708120133, 2440669705836476759690, 25406860612697208395304, 264080647702880377275629, 2741792344418841077925563, 28497781743220895660131277]
[9, 6]
[0, 1, 20, 300, 4038, 52396, 673768, 7737919, 87379190, 973804376, 11168917106, 121347998860, 1316899586541, 14447972876554, 154511001243799, 1669046749703805, 17682744333799008, 188891894838895930, 2088318925434345684, 22389813725383601031, 234066968013538887691, 2440669699175785313154, 25406792564877423197861, 264080647692712890874152, 2741791293174306720467394, 28497692578937105237671325]
[9, 7]
[0, 1, 20, 300, 4000, 50810, 669878, 7699583, 87379190, 973798544, 11065639768, 121302478642, 1315872756108, 14447938617528, 154510815236742, 1661409960071225, 17682744333798612, 188886354659473105, 1988886500372792144, 21582999983663260326, 234066968013538395616, 2440669680135384091311, 25406697032946103940671, 264080647494669049994993, 2741264009230325529043007, 28497684481894681312085833]
[9, 8]
[0, 1, 20, 300, 4000, 50810, 610829, 7678861, 86936835, 973798461, 10737984702, 121302478460, 1313025375090, 14280377642108, 154510815065009, 1645112030235000, 17682744269589068, 188760173941895112, 1988242324204541280, 21038961898509042090, 224647891370179246927, 2440669680135383956151, 25406697032946093023038, 264071691000766107154772, 2740806474946690930417196, 28447108593585004471954536]
[10, "total"]
[1, 11, 192, 2893, 38894, 488895, 5888896, 68888897, 788888898, 8888888899, 98888888900, 1088888888901, 11888888888902, 128888888888903, 1388888888888904, 14888888888888905, 158888888888888906, 1688888888888888907, 17888888888888888908, 188888888888888888909, 1988888888888888888910, 20888888888888888888911, 218888888888888888888912, 2288888888888888888888913, 23888888888888888888888914, 248888888888888888888888915]
[10, 0]
[0, 1, 11, 192, 2893, 38894, 488895, 5888896, 68888897, 788888898, 8888888899, 98888888900, 1088888888901, 11888888888902, 128888888888903, 1388888888888904, 14888888888888905, 158888888888888906, 1688888888888888907, 17888888888888888908, 188888888888888888909, 1988888888888888888910, 20888888888888888888911, 218888888888888888888912, 2288888888888888888888913, 23888888888888888888888914]
[10, 1]
[1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 110000000001, 1200000000001, 13000000000001, 140000000000001, 1500000000000001, 16000000000000001, 170000000000000001, 1800000000000000001, 19000000000000000001, 200000000000000000001, 2100000000000000000001, 22000000000000000000001, 230000000000000000000001, 2400000000000000000000001, 25000000000000000000000001]
[10, 2]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 3]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 4]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 5]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 6]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 7]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 8]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]
[10, 9]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000, 16000000000000000, 170000000000000000, 1800000000000000000, 19000000000000000000, 200000000000000000000, 2100000000000000000000, 22000000000000000000000, 230000000000000000000000, 2400000000000000000000000, 25000000000000000000000000]