Duncan's blog

February 6, 2009

Project Euler problem 56

Filed under: Project Euler,Python — duncan @ 12:00 am
Tags: , , ,

Problem 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?

So, let’s do nested loops, both going 1 to 100. Inside the inner loop, calculate a^b (or i^j in this case). Then loop through the digits of that value, adding them up. Keep track of which is the largest value this produces.

Running time about 3 seconds in Python:

import time
tStart = time.time()

maxsum = 0

for i in range(100):
    for j in range(100):
        num = i ** j
        total = 0

        for k in str(num):
            total += int(k)

        if total > maxsum:
            maxsum = total

print(maxsum)
print("time:" + str(time.time() - tStart))        
Advertisements

1 Comment »

  1. […] previously blogged about this Project Euler puzzle over 5 years ago, using Python.  This is my approach using PHP as a simple practical exercise for myself, and I’d […]

    Pingback by Project Euler problem 56 (PHP) – Powerful digit sum | Duncan's blog — October 20, 2014 @ 8:10 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: