Project Euler Problem 63 Solution: Powerful Digit Counts

Project Euler Problem 63 Statement

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

How many $n$-digit positive integers exist which are also an $n$th power?

Solution

This is a simple, straight forward solution without much though required to solving it once you get your head around what they are asking for. The trick is knowing that $ n \geq 10 $ raised to any power will always have more than $ p $ digits for sufficiently large $ p $. Hence, the loop only checks $ n = 1 $ to $ 9 $.

Proof: Restricting the Loop to $ n = 1 $ to $ 9 $

The statement to be proven is:

"For any integer $ n \geq 10 $, $ n^p $ will always have more than $ p $ digits for sufficiently large $ p $. Hence, the loop only checks $ n = 1 $ to $ 9 $."

Proof

We aim to demonstrate that for any integer $ n \geq 10 $, the number $ n^p $ will have more than $ p $ digits when $ p $ is sufficiently large. This allows us to optimize algorithms by restricting our search to single-digit bases $ n = 1 $ to $ 9 $, as multi-digit bases will exceed the digit limit $ p $.

1. Number of Digits in $ n^p $

The number of digits $ D(m) $ in a positive integer $ m $ is given by:

\[ D(m) = \lfloor \log_{10} m \rfloor + 1 \]

For $ m = n^p $, the number of digits becomes:

\[ D(n^p) = \lfloor \log_{10} (n^p) \rfloor + 1 = \lfloor p \cdot \log_{10} n \rfloor + 1 \]

2. Establishing When $ D(n^p) > p $

We seek to find the conditions under which:

\[ D(n^p) > p \]

Substituting the expression for $ D(n^p) $:

\[ \lfloor p \cdot \log_{10} n \rfloor + 1 > p \]

Simplifying the inequality:

\[ p \cdot \log_{10} n > p - 1 \] \[ \log_{10} n > \frac{p - 1}{p} \]

As $ p $ increases, $ \frac{p - 1}{p} $ approaches $ 1 $:

\[ \lim_{p \to \infty} \frac{p - 1}{p} = 1 \]

Therefore, for the inequality $ \log_{10} n > \frac{p - 1}{p} $ to hold for sufficiently large $ p $, it suffices that:

\[ \log_{10} n \geq 1 \] \[ n \geq 10 \]

This shows that for $ n \geq 10 $, $ D(n^p) > p $ for all $ p \geq 1 $.

3. Verifying the Inequality for $ n \geq 10 $

Case $ n = 10 $:
\[ D(10^p) = \lfloor p \cdot \log_{10} 10 \rfloor + 1 = \lfloor p \cdot 1 \rfloor + 1 = p + 1 > p \]
Example: \[ 10^1 = 10 \quad (\text{2 digits}), \quad 10^2 = 100 \quad (\text{3 digits}), \quad \ldots \]
Case $ n > 10 $:
\[ \log_{10} n > 1 \implies p \cdot \log_{10} n > p \] \[ D(n^p) = \lfloor p \cdot \log_{10} n \rfloor + 1 \geq p + 1 > p \]
Example: \[ 11^1 = 11 \quad (\text{2 digits}), \quad 11^2 = 121 \quad (\text{3 digits}), \quad \ldots \]

Conclusion

The proof demonstrates that for any integer $ n \geq 10 $ and any exponent $ p \geq 1 $:

\[ D(n^p) = \lfloor p \cdot \log_{10} n \rfloor + 1 > p \]

Therefore, $ n^p $ will always have more than $ p $ digits. This makes it unnecessary to include $ n \geq 10 $ in any search or loop aimed at finding numbers where $ n^p $ has exactly $ p $ digits.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 63

HackerRank Project Euler 63: Given $N$, $(1\le N\le 19)$ print the $N-digit$ positive integers which are also an $N^{th}$ power?

Python Source Code

N = int(input())
for n in range(1, 10):
    if len(str(pow(n,N))) == N: print(pow(n,N))