Problem #63 Difficulty: 5%

Powerful Digit Counts

Solution Language: Python

The problem

Count the positive integers that have exactly n digits and are also an nth power.

My solution

Check every base from 1 to 9 against every exponent from 1 to 21, counting the cases where m**n has exactly n digits:

for n in range(1, 22):
  for m in range(1, 10):
    value = m**n

    if len(str(value)) == n:
      counter += 1

Both bounds are tight. The base can’t be 10 or more, because 10ⁿ already has n + 1 digits. For the exponent, 9ⁿ has ⌊n·log₁₀9⌋ + 1 ≈ ⌊0.954n⌋ + 1 digits, which equals n only up to n = 21 and falls behind from n = 22 on. Smaller bases fall behind sooner. So 189 checks cover every case, and the script runs instantly. It’s Python 2 (print counter).