Project Euler 56: For natural numbers of the form, ab, find the maximum digital sum
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?
We selected Python because of the native large integer support and perl-like string parsing.
Selecting our starting range was based on several assumptions. First, the more digits the bigger the sum. With an average value of 5 per digit, 9090 has at least 175 digits. When multiplied by our average of 5, that gives us a total sum of digits of 875. This should be a safe starting point and only suspicious if our results don’t exceed it.
Having the “Oracle” that is Project Euler’s validation system for the correct answer does take away some of the drama and intrigue; I take advantage of it whenever possible. Specifically, this is an excuse for guessing at brute-force testing ranges because if the answer submitted is wrong, then, probably, so are my ranges. Think of it as the empirical approach.
Project Euler 56 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 56 Solution Python 2.7 source.
AnswerSlowly 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.
- We also wanted to know the values of a and b for our maximum to assure our starting assumptions were valid.