Problem #56 concerns the sum of the digits of various perfect powers. The question reads:
Project Euler Problem 56: Powerful digit 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?
Unfortunately, there is no easy way to determine the sum of the digits of a power. It is possible to find the remainder when it is divided by 9, but determining the exact value requires expanding the power. Thus, my solution for this problem falls into the category of brute force. Here is my solution:
Solution #1: Brute Force Approach
We simply calculate every power in this range and store the maximum digital sum. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #56
'''
import time
def sumDigits(x):
a = str(x)
total = 0
for c in a:
total+=int(c)
return total
def projectEulerProblemFiftySix(n):
maximum = -1
for a in range(1,n):
p = 1
for b in range(1,n):
p*=a
v = sumDigits(p)
if(v>maximum):
maximum = v
return maximum
start = time.time()
print projectEulerProblemFiftySix(100)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
972
--- 0.279350042343 seconds ---
for input of n = 100.
'''
And with that, we’re done. I would like to find a more efficient method for solving this problem some day. However, brute force is plenty efficient for the inputs in this problem.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 