# 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 Problem 30 is an easy problem once you figure out the secret. The problem reads

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.

I definitely want to pursue a brute force strategy in C#, but we need an upper bound if we don’t want to continue in eternity. So finding the upper bound is the secret to solving this problem. The rest is straight forward.

So lets determine the upper bound. We need to find a number x95 which gives us an x digit number. We can do this by hand. Since 95 = 59049, we need at least 5 digits. 595 = 295245, so with 5 digits we can make a 6 digit number. 6*95 = 354294. So 355000 seems like a reasonable upper bound to use. We could probably tighten is even further if we wanted.

## The C# implementation

The algorithm is a loop count up from 2 to 355000, and in order to calculate the fifth power of the digits, I chop for digits with the modulo operator as I have done when solving problem 20 as well. The C# code looks like

```int result = 0;

for (int i = 2; i < 355000; i++) { int sumOfPowers = 0; int number = i; while (number > 0) {
int d = number % 10;
number /= 10;

int temp = d;
for(int j = 1; j < 5; j++){
temp *= d;
}
sumOfPowers += temp;
}

if (sumOfPowers == i) {
result += i;
}
}
```

In line 10-13 I made a small loop to make the fifth power of the digit as this is faster than using the math.pow function since we can keep working on integers rather than floating point operations.

The result of running the algorithm is

```The sum of all numbers who are the fifth power of their digits is 443839
Solution took 21 ms
```

which is well within the limits of the rules.

## Wrapping up

It was a fun little problem, but once you solve it there isn’t much more to say about it. As usual you can find the source code for download if you like. Comments, other solutions and questions are as always welcome both in the comments and on email. ### Posted by Kristian SuprDewd

What about caching the fifth powers of all numbers from 0 to 9?

int[] fifthPowers = new int;
for (int i = 0; i < 10; i++) fifthPowers[i] = (int)Math.Pow(i, 5);

And then replace your power-loop with:

sumOfPowers += fifthPowers[d]; SuprDewd

Now that I’ve read problem 34, I can see that that’s what you did there. 🙂 Kristian

Hi SuprDewd

Thanks for making this comment. You are right that is a good idea. And yes I realised that was a possible solution when I solved problem 34.

I have added this solution to the available source code, so to include your solution. Performance wise I have found it to change the time from 21 to 20ms, so a 5% improved performance. But if that is consistent, or just me having a lucky streak I don’t know.

Once again, thanks for the comment. It is really appreciated.

/Kristian Nusrat

Hi ,
Why did you continue the loop upto 355000 …is there any reason to do that ?

-Nusrat Kristian

Not really, it just seemed easier to write than 354294. I guess it is called lazyness.

/Kristian D

Good solution, that’s how I went about as well.

Please consider removing the answer (in terms of the actual answer, not the code) from the post however, on project euler they ask that we do not publich them ! Kristian

Thanks. I am considering remove the solution, but I doubt it will make much of a difference to be honest. In the later posts I have hidden the solution and I am considering not posting it for new posts. But if people want to cheat there are resources out there that lists solutions and nothing else. Jean-Marie Hachey

Project Euler – Problem 30 illustrates a special class of narcissistic numbers (1).

General definition of a narcissistic number :
« A narcissistic number is one which can be represented as some function
of its digits » (2)

A special class of narcissistic numbers in problem 30 :
The power applicable to the digits is constant and applied to numbers of different digit lengths.
Quote of problem 30 :
« Find the sum of all the numbers that can be written as the sum of fifth powers of their digits ».

Here the sum is not limited to 5-digit numbers.
Adaptation of the variables i and j in the code posted by Kristian (3) leads to the following results :

Sum of all the numbers that can be written as the sum of the fifth power of their digits
1) 4150
2) 4151
3) 54748
4) 92727
5) 93084
6) 194979
Sum : 443839
(Re : 443839, as reported in the article)

___

Sources :

1) Narcissistic number
http://en.wikipedia.org/wiki/Narcissistic_number
2) SOME NEW NARClSSISTIC NUMBERS
3) Code of Project Euler – Problem 30
http://www.mathblog.dk/files/euler/Problem30.cs
4) Microsoft Visual C# 2010 Express
5) Microsoft Office Excel (2007) zakariae

many thanks for this wonderful website. i have a question.
i didn’t understand why you have set the upper bound to 355000, can you explain , it’s not clear for me. Kristian

That is because it is larger than 6*9^5.

We know that we need to find numbers where the number is equal to the sum of the fifth power of their digits. Therefore we have 9^5.

The largest possible number is a six digit number, since 9999999 would only yield a six digit number as well, therefore we cannot have any 7 digit numbers with this property. zakariae

than you for the reaction, i get it aa1992

instead of starting the loop from 2..it can be more optimised by starting it from 10;As single digit numbers are avoided Darcy Gross

f=0
for x in range(10,1000000):
z=0
a=str(x)
c=len(a)
for y in range(0,c):
z+=(int(a[y]))**5
if z==x:
f+=x
print x
a=”
z=0
print f

this is a python way to do it. I am not very good at programming but I managed this one :3 I see this as quite an easy solution because it is very simple and easy to understand Stephen Hallquist

A simple pythonic version:

``` a = [] for i in range(10, 355000): s = [pow(int(k), 5) for k in str(i)] if sum(s) == i: a.append(i) print sum(a) ```