Project Euler 56: For natural numbers of the form, a^b, find the maximum digital sum

Project Euler 56 Problem Description

Project Euler 56: 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?

Analysis

This is an easy problem to solve with Python, much like Project Euler 16, because of the language’s native large integer support and adept string handling.

The HackerRank limits are not that more aggressive as it only extends the limit from 100 to 200. And the same solution presented below easily solves both challenges:

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

In order to improve performance, with the only intention to see how much processing time could be saved, new starting limits for the base and exponent were discovered.

Selecting a new starting range was based on one assumption: the more digits, greater than the average digit value 4, the bigger the sum. This assumption focuses attention on looking at the larger exponents. So, smaller powers in the search range can be skipped and we can reduce the base (a) to start at 60% of the limit and the exponent (b) at 80% of the limit. We proved empirically that both of these reductions satisfy any query with an a and b less than 1000. In fact, the reduction factors for the base and exponent can increase to 85% and 90%, respectively, with larger values of a and b.

Summing the digits of a number

The python expression below will separate each digit from the calculated power and add them together. This is accomplished by converting the numerical power (a**b) to a string, which is iterable, and using the map function to convert each character (digit) into an integer. These integers are then summed into a digital sum.

sum(map(int, str(a**b)))

Finding the maximum digital sum

As each power is calculated and the sum of their digits evaluated they are buffered into a collection, like an array, where the maximum of the collection is selected.

This program and method
solves all test cases for
Project Euler 56 on HackerRank

Project Euler 56 Solution

Afterthoughts

No afterthoughts yet.