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

Written by on 5 March 2011

Topics: Project Euler

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 x*95 which gives us an x digit number. We can do this by hand. Since 95 = 59049, we need at least 5 digits. 5*95 = 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.

14 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    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];

  2. SuprDewd says:

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

  3. Kristian says:

    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

  4. Nusrat says:

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

    -Nusrat

  5. Kristian says:

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

    /Kristian

  6. D says:

    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 !

  7. Kristian says:

    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.

  8. Jean-Marie Hachey says:

    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)

  9. zakariae says:

    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.

  10. Kristian says:

    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.

  11. zakariae says:

    than you for the reaction, i get it

  12. aa1992 says:

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

  13. Darcy Gross says:

    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

  14. Stephen Hallquist says:

    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)

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.