Project Euler 56

The problem description that Problem 56 gives is as follows:

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?

 This problem really shows off how sucinctly python can solve some of the problems, especially without having to worry about producing these insanely large numbers. If this was to be done in c you would have to deal with all sorts of problems with having numbers that are too big, and with java you would have to pull out BigInt. I ended up solving this problem in two lines of python.

from itertools import product

print max(map(lambda x: sum(map(int,str(x[0]**x[1]))), product(range(1,100),range(1,100))))

This solves the problem, and at a skimpy 1 second to boot. However while it is cute to solve problems in one or two lines, it is by no means pretty or easy to understand. So lets expand this a bit and see if we can make it more readable

from itertools import product

# for example this takes in (90,90) returns 360 
sum_of_digits = lambda x: sum(map(int,str(x[0]**x[1])))
#generates a list from (90,90),(90,91) to (99,98),(99,99)
numbers_to_check = product(xrange(90,100),xrange(90,100))

print max(map(sum_of_digits,numbers_to_check))

So the first variable you see turns out to actually be a function. Lambda is a keyword that simply creates a new function on the fly, it is heavily used in functional style programming. If you find this line confusing I will write out an equivilant, but more verbose way of accomplishing the same thing:

def sum_of_digits(x):
   sum = 0
   number = x[0] ** x[1] #Takes the product. ex: (3,2) -> 9
   string = str(number) #turns it into a string ex: 9 -> "9"
   for digit in string:
      sum += int(digit)
   return sum

This may look more familiar, and if the first line was confusing I would highly recommend trying to puzzle out what each part of it does before reading my explination below, it is not too long and figuring something out on your own is one of the most gratifiying parts of learning!






So as you must have realized the for loop must have gone somewhere, that is where the map function comes into play. The map function takes a function as its first argument (here the function int()) and something it can loop over for its second (here a string). Then it applies that function to each of the elements and returns a new list that contains the results. So for example "123" turns into [1,2,3]. Very handy.

The second line, leverages the product function from itertools. hopefully my comment shows what the function does, if it does not please refer to the python documentation, it explains it very well.

And lastly the astute reader will have noticed that I changed from iterating from 1 to 100 to 90 to 100. I made the assumption that the larger the a and b variables are the larger a^b will be, a pretty safe assumption! It turns out that this is correct and my computation now runs in only 0.02 seconds.

As always, any comments or questions are more than welcome.

 EDIT:

Nolen Royalty has commeneted and provided what I believe to be a cleaner solution. It is as follows:

print max(sum(map(int, str(i**j))) for i in range(100) for j in range(100))

Or for people who don't like one liners:

answer = 0
for i in range(100):
   for j in range(100):
      answer = max(sum(map(int, str(i**j))),answer)
print answer