Select Page

#### Project Euler 56 Problem Statement

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digit sum for all the powers? For example 187 is 612220032 and the digit sum for this power is 18.

#### Solution

Python natively supports arbitrary-precision integers and arithmetic with as many digits as necessary to perform a calculation. 100100 requires 201 digits to represent this power and Python handles it easily.

To solve this problem we calculate the powers in the range of bases and exponents for a maximal digit sum.  We can ignore the bottom 3/4 (at least) of the search range as the top 1/4 will produce powers with many more digits yielding a larger digit sum.  This is a safe and intuitive observation that can be proven empirically.

But first each power must be converted to a string so we can iterate over every character-digit (integers are not iterable, but strings are).

`max(sum(map(int, str(a**b))) for a in xrange(75, 100) for b in xrange(75, 100))`

Then, using the `map` function we iterate over the string and convert each character-digit back to an integer using the `int` function adding them together for a digit sum. Digit sums are stored implicitly with every iteration of the `for` loop.

`max(sum(map(int, str(a**b))) for a in xrange(75, 100) for b in xrange(75, 100))`

After the `for` loops finish, a maximal digit sum is found in the implicit list using the `max` function.

`max(sum(map(int, str(a**b))) for a in xrange(75, 100) for b in xrange(75, 100))`

#### HackerRank version

HackerRank increases the range to 5 ≤ a,b ≤ 200.  This solution was fast enough to handle these parameters.

#### Last Word

Embrace the power of arbitrary-precision integers and ignore the call to solve it in some primitive way.