151013(2)

Ruby

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

f(10, k, n) = n を満たすnについては、オンライン整数列大辞典の
A014778（http://oeis.org/A014778/list）、
A101639（http://oeis.org/A101639/list）、
A101640（http://oeis.org/A101640/list）、
A101641（http://oeis.org/A101641/list）、
A130427（http://oeis.org/A130427/list）、
A130428（http://oeis.org/A130428/list）、
A130429（http://oeis.org/A130429/list）、
A130430（http://oeis.org/A130430/list）、
A130431（http://oeis.org/A130431/list）
を参照しました。

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

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

def f(m, k, n)
  str = n.to_s(m)
  return g(m, k, str, str.size) if k > 0
  sum = 0
  (1..m - 1).each{|k0| sum += g(m, k0, str, str.size)}
  g_total(m, n) - sum
end

p f(10, 1, 1) == 1
p f(10, 1, 199981) == 199981
p f(10, 2, 28263827) == 28263827
p f(10, 3, 371599983) == 371599983
p f(10, 4, 499999984) == 499999984
p f(10, 5, 10000000000) == 10000000000
p f(10, 6, 9500000000) == 9500000000
p f(10, 7, 9465000000) == 9465000000
p f(10, 8, 9465000000) == 9465000000
p f(10, 9, 10000000000) == 10000000000

出力結果
true
true
true
true
true
true
true
true
true
true