     (11 votes, average: 5.00 out of 5) Loading...

## Project Euler 30 Solution ## Project Euler 30: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits

#### Project Euler 30 Problem Description

Project Euler 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.

#### Project Euler 30 Analysis

These numbers are somewhat related to Armstrong numbers (or narcissistic numbers) which differ from having more or fewer digits than the exponent to only allowing the same number of digits as the exponent (series Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A005188: Armstrong (or Plus Perfect, or narcissistic) numbers: n-digit numbers equal to sum of n-th powers of their digits (a finite sequence, the last term being 115132219018763992565095597973971522401).).

The easiest and fastest way to solve this problem is to use brute force searching which solves this and the HackerRank version within the time limit. All we need is the maximum number of digits to search through for the chosen exponent which happens to safely be the exponent+1. This saves having to argue what the upper limit should be and serially checking every number in a range.

### Using combinations

In the problem statement above, 1634 was used as the first example that satisfies the summation of powers requirement. It becomes obvious that various combinations of 1634 (1643, 1346, 1364, 1436, 1463, 3146, 3164, 3416, 3461, 3614, 3641, 4136, 4163, 4316, 4361, 4613, 4631, 6134, 6143, 6314, 6341, 6413, 6431) will all evaluate to the same sum. Clearly, we can eliminate all but one combination and just test that candidate from the set.

This reduces our search space from tens of thousands numbers to only a couple thousand. Since all the numbers evaluate to the same power-sum by virtue of the commutative law of addition, it doesn’t matter which number from the set we choose, as long as its power-sum, subjected to the same process, is equal to the sum’s digits and unique in the search.

Example: Take arbitrarily from the set above, say 3614, and sum the 4th powers of its digits. The sum is 1634 as it is for any number in the set. Now, let’s do the same calculation on the sum, 1634: 14+64+34+44 = 1634. When the two sums are equal, 1634 is the successful candidate from the set.

HackerRank only goes as far as extending the problem to 6th powers of their digits when 11 or 12 digits would be more challenging and quickly solved using this method. This program and method
solves all test cases for
Project Euler 30 on HackerRank

• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A052455: Fixed points for operation of repeatedly replacing a number by the sum of the fourth power of its digits.
• With a little further searching, I found:
Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A052464: Fixed points for operation of repeatedly replacing a number by the sum of the fifth power of its digits.

• Power

Number Set
2

*NONE*
3

153, 370, 371, 407
4

1634, 8208, 9474
5

4150, 4151, 54748, 92727, 93084, 194979
6

548834
7

1741725, 4210818, 9800817, 9926315, 14459929
8

24678050, 24678051, 88593477
9

146511208, 472335975, 534494836, 912985153
10

4679307774
11

32164049650, 40028394225, 42678290603, 44708635679, 49388550606, 32164049651, 82693916578, 94204591914
12

*NONE*
13

564240140138
14

28116440335967
15

*NONE*
16

4338281769391370, 4338281769391371
17

233411150132317, 21897142587612075, 35641594208964132, 35875699062250035
18

*NONE*
19

1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826
20

63105425988599693916
Project Euler 30 Solution last updated

## Discussion

### 7 Responses to “Project Euler 30 Solution”

1. Hi, I don’t understand why ex needs to be incremented by one if its initial value is >= 5.

Posted by Ryan | January 10, 2020, 2:40 PM
2. I’m confused why ex has 1 added to it if it’s initial value is >= 5.

Posted by Ryan | January 10, 2020, 12:47 PM
3. hello, guys. the euler.py don’t have the pow_digits() … :s

Posted by kmonsoor | January 14, 2014, 10:43 AM
• Posted by Mike | January 14, 2014, 11:26 PM
4. 2**5+5*9**5≤3*10**5 so the limit max
This is good to speed up.
≤2s in python

Posted by Francky | April 29, 2011, 4:53 PM
• That is a great optimization. I need to convert this solution to python or you can send me yours. Thanks for all your diligence and useful comments.

Posted by Mike | May 12, 2011, 12:44 PM
• Hi, I’m struggling to see the reasoning behind this optimization. Would you care to elaborate a bit?
Regards

Posted by Chris | January 25, 2016, 1:17 AM