Project Euler Solution #56: Powerful digit sum

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

Solution

The most naive way of solving this problem is using a language like Python:

print(max(sum(map(int, str(a**b))) for a in range(100) for b in range(100)))

In order to improve performance and to explore the inner of the problem a little better, let's see what information we can gather. According to Problem 25, the number length function \(L(n) = \lfloor 1 + log_{10}(n)\rfloor\) and therefore \(L(a^b) = \lfloor 1 + \log_{10}(a^b)\rfloor = \lfloor 1 + b\cdot\log_{10}(a)\rfloor\).

The upper limit is then \(9\cdot L(a^b)\) and if we say all digits are uniformly distributed, the expected sum of the digits would be \(5\cdot L(a^b)\), which gives \(9\cdot L(99^{99}) = 9\cdot 198 = 1782\), \(5\cdot L(99^{99}) = 5\cdot 198 = 999\) and similarly \(9\cdot L(90^{90}) = 9\cdot 176 = 1584\), \(5\cdot L(90^{90}) = 5\cdot 176 = 880\).

Since the expected value raises dramatically from 880 to 990 in this small interval, it's probably safe to start with a=90 and b=90:

print(max(sum(map(int, str(a**b))) for a in range(90, 100) for b in range(90, 100)))

Which solves the problem as well and improves the performance noticeable. However, while the assumption for \(a\) is totally fine, the assumption for \(b\) was just luck. We make the approach a little more robust and implement the number length function and break early, if the upper bound is less then the current maximum, which is:

import math
def L(a, b):
  return 1 + math.floor(b * math.log(a, 10))

maxi = 0
for b in range(99, 1, -1):
  if 9 * L(99, b) < maxi:
    break
  for a in range(99, 90, -1):
    maxi = max(maxi, sum(map(int, str(a**b))))

print(maxi)

Going backwards helps quite a lot here. The last idea that could be used is using a diagonalizing function like the inverse Cantor pairing function and move step by step down from 99. Since this requires to calculate the triangular root, we skip the calculations and keep the result like this.