Solution

Answer: 248155780267521

We seek numbers of the form

$$n = s(n)^k$$

where $s(n)$ is the sum of the decimal digits of $n$, $k \ge 2$, and $n$ has at least two digits.

The sequence $a_n$ consists of all such numbers sorted increasingly.

We are given:

$512 = 8^3$, with digit sum $5+1+2=8$
$614656 = 28^4$, with digit sum $6+1+4+6+5+6=28$

and asked to find $a_{30}$.

Mathematical analysis

Suppose a number $N$ satisfies the condition.

Let

$$s = s(N)$$

be its digit sum. Then

$$N = s^k$$

for some integer $k \ge 2$.

So every valid number is a perfect power whose base equals its own digit sum.

The brute-force idea would be:

Try many bases $s$.
Generate powers $s^k$.
Check whether the digit sum of $s^k$ equals $s$.

This works because:

digit sums grow slowly,
powers grow rapidly,
only very few numbers satisfy the condition.

Bounding the search

If $N$ has $d$ digits, then

$$s(N) \le 9d.$$

But $N = s^k$, so for fixed $s$, powers eventually become enormous.

Empirically, searching bases up to a few hundred and exponents up to around 15–20 is sufficient to capture the first 30 terms.

Python implementation

def digit_sum(n):
    """Return the sum of decimal digits of n."""
    return sum(int(c) for c in str(n))

values = set()

# Try possible digit sums (bases)
for s in range(2, 200):

    # Generate powers s^k
    power = s * s  # start with k = 2

    for k in range(2, 20):

        # Check the defining property
        if digit_sum(power) == s:
            # Must contain at least two digits
            if power >= 10:
                values.add(power)

        power *= s

# Sort the sequence
sequence = sorted(values)

# Display first several terms
for i, v in enumerate(sequence[:30], start=1):
    print(i, v)

print("a_30 =", sequence[29])

Code walkthrough

1. Digit sum function

def digit_sum(n):
    return sum(int(c) for c in str(n))

Converts the number to a string and sums its digits.

Example:

digit_sum(512)

gives

$$5+1+2 = 8.$$

2. Storage for valid numbers

values = set()

We use a set because the same number could theoretically appear more than once.

3. Enumerating possible bases

for s in range(2, 200):

Here $s$ is the candidate digit sum.

We begin at 2 because:

1 gives only trivial powers,
single-digit numbers are excluded.

4. Generating powers

power = s * s

This initializes $s^2$.

Then:

for k in range(2, 20):

we repeatedly multiply by $s$ to get:

$$s^2, s^3, s^4, \dots$$

5. Testing the property

if digit_sum(power) == s:

This checks whether the number’s digit sum equals the base.

For example:

$$8^3 = 512$$

and

$$5+1+2 = 8.$$

So 512 is included.

6. Sorting the sequence

sequence = sorted(values)

The sequence $a_n$ is defined in increasing order.

Checking the known examples

The generated sequence begins:

$$81,, 512,, 2401,, 4913,, 5832,\dots$$

Indeed:

$81 = 9^2$, digit sum $=9$
$512 = 8^3$, digit sum $=8$

and the 10th term is:

$$614656 = 28^4,$$

matching the problem statement.

Final verification

The computed sequence gives:

$$a_{30} = 248155780267521.$$

Check:

$$2+4+8+1+5+5+7+8+0+2+6+7+5+2+1 = 63$$

and

$$63^8 = 248155780267521.$$

So it satisfies the defining property exactly.

Answer: 248155780267521

Project Euler Problem 119