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^{100}) is a massive number: one followed by onehundred zeros; 100^{100} is almost unimaginably large: one followed by twohundred 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.
Project Euler 56 Solution
Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 56 Solution Python 2.7 source.
Answer
Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.Afterthoughts

No afterthoughts yet.
Discussion
No comments yet.