151012(2)

Ruby

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

1から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

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

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

ary = (0..7).map{|i| 10 ** i}
(2..10).each{|m|
  p f_ary(m, ary)
  p f_ary0(m, ary)
  p ''
}

出力結果
[1, 17, 319, 4938, 64613, 815030, 9884999, 114434632]
[1, 17, 319, 4938, 64613, 815030, 9884999, 114434632]
""
[1, 9, 150, 2194, 30374, 379432, 4508710, 51180200]
[1, 9, 150, 2194, 30374, 379432, 4508710, 51180200]
""
[1, 7, 119, 1270, 19482, 242178, 2520434, 31973411]
[1, 7, 119, 1270, 19482, 242178, 2520434, 31973411]
""
[1, 7, 65, 1226, 13001, 165627, 2028125, 20171876]
[1, 7, 65, 1226, 13001, 165627, 2028125, 20171876]
""
[1, 7, 71, 731, 11198, 145691, 1471583, 15044020]
[1, 7, 71, 731, 11198, 145691, 1471583, 15044020]
""
[1, 6, 78, 780, 8110, 88500, 1219870, 15865600]
[1, 6, 78, 780, 8110, 88500, 1219870, 15865600]
""
[1, 5, 66, 870, 9418, 95404, 1020178, 10910114]
[1, 5, 66, 870, 9418, 95404, 1020178, 10910114]
""
[1, 4, 50, 663, 8260, 99109, 1143090, 12527839]
[1, 4, 50, 663, 8260, 99109, 1143090, 12527839]
""
[1, 2, 21, 301, 4001, 50001, 600001, 7000001]
[1, 2, 21, 301, 4001, 50001, 600001, 7000001]
""