Tim Varley Logo
Tim Varley Principal AI Engineer and Tech Leader
Problem #63 medium

Powerful Digit Counts

The 55-digit number, 16807=7516807=7^5, is also a fifth power. Similarly, the 99-digit number, 134217728=89134217728=8^9, is a ninth power.

How many nn-digit positive integers exist which are also an nnth power?

View on Project Euler

Implementations

cpp
#include <iostream>
#include <cmath>
int powerful_digit_counts() {
int count = 0;
for (int a = 1; a <= 9; ++a) {
double log_a = std::log10(static_cast<double>(a));
int max_n = static_cast<int>(1.0 / (1.0 - log_a));
count += max_n;
}
return count;
}
#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
std::cout << powerful_digit_counts() << std::endl;
}
#endif
View on GitHub
O(1) time complexity

Solution Notes

Mathematical Background

This problem asks for the count of n-digit numbers that are also nth powers.

Algorithm Analysis

Use logarithmic calculation to find the maximum n for each base a from 1 to 9, where a^n has exactly n digits.

Performance Analysis

  • Time Complexity: O(1) - constant loop over 9 values
  • Space Complexity: O(1) - no additional space
  • Execution Time: Instantaneous
  • Scalability: Not applicable, fixed computation

Key Insights

  • For base a, the maximum n is floor(1 / (1 - log10(a)))
  • Only bases 1-9 can produce n-digit nth powers for n > 1
  • The answer is 49

Educational Value

This problem teaches:

  • Logarithmic properties for digit counting
  • Mathematical bounds and inequalities
  • Efficient computation without iteration