151012(6)

Ruby

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

1からnまでをm進法で表したとき、'k'が現れる回数をf(m, k, n)と表す。

0 ≦ k ≦ m - 1 のとき、f(m, k, n)を計算してみた。

# 高速化（ただし、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 + (m - 1) * ((s - 1) * m ** s - s * m ** (s - 1) + 1) / ((m - 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

# 1からnまで全て調べる方法
def f_ary0(m, k, ary)
  n = ary.max
  i = 0
  cnt = 0
  ary0 = []
  while i < n
    i += 1
    cnt += i.to_s(m).count(k.to_s)
    ary0 << cnt if ary.include?(i)
  end
  ary0
end

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

出力結果
[2, 0]
[0, 12, 261, 4049, 59018, 753916, 9066446, 108788177]
[0, 12, 261, 4049, 59018, 753916, 9066446, 108788177]
[2, 1]
[1, 17, 319, 4938, 64613, 815030, 9884999, 114434632]
[1, 17, 319, 4938, 64613, 815030, 9884999, 114434632]
[3, 0]
[0, 5, 112, 1830, 24856, 312299, 3780509, 44933595]
[0, 5, 112, 1830, 24856, 312299, 3780509, 44933595]
[3, 1]
[1, 9, 150, 2194, 30374, 379432, 4508710, 51180200]
[1, 9, 150, 2194, 30374, 379432, 4508710, 51180200]
[3, 2]
[0, 6, 122, 1890, 24938, 319707, 3913633, 46711767]
[0, 6, 122, 1890, 24938, 319707, 3913633, 46711767]
[4, 0]
[0, 2, 65, 930, 14294, 187918, 2187936, 26908111]
[0, 2, 65, 930, 14294, 187918, 2187936, 26908111]
[4, 1]
[1, 7, 119, 1270, 19482, 242178, 2520434, 31973411]
[1, 7, 119, 1270, 19482, 242178, 2520434, 31973411]
[4, 2]
[0, 6, 70, 1260, 16409, 192212, 2519665, 28590949]
[0, 6, 70, 1260, 16409, 192212, 2519665, 28590949]
[4, 3]
[0, 2, 65, 1204, 14361, 190320, 2422450, 26935136]
[0, 2, 65, 1204, 14361, 190320, 2422450, 26935136]
[5, 0]
[0, 2, 36, 697, 9723, 133599, 1539850, 17964853]
[0, 2, 36, 697, 9723, 133599, 1539850, 17964853]
[5, 1]
[1, 7, 65, 1226, 13001, 165627, 2028125, 20171876]
[1, 7, 65, 1226, 13001, 165627, 2028125, 20171876]
[5, 2]
[0, 3, 65, 850, 13000, 134376, 1840627, 19937500]
[0, 3, 65, 850, 13000, 134376, 1840627, 19937500]
[5, 3]
[0, 2, 65, 726, 10501, 134375, 1559375, 19859376]
[0, 2, 65, 726, 10501, 134375, 1559375, 19859376]
[5, 4]
[0, 2, 41, 725, 9875, 134375, 1543751, 19859375]
[0, 2, 41, 725, 9875, 134375, 1543751, 19859375]
[6, 0]
[0, 1, 28, 472, 7792, 96602, 1135660, 13028618]
[0, 1, 28, 472, 7792, 96602, 1135660, 13028618]
[6, 1]
[1, 7, 71, 731, 11198, 145691, 1471583, 15044020]
[1, 7, 71, 731, 11198, 145691, 1471583, 15044020]
[6, 2]
[0, 2, 64, 731, 8015, 105724, 1468480, 15036280]
[0, 2, 64, 731, 8015, 105724, 1468480, 15036280]
[6, 3]
[0, 2, 35, 724, 8015, 99035, 1317036, 15036215]
[0, 2, 35, 724, 8015, 99035, 1317036, 15036215]
[6, 4]
[0, 2, 34, 615, 7863, 99034, 1135666, 15005175]
[0, 2, 34, 615, 7863, 99034, 1135666, 15005175]
[6, 5]
[0, 1, 28, 472, 7792, 97934, 1135660, 14834162]
[0, 1, 28, 472, 7792, 97934, 1135660, 14834162]
[7, 0]
[0, 1, 24, 380, 5647, 68892, 965000, 10787085]
[0, 1, 24, 380, 5647, 68892, 965000, 10787085]
[7, 1]
[1, 6, 78, 780, 8110, 88500, 1219870, 15865600]
[1, 6, 78, 780, 8110, 88500, 1219870, 15865600]
[7, 2]
[0, 2, 32, 752, 8051, 88500, 984600, 11630400]
[0, 2, 32, 752, 8051, 88500, 984600, 11630400]
[7, 3]
[0, 2, 28, 430, 8051, 88492, 974738, 11630383]
[0, 2, 28, 430, 8051, 88492, 974738, 11630383]
[7, 4]
[0, 1, 28, 430, 6047, 88296, 965000, 11630347]
[0, 1, 28, 430, 6047, 88296, 965000, 11630347]
[7, 5]
[0, 1, 28, 430, 5649, 87266, 965000, 10924285]
[0, 1, 28, 430, 5649, 87266, 965000, 10924285]
[7, 6]
[0, 1, 28, 402, 5649, 70452, 965000, 10806308]
[0, 1, 28, 402, 5649, 70452, 965000, 10806308]
[8, 0]
[0, 1, 20, 309, 4738, 59653, 721097, 8542809]
[0, 1, 20, 309, 4738, 59653, 721097, 8542809]
[8, 1]
[1, 5, 66, 870, 9418, 95404, 1020178, 10910114]
[1, 5, 66, 870, 9418, 95404, 1020178, 10910114]
[8, 2]
[0, 2, 29, 381, 7124, 95373, 1020112, 10902625]
[0, 2, 29, 381, 7124, 95373, 1020112, 10902625]
[8, 3]
[0, 1, 29, 381, 5075, 63918, 971537, 10902241]
[0, 1, 29, 381, 5075, 63918, 971537, 10902241]
[8, 4]
[0, 1, 26, 381, 4755, 62053, 754449, 10416353]
[0, 1, 26, 381, 4755, 62053, 754449, 10416353]
[8, 5]
[0, 1, 20, 374, 4738, 62052, 753872, 8804960]
[0, 1, 20, 374, 4738, 62052, 753872, 8804960]
[8, 6]
[0, 1, 20, 373, 4738, 62052, 738065, 8581345]
[0, 1, 20, 373, 4738, 62052, 738065, 8581345]
[8, 7]
[0, 1, 20, 350, 4738, 62052, 721104, 8542816]
[0, 1, 20, 350, 4738, 62052, 721104, 8542816]
[9, 0]
[0, 1, 20, 300, 4000, 50810, 608100, 7581483]
[0, 1, 20, 300, 4000, 50810, 608100, 7581483]
[9, 1]
[1, 4, 50, 663, 8260, 99109, 1143090, 12527839]
[1, 4, 50, 663, 8260, 99109, 1143090, 12527839]
[9, 2]
[0, 1, 22, 390, 4819, 57508, 674529, 8178624]
[0, 1, 22, 390, 4819, 57508, 674529, 8178624]
[9, 3]
[0, 1, 20, 331, 4819, 57380, 674342, 7739021]
[0, 1, 20, 331, 4819, 57380, 674342, 7739021]
[9, 4]
[0, 1, 20, 300, 4607, 57380, 673800, 7737919]
[0, 1, 20, 300, 4607, 57380, 673800, 7737919]
[9, 5]
[0, 1, 20, 300, 4081, 57373, 673800, 7737919]
[0, 1, 20, 300, 4081, 57373, 673800, 7737919]
[9, 6]
[0, 1, 20, 300, 4038, 52396, 673768, 7737919]
[0, 1, 20, 300, 4038, 52396, 673768, 7737919]
[9, 7]
[0, 1, 20, 300, 4000, 50810, 669878, 7699583]
[0, 1, 20, 300, 4000, 50810, 669878, 7699583]
[9, 8]
[0, 1, 20, 300, 4000, 50810, 610829, 7678861]
[0, 1, 20, 300, 4000, 50810, 610829, 7678861]
[10, 0]
[0, 1, 11, 192, 2893, 38894, 488895, 5888896]
[0, 1, 11, 192, 2893, 38894, 488895, 5888896]
[10, 1]
[1, 2, 21, 301, 4001, 50001, 600001, 7000001]
[1, 2, 21, 301, 4001, 50001, 600001, 7000001]
[10, 2]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 3]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 4]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 5]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 6]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 7]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 8]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[10, 9]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]
[0, 1, 20, 300, 4000, 50000, 600000, 7000000]