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]