Duncan's blog

January 31, 2009

Project Euler problem 30

Filed under: Project Euler,Python — duncan @ 4:01 pm
Tags: , ,

Problem 30:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

Another problem where I’d worked out the logic in Coldfusion, but had to rewrite it in Python to get the solution.

We’re going to loop through numbers testing them out. We know we can skip 1. But how far do we need to loop up to? Let’s look at 4 digit numbers first; the lowest 4-digit number is 1000.  1^5 + 0^5 + 0^5 + 0^5 =1.  The highest 4-digit number is 9999.  9^5 + 9^5 + 9^5 + 9^5 = 236196.  Somewhere in between there is scope for the 5th powers of a 4 digit number to add up to a 4 digit number.

What about 5 digit numbers?  The highest sum of the 5th powers is 295,245. So all 5 digit numbers fall within that range.

And with 6 digit numbers?  The highest sum of the 5th powers is 354294.  So we can cover 6 digit numbers up to that far and no further.

With 7 digit numbers, the highest value is 413343, i.e. the highest sum of the 5th powers of a 7 digit number only adds up to a 6 digit number.  So we only need to loop from 2 to 354294.

powers = []
grandtotal = 0

for i in range(2,354294):
        total = 0
        for j in str(i):
                total += int(j) ** 5

        if total == i:
                powers.append(i)

for i in powers:
        grandtotal += i

print("powers:", powers)
print("total:", grandtotal)

So we loop through our numbers. On each number, loop through the digits, adding up the values of each digit to the power of 5. If the total of those values = our number, then store that number in a list.
At the end of the loop, add up all the values in the list to give the solution to the problem.

Advertisements

2 Comments »

  1. Actually there is a “dynamic programming” way to solve this problem, although the real time benefit or the simplicity of dp is not very obvious here for question per se. However, let’s assume what was asked for was how many instead of the sum, dp will slightly show more edge over brute force. Believe it or not, the dp way for this question can be modified to solve problem 290.

    Comment by dgg32 — September 23, 2010 @ 8:48 pm | Reply

  2. […] previously blogged about this Project Euler puzzle nearly 6 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 30 (PHP) | Duncan's blog — October 9, 2014 @ 8:11 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: