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.

Python 2.7 Source

Last Word

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

See also, Project Euler 16: Digit sum for a large power of 2 – SOLVED