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]