151018

Ruby

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

f(m, k, m ** i) を調べてみた。
total と f(m, 0, 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

# 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}
  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, 4107, 9228, 20493, 45070, 98319, 213008, 458769]
[2, 0]
[0, 1, 3, 8, 21, 54, 135, 328, 777, 1802, 4107, 9228, 20493, 45070, 98319, 213008]
[2, 1]
[1, 2, 5, 13, 33, 81, 193, 449, 1025, 2305, 5121, 11265, 24577, 53249, 114689, 245761]
[3, "total"]
[1, 4, 17, 72, 289, 1100, 4017, 14224, 49217, 167316, 560977, 1860056, 6111585, 19929052, 64570097, 208059168]
[3, 0]
[0, 1, 4, 17, 72, 289, 1100, 4017, 14224, 49217, 167316, 560977, 1860056, 6111585, 19929052, 64570097]
[3, 1]
[1, 2, 7, 28, 109, 406, 1459, 5104, 17497, 59050, 196831, 649540, 2125765, 6908734, 22320523, 71744536]
[3, 2]
[0, 1, 6, 27, 108, 405, 1458, 5103, 17496, 59049, 196830, 649539, 2125764, 6908733, 22320522, 71744535]
[4, "total"]
[1, 5, 30, 175, 944, 4785, 23218, 109235, 502452, 2271925, 10136246, 44739255, 195734200, 850045625, 3668617914, 15748213435]
[4, 0]
[0, 1, 5, 30, 175, 944, 4785, 23218, 109235, 502452, 2271925, 10136246, 44739255, 195734200, 850045625, 3668617914]
[4, 1]
[1, 2, 9, 49, 257, 1281, 6145, 28673, 131073, 589825, 2621441, 11534337, 50331649, 218103809, 939524097, 4026531841]
[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"]
[1, 6, 47, 348, 2349, 14850, 89851, 527352, 3027353, 17089854, 95214855, 524902356, 2868652357, 15563964858, 83923339859, 450134277360]
[5, 0]
[0, 1, 6, 47, 348, 2349, 14850, 89851, 527352, 3027353, 17089854, 95214855, 524902356, 2868652357, 15563964858, 83923339859]
[5, 1]
[1, 2, 11, 76, 501, 3126, 18751, 109376, 625001, 3515626, 19531251, 107421876, 585937501, 3173828126, 17089843751, 91552734376]
[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"]
[1, 7, 68, 609, 4930, 37331, 270612, 1903573, 13101014, 88683735, 592568536, 3918208217, 25686031578, 167176883419, 1081425464540, 6958737771741]
[6, 0]
[0, 1, 7, 68, 609, 4930, 37331, 270612, 1903573, 13101014, 88683735, 592568536, 3918208217, 25686031578, 167176883419, 1081425464540]
[6, 1]
[1, 2, 13, 109, 865, 6481, 46657, 326593, 2239489, 15116545, 100776961, 665127937, 4353564673, 28298170369, 182849716225, 1175462461441]
[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"]
[1, 8, 93, 976, 9209, 81240, 686293, 5627552, 45157617, 356456872, 2777673293, 21421039728, 163788565225, 1243408966904, 9382085841093, 70422162397504]
[7, 0]
[0, 1, 8, 93, 976, 9209, 81240, 686293, 5627552, 45157617, 356456872, 2777673293, 21421039728, 163788565225, 1243408966904, 9382085841093]
[7, 1]
[1, 2, 15, 148, 1373, 12006, 100843, 823544, 6588345, 51883210, 403536071, 3107227740, 23727920917, 179936733614, 1356446145699, 10173346092736]
[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"]
[1, 9, 122, 1467, 15804, 159165, 1535422, 14380479, 131820992, 1188785601, 10584026562, 93262147011, 814816652740, 7068289035717, 60944358796742, 522739242462663]
[8, 0]
[0, 1, 9, 122, 1467, 15804, 159165, 1535422, 14380479, 131820992, 1188785601, 10584026562, 93262147011, 814816652740, 7068289035717, 60944358796742]
[8, 1]
[1, 2, 17, 193, 2049, 20481, 196609, 1835009, 16777217, 150994945, 1342177281, 11811160065, 103079215105, 893353197569, 7696581394433, 65970697666561]
[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"]
[1, 10, 155, 2100, 25429, 287870, 3122223, 32882920, 338992937, 3438356850, 34431995971, 341269023260, 3353850745725, 32726522539750, 317415495312599, 3062630589907920]
[9, 0]
[0, 1, 10, 155, 2100, 25429, 287870, 3122223, 32882920, 338992937, 3438356850, 34431995971, 341269023260, 3353850745725, 32726522539750, 317415495312599]
[9, 1]
[1, 2, 19, 244, 2917, 32806, 354295, 3720088, 38263753, 387420490, 3874204891, 38354628412, 376572715309, 3671583974254, 35586121596607, 343151886824416]
[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"]
[1, 11, 192, 2893, 38894, 488895, 5888896, 68888897, 788888898, 8888888899, 98888888900, 1088888888901, 11888888888902, 128888888888903, 1388888888888904, 14888888888888905]
[10, 0]
[0, 1, 11, 192, 2893, 38894, 488895, 5888896, 68888897, 788888898, 8888888899, 98888888900, 1088888888901, 11888888888902, 128888888888903, 1388888888888904]
[10, 1]
[1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 110000000001, 1200000000001, 13000000000001, 140000000000001, 1500000000000001]
[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]