Project Euler Problem 63 Solution

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. 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$$

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 Problem 63: Given $N$ where $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))