Project Euler Problem 29

Solution

Answer: 9183

We need the number of distinct values of $a^b$ for

$$2 \le a \le 100,\qquad 2 \le b \le 100.$$

A brute-force approach works perfectly here: generate every power $a^b$, store the results in a set (which automatically removes duplicates), and count the set size.

The only duplicates arise when different bases are themselves powers, e.g.

$$4^3 = (2^2)^3 = 2^6.$$

So using a set guarantees each numerical value is counted once.

Python code:

terms = set()

for a in range(2, 101):
    for b in range(2, 101):
        terms.add(a ** b)

print(len(terms))

Reasoning check:

There are initially $99 \times 99 = 9801$ generated expressions.
Some repeat because of identities like:
$4^2 = 2^4$
$8^2 = 4^3 = 2^6$
$27^2 = 9^3 = 3^6$
After removing all duplicates, the set size is:

$$9183$$

Answer: 9183