151018(2)

Ruby

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

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

# 高速化（ただし、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

# 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以外の数字が現れた回数を除く
  sum = 0
  (1..m - 1).each{|k0| sum += g(m, k0, str, str.size)}
  g_total(m, n) - sum
end

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

(2..10).each{|m|
  ary = (0..15).map{|i| m ** i - 1}
  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"]
[0, 1, 5, 17, 49, 129, 321, 769, 1793, 4097, 9217, 20481, 45057, 98305, 212993, 458753]
[2, 0]
[0, 0, 1, 5, 17, 49, 129, 321, 769, 1793, 4097, 9217, 20481, 45057, 98305, 212993]
[2, 1]
[0, 1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264, 24576, 53248, 114688, 245760]
[3, "total"]
[0, 2, 14, 68, 284, 1094, 4010, 14216, 49208, 167306, 560966, 1860044, 6111572, 19929038, 64570082, 208059152]
[3, 0]
[0, 0, 2, 14, 68, 284, 1094, 4010, 14216, 49208, 167306, 560966, 1860044, 6111572, 19929038, 64570082]
[3, 1]
[0, 1, 6, 27, 108, 405, 1458, 5103, 17496, 59049, 196830, 649539, 2125764, 6908733, 22320522, 71744535]
[3, 2]
[0, 1, 6, 27, 108, 405, 1458, 5103, 17496, 59049, 196830, 649539, 2125764, 6908733, 22320522, 71744535]
[4, "total"]
[0, 3, 27, 171, 939, 4779, 23211, 109227, 502443, 2271915, 10136235, 44739243, 195734187, 850045611, 3668617899, 15748213419]
[4, 0]
[0, 0, 3, 27, 171, 939, 4779, 23211, 109227, 502443, 2271915, 10136235, 44739243, 195734187, 850045611, 3668617899]
[4, 1]
[0, 1, 8, 48, 256, 1280, 6144, 28672, 131072, 589824, 2621440, 11534336, 50331648, 218103808, 939524096, 4026531840]
[4, 2]
[0, 1, 8, 48, 256, 1280, 6144, 28672, 131072, 589824, 2621440, 11534336, 50331648, 218103808, 939524096, 4026531840]
[4, 3]
[0, 1, 8, 48, 256, 1280, 6144, 28672, 131072, 589824, 2621440, 11534336, 50331648, 218103808, 939524096, 4026531840]
[5, "total"]
[0, 4, 44, 344, 2344, 14844, 89844, 527344, 3027344, 17089844, 95214844, 524902344, 2868652344, 15563964844, 83923339844, 450134277344]
[5, 0]
[0, 0, 4, 44, 344, 2344, 14844, 89844, 527344, 3027344, 17089844, 95214844, 524902344, 2868652344, 15563964844, 83923339844]
[5, 1]
[0, 1, 10, 75, 500, 3125, 18750, 109375, 625000, 3515625, 19531250, 107421875, 585937500, 3173828125, 17089843750, 91552734375]
[5, 2]
[0, 1, 10, 75, 500, 3125, 18750, 109375, 625000, 3515625, 19531250, 107421875, 585937500, 3173828125, 17089843750, 91552734375]
[5, 3]
[0, 1, 10, 75, 500, 3125, 18750, 109375, 625000, 3515625, 19531250, 107421875, 585937500, 3173828125, 17089843750, 91552734375]
[5, 4]
[0, 1, 10, 75, 500, 3125, 18750, 109375, 625000, 3515625, 19531250, 107421875, 585937500, 3173828125, 17089843750, 91552734375]
[6, "total"]
[0, 5, 65, 605, 4925, 37325, 270605, 1903565, 13101005, 88683725, 592568525, 3918208205, 25686031565, 167176883405, 1081425464525, 6958737771725]
[6, 0]
[0, 0, 5, 65, 605, 4925, 37325, 270605, 1903565, 13101005, 88683725, 592568525, 3918208205, 25686031565, 167176883405, 1081425464525]
[6, 1]
[0, 1, 12, 108, 864, 6480, 46656, 326592, 2239488, 15116544, 100776960, 665127936, 4353564672, 28298170368, 182849716224, 1175462461440]
[6, 2]
[0, 1, 12, 108, 864, 6480, 46656, 326592, 2239488, 15116544, 100776960, 665127936, 4353564672, 28298170368, 182849716224, 1175462461440]
[6, 3]
[0, 1, 12, 108, 864, 6480, 46656, 326592, 2239488, 15116544, 100776960, 665127936, 4353564672, 28298170368, 182849716224, 1175462461440]
[6, 4]
[0, 1, 12, 108, 864, 6480, 46656, 326592, 2239488, 15116544, 100776960, 665127936, 4353564672, 28298170368, 182849716224, 1175462461440]
[6, 5]
[0, 1, 12, 108, 864, 6480, 46656, 326592, 2239488, 15116544, 100776960, 665127936, 4353564672, 28298170368, 182849716224, 1175462461440]
[7, "total"]
[0, 6, 90, 972, 9204, 81234, 686286, 5627544, 45157608, 356456862, 2777673282, 21421039716, 163788565212, 1243408966890, 9382085841078, 70422162397488]
[7, 0]
[0, 0, 6, 90, 972, 9204, 81234, 686286, 5627544, 45157608, 356456862, 2777673282, 21421039716, 163788565212, 1243408966890, 9382085841078]
[7, 1]
[0, 1, 14, 147, 1372, 12005, 100842, 823543, 6588344, 51883209, 403536070, 3107227739, 23727920916, 179936733613, 1356446145698, 10173346092735]
[7, 2]
[0, 1, 14, 147, 1372, 12005, 100842, 823543, 6588344, 51883209, 403536070, 3107227739, 23727920916, 179936733613, 1356446145698, 10173346092735]
[7, 3]
[0, 1, 14, 147, 1372, 12005, 100842, 823543, 6588344, 51883209, 403536070, 3107227739, 23727920916, 179936733613, 1356446145698, 10173346092735]
[7, 4]
[0, 1, 14, 147, 1372, 12005, 100842, 823543, 6588344, 51883209, 403536070, 3107227739, 23727920916, 179936733613, 1356446145698, 10173346092735]
[7, 5]
[0, 1, 14, 147, 1372, 12005, 100842, 823543, 6588344, 51883209, 403536070, 3107227739, 23727920916, 179936733613, 1356446145698, 10173346092735]
[7, 6]
[0, 1, 14, 147, 1372, 12005, 100842, 823543, 6588344, 51883209, 403536070, 3107227739, 23727920916, 179936733613, 1356446145698, 10173346092735]
[8, "total"]
[0, 7, 119, 1463, 15799, 159159, 1535415, 14380471, 131820983, 1188785591, 10584026551, 93262146999, 814816652727, 7068289035703, 60944358796727, 522739242462647]
[8, 0]
[0, 0, 7, 119, 1463, 15799, 159159, 1535415, 14380471, 131820983, 1188785591, 10584026551, 93262146999, 814816652727, 7068289035703, 60944358796727]
[8, 1]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[8, 2]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[8, 3]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[8, 4]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[8, 5]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[8, 6]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[8, 7]
[0, 1, 16, 192, 2048, 20480, 196608, 1835008, 16777216, 150994944, 1342177280, 11811160064, 103079215104, 893353197568, 7696581394432, 65970697666560]
[9, "total"]
[0, 8, 152, 2096, 25424, 287864, 3122216, 32882912, 338992928, 3438356840, 34431995960, 341269023248, 3353850745712, 32726522539736, 317415495312584, 3062630589907904]
[9, 0]
[0, 0, 8, 152, 2096, 25424, 287864, 3122216, 32882912, 338992928, 3438356840, 34431995960, 341269023248, 3353850745712, 32726522539736, 317415495312584]
[9, 1]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 2]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 3]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 4]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 5]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 6]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 7]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[9, 8]
[0, 1, 18, 243, 2916, 32805, 354294, 3720087, 38263752, 387420489, 3874204890, 38354628411, 376572715308, 3671583974253, 35586121596606, 343151886824415]
[10, "total"]
[0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889, 1088888888889, 11888888888889, 128888888888889, 1388888888888889, 14888888888888889]
[10, 0]
[0, 0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889, 1088888888889, 11888888888889, 128888888888889, 1388888888888889]
[10, 1]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 2]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 3]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 4]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 5]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 6]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 7]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 8]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]
[10, 9]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000, 10000000000, 110000000000, 1200000000000, 13000000000000, 140000000000000, 1500000000000000]