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 = 1^{4}+ 6^{4}+ 3^{4}+ 4^{4}

8208 = 8^{4}+ 2^{4}+ 0^{4}+ 8^{4}

9474 = 9^{4}+ 4^{4}+ 7^{4}+ 4^{4}

As 1 = 1^{4}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 x*9^{5} which gives us an x digit number. We can do this by hand. Since 9^{5} = 59049, we need at least 5 digits. 5*9^{5} = 295245, so with 5 digits we can make a 6 digit number. 6*9^{5} = 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.

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

int[] fifthPowers = new int[10];

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

And then replace your power-loop with:

sumOfPowers += fifthPowers[d];

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

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

Hi ,

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

-Nusrat

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

/Kristian

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 !

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.

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

http://www.fq.math.ca/Scanned/10-3/madachy.pdf

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)

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.

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.

than you for the reaction, i get it

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

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

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)