Project Euler Problem 63

Solution

Answer: 49

We seek all positive integers that are simultaneously:

• an $n$-digit number, and
• an $n$th power.

That is, numbers of the form

$$k^n$$

such that $k^n$ has exactly $n$ digits.

---

Mathematical analysis

A positive integer $x$ has exactly $n$ digits iff

$$10^{n-1} \le x < 10^n.$$

Substitute $x = k^n$:

$$10^{n-1} \le k^n < 10^n.$$

Take base-10 logarithms:

$$n-1 \le n\log_{10} k < n.$$

The right inequality is always true for $k<10$, because then $\log_{10} k < 1$.

The left inequality is the important one:

$$n-1 \le n\log_{10} k.$$

Rearrange:

$$1 - \frac1n \le \log_{10} k.$$

Equivalently,

$$n(1-\log_{10} k)\le 1.$$

So for a fixed base $k$, the allowed exponents satisfy

$$n \le \frac{1}{1-\log_{10} k}.$$

---

Which bases are possible?

If $k \ge 10$, then $k^n$ has more than $n$ digits, so impossible.

If $k=1$, then $1^n=1$, which has only 1 digit, so only $n=1$ works.

Thus we only need

$$k = 1,2,\dots,9.$$

For each $k\in{1,\dots,9}$, count how many positive integers $n$ satisfy

$$10^{n-1}\le k^n.$$

Using the derived inequality:

$$n \le \frac{1}{1-\log_{10} k}.$$

Therefore the number of valid $n$ values for a given $k$ is

$$\left\lfloor \frac{1}{1-\log_{10} k} \right\rfloor.$$

Now compute:

$k$	Count
1	1
2	1
3	1
4	2
5	3
6	4
7	6
8	10
9	21

Total:

$$1+1+1+2+3+4+6+10+21 = 49.$$

---

Python implementation

import math

count = 0

# Bases only need to go from 1 to 9
for k in range(1, 10):

    # Maximum n satisfying:
    # n <= 1 / (1 - log10(k))
    max_n = int(1 / (1 - math.log10(k)))

    count += max_n

print(count)

---

Code walkthrough

import math

We need logarithms, so we import the math module.

---

count = 0

This stores the total number of valid integers.

---

for k in range(1, 10):

Possible bases are only $1$ through $9$.

Any base $10$ or larger automatically produces too many digits.

---

max_n = int(1 / (1 - math.log10(k)))

From the derivation:

$$n \le \frac{1}{1-\log_{10} k}.$$

Taking the integer part gives the number of valid exponents.

Examples:

• $k=7$:

$$\frac1{1-\log_{10}7}\approx 6.45$$

So there are 6 valid powers:

$7^1,\dots,7^6$.

Indeed:

• $7^5 = 16807$ has 5 digits,
• $7^6 = 117649$ has 6 digits,
• $7^7$ has 6 digits, so it stops there.

---

count += max_n

Add the contribution from this base.

---

print(count)

Outputs the final total.

---

Verification with the examples

The problem gives:

$$7^5 = 16807$$

which is a 5-digit fifth power.

Also:

$$8^9 = 134217728$$

which is a 9-digit ninth power.

Both are included by the inequality above.

The final total $49$ is reasonable because only bases $1$–$9$ can work, and the counts grow rapidly near base $9$.

---

Answer: 49