Project Euler # 56 Powerful digit sum in Python

Question

A googol (\$10^{100}\$) is a massive number: one followed by one-hundred zeros; \$100^{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?

def get_powers(n):
    """Assumes n a range, generates all numbers to the power of all numbers within the range."""
    for num in range(n):
        for power in range(n):
            yield num ** power


def get_digit_sum(n):
    """Assumes n a number, returns sum of digits."""
    return sum(int(digit) for digit in str(n))


def get_maximum(n):
    """Assumes n a range, gets all a ** b within range, returns max sum digits."""
    return max((get_digit_sum(num) for num in get_powers(n)))


if __name__ == '__main__':
    print(get_maximum(100))

Answer 1

Very nice code! Here are a few small comments, most of which are not something you have to change but rather food for thoughts as you learn more.

• Although this is a matter of personal style, I would turn around your docstrings so what is returned comes first, if possible.

  I.e. I would write

  """Generates all numbers of the form `a ** b` for `a, b < n`."""
  """Return the sum of digits of the number `n`."""
  """Return the max sum of the digits of all numbers of the form `a ** b` for `a, b < n`."""
  

• If a generator expression is the only argument to a function, one pair of () can be omitted:

  return max(get_digit_sum(num) for num in get_powers(n))
  

• Although sometimes discouraged, if you need those last 10% of speed, this is slightly faster since int is a built-in function implemented in C:

  def get_digit_sum(n):
      return sum(map(int, str(n)))
  

• Nested for loops can be replaced with itertools.product, although here it is arguably harder to read instead of easier. For high levels of nestedness it can help increase readability, though.

  from itertools import product
  
  def get_powers(n):
      for num, power in product(range(n), range(n)):
          yield num ** power
  

Answer 2

Your range is too large.

The problem asks for natural numbers of the form \$a^b\$. Natural number start at one (1, 2, 3, ...); whole numbers start at zero (0, 1, 2, 3, ...). If the problem asked for the minimum of the sum of the digits, you’d return zero, while the correct answer would be 1.

Perhaps more importantly, you’re flirting with non-deterministic behaviour. Any positive number to the power of zero is one (\$a^0 = 1\$), and zero raised to a positive number is zero (\$0^b = 0\$); \$0^0\$ is mathematically undefined. Python should return NaN for that expression. And the sum of digits of NaN is ValueError.

You should use for num in range(1, n) to avoid both the technical NaN and the non-natural number results.

---

Since \$1^b = 1\$, for efficiency, you could shrink the search space further: for num in range(2, n), avoiding the first 100 repeated digit sums of the same natural number.

You could also eliminate another 100 digit sums of 1 by eliminating the 0th powers (for power in range(1, n)). But technically, you’ve now eliminated the digit sum of the value 1, so you should make sure it doesn’t affect the answer, or include that afterwards, such as by max(..., default=get_digit_sum(1)).

---

You are still brute-forcing the answer. Look for ways to reduce the problem space.

get_digit_sum(99**99) = 936. The smallest number with a digit sum of 936 would contain 936/9 = 104 nine digits. If \$a^b < 10^{104}\$, it doesn’t contain enough digits, so you don’t need to compute the digit sum for that value, and can avoid converting the number to a string, separating it into digits, converting those to int’s, and summing them together.

Better: compute powers in the reverse order. If \$a^b < 10^{104}\$, you can break out of the inner loop.

Even better: compute the bases in the reverse order also. If \$a^{99} < 10^{104}\$, you can break out of the outer loop too.

But don’t hard code \$10^{104}\$ in your program. It should calculate that limit itself.

Even better: make the threshold dynamic. If the digit sum goes up by over 9, your minimum digit count goes up by 1, and your minimum threshold goes up as well.