# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2063
#
# 説明のため，
# n ** m が m 桁になる数を数える
# とする.
#
# 指数は単調増加関数であることから，
# 1. 10 ** m は 必ず m + 1 桁になることから n は10以下である．
# 2. 9 ** m が 10 ** (m - 1) 以下であれば
#    9以下の数について　n ** m が m 桁になることはない．
#
# 2となる m を m_max とすると，1, 2より
# m は 1 .. m_max
# n は 1 .. 9
# であるので，
# この組み合わせについて n ** m が m 桁になる数を数えればいい．
def m_max
  m = 1
  loop do
    if (9 ** m < 10 ** (m - 1))
      return m - 1
    end
    m += 1
  end
end
puts (1 .. m_max).reduce(0) {|count, m|
  count + (1 .. 9).reduce(0) {|count, n|
    nm = n ** m
    count + (10 ** (m - 1) <= nm && nm < 10 ** m ? 1 : 0)
  }
}