Continuing with the new series on Project Euler I’m tackling problem #30:

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

1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

As 1 = 1⁴ 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.

Let’s break it down

Here’s what we need:

• A function to break an input number into its digits and find the sum of those digits each raised to a given power
• A loop to go through a reasonable set of numbers and test each one (reasonable in that we don’t expect numbers higher than the end of our limit will exhibit the features we’re testing for)
• A means to compare a number against the sum of its digits (trivial)

Digitize and Powerify

Here’s our function taking a number and power as inputs; passing in the power that we’re raising digits to lets us solve the question with 6th powers, 10th powers, etc.

    private int FindSumOfPowers(double inputNumber, double power)
    {
        int returnValue = 0;
        int tempValue = 0;
        foreach (char c in inputNumber.ToString())
        {
            tempValue = (int)Math.Pow(Convert.ToDouble(c.ToString()), power);
            returnValue += tempValue;

        }
        return returnValue;
    }

Feeding our function

Yep, that’s all there is to it; let’s put pieces together and pull out numbers matching our criteria into a collection:

    protected void Page_Load(object sender, EventArgs e)
    {
        double power = 5;
        var results = from p in Enumerable.Range(2, 10000000)
                      let sumofPowers = FindSumOfPowers(p, power)
                      where p == sumofPowers
                      select new { p, sumofPowers };

        foreach (var result in results)
        {
            Response.Write(result.p.ToString() + "<br/>");
        }
        Response.Write("===========================<br/>");
        Response.Write(results.Sum(result => { return result.p;}));
    }

I chose to run this code until the number 10,000,000, at which I felt confident I had run through all the possible numbers. We skip 1 because as the problem stated that number doesn’t count. We’re using some simple LINQ to loop through the numbers in our range and pull out the values that are equal to the return value of FindSumOfPowers(…). The anonymous variable results will be an Inumerable<> holding our matching numbers (technicalliy, the number and the calculated sum, which by the where clause are the same). Finally, we’ll use the Sum() extension method with a lambda expression telling it to use the “p” property when summing the collection.

Your turn

This certainly can’t be the most efficient or elegant solution; anyone have some pointers on speeding this up or making it better? Does your language run circles around C# on this problem?

Bookmark to:
Del.icio.us digg FURL reddit Technorati Ma.gnolia Stumble Upon Bloglines