// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 56 Solution

Project Euler 56 Solution

Project Euler 56: For natural numbers of the form, ab, find the maximum digital sum


Project Euler 56 Problem Description

Project Euler 56: A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 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, ab, where a, b < 100,
what is the maximum digital sum?

Analysis

This is an easy problem to solve with Python 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.

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank


Project Euler 56 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse 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.
|972|

Afterthoughts

    No afterthoughts yet.
Project Euler 56 Solution last updated

Discussion

No comments yet.

Post a comment