Project Euler Problem 56

Solution

Answer: 972

We seek the maximum possible sum of digits of numbers of the form

$$a^b, \qquad a,b<100.$$

That means we must examine all integer powers $a^b$ with $1 \le a \le 99$ and $1 \le b \le 99$, compute the digit sum of each value, and find the maximum.

---

Mathematical analysis

The digit sum function is

$$s(n)=\text{sum of the decimal digits of } n.$$

For example:

$$2^{15}=32768,$$

so

$$s(2^{15}) = 3+2+7+6+8 = 26.$$

The problem asks for

$$\max_{1\le a,b<100} s(a^b).$$

There is no simple closed-form formula for the maximum digit sum, because carrying in base 10 makes the digit behavior highly irregular. However, several observations help:

---

1. Size growth

The number of digits of $a^b$ is approximately

$$\lfloor b\log_{10}(a)\rfloor + 1.$$

Large $a$ and large $b$ tend to produce more digits, and therefore potentially larger digit sums.

Since the maximum possible digit sum for a $d$-digit number is $9d$, large numbers are favored.

For example:

$$99^{99}$$

has approximately

$$99\log_{10}(99)\approx 197.56$$

digits, so the theoretical maximum digit sum nearby would be roughly

$$9\times198 = 1782.$$

The actual answer will be much smaller because digits are not all $9$'s.

---

2. Brute force is feasible

There are only

$$99\times99 = 9801$$

pairs $(a,b)$.

Modern arbitrary-precision integers can compute these values instantly.

Algorithm:

1. Loop through $a=1,\dots,99$
2. Loop through $b=1,\dots,99$
3. Compute $n=a^b$
4. Compute digit sum:

$$s(n)=\sum \text{digits of } n$$ 5. Track the maximum.

This is computationally trivial.

---

Python implementation

# Project Euler Problem 56
# Maximum digital sum of a^b for a,b < 100

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

max_sum = 0
best_pair = None

# Check all powers a^b with 1 <= a,b < 100
for a in range(1, 100):
    for b in range(1, 100):
        value = a ** b
        s = digit_sum(value)

        # Update maximum if necessary
        if s > max_sum:
            max_sum = s
            best_pair = (a, b)

print("Maximum digital sum:", max_sum)
print("Produced by:", best_pair)

---

Code walkthrough

Function definition

def digit_sum(n):

Defines a helper function to compute the digit sum.

---

return sum(int(d) for d in str(n))

Steps:

1. Convert the number to a string.
2. Iterate through each character digit.
3. Convert each digit back to an integer.
4. Sum them.

Example:

digit_sum(32768)

computes

$$3+2+7+6+8 = 26.$$

---

Initialize tracking variables

max_sum = 0
best_pair = None

• max_sum stores the largest digit sum seen so far.
• best_pair stores the corresponding $(a,b)$.

---

Main search

for a in range(1, 100):

Loops through all bases $1\le a<100$.

---

for b in range(1, 100):

Loops through all exponents $1\le b<100$.

---

value = a ** b

Computes $a^b$ using Python's arbitrary-precision integers.

---

s = digit_sum(value)

Computes the sum of digits.

---

if s > max_sum:

Checks whether we found a larger digit sum.

---

max_sum = s
best_pair = (a, b)

Updates the current best result.

---

Small example verification

Consider:

2 ** 15 = 32768

Digit sum:

$$3+2+7+6+8=26.$$

The function correctly returns 26.

Another example:

10 ** 100

is a 1 followed by 100 zeros, so the digit sum is

$$1.$$

The code also handles this correctly.

---

Final verification

The search space contains only 9801 cases, so exhaustive search guarantees correctness.

The resulting maximum digit sum is well below the theoretical upper bound (~1782), which is expected because random large integers rarely have all digits near 9.

Running the program gives:

$$972$$

which is attained by certain large powers such as $99^{95}$.

---

Answer: 972