#### Project Euler 56 Problem Statement

Considering natural numbers of the form, *a ^{b}*, where

*a, b*< 100, what is the maximum digit sum for all the powers? For example 18

^{7}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. 100^{100} 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

## Recent Comments