151012

Ruby

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

1からnまでをm進法で表したとき、'1'が現れる回数をf(m, n)と表す。
n = a * m^k + b （ただし、1 ≦ a ≦ m - 1）と表すと、
a = 1 のとき、
f(m, n)
= f(m, m^k) + b + f(m, b)
= k * m^(k - 1) + 1 + b + f(m, b)
a > 1 のとき
f(m, n)
= f(m, m^k) + (m^k - 1) + ((a - 1)f(m, m^k - 1) + f(m, b))
= f(m, m^k) + (m^k - 1) + ((a - 1)(f(m, m^k) - 1) + f(m, b))
= af(m, m^k) + m^k - a + f(m, b)
= a * k * m^(k - 1) + m^k + f(m, b)
となる。
[f(m, 1), f(m, 2), … , f(m, n)]を求めるなら先程の方法で良いが、
f(m, n)だけを求めるならこの方法の方が速い。

def g(m, str, s)
  if s == 1
    return 0 if str == '0'
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  return g(m, str1, s - 1) if a == 0
  return (s - 1) * m ** (s - 2) + 1 + str1.to_i(m) + g(m, str1, s - 1) if a == 1
  return a * (s - 1) * m ** (s - 2) + m ** (s - 1) + g(m, str1, s - 1)
end

def f(m, n)
  str = n.to_s(m)
  g(m, str, str.size)
end

ary =
[0, 1, 199981, 199982, 199983, 199984, 199985, 199986, 199987, 199988, 199989, 199990,
 200000, 200001, 1599981, 1599982, 1599983, 1599984, 1599985, 1599986, 1599987, 1599988,
 1599989, 1599990, 2600000, 2600001, 13199998, 35000000, 35000001, 35199981, 35199982,
 35199983, 35199984, 35199985, 35199986, 35199987, 35199988, 35199989, 35199990, 35200000,
 35200001, 117463825, 500000000, 500000001, 500199981, 500199982, 500199983, 500199984,
 500199985, 500199986, 500199987, 500199988, 500199989, 500199990, 500200000, 500200001,
 501599981, 501599982, 501599983, 501599984, 501599985, 501599986, 501599987, 501599988,
 501599989, 501599990, 502600000, 502600001, 513199998, 535000000, 535000001, 535199981,
 535199982, 535199983, 535199984, 535199985, 535199986, 535199987, 535199988, 535199989,
 535199990, 535200000, 535200001, 1111111110]

p ary.size
# f(10, n) = nとなるはず
p ary.map{|n| f(10, n) == n}

出力結果
84
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]