Challenge: Digit Fifth Powers

Posted on: August 23, 2017 11:28:58 PM

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.

This is another relatively straight forward challenge where a modified brute force approach is fastest. I cached the 0-9 fifth powers so they wouldn't always need to be calculated and based on those results, it was clear that a good starting point was 3⁵ since there was no possible way it could be anything between 2⁵ and 3⁵. The next step is finding an upper bound. I started by taking 5x9⁵ and found that the result contained 6 digits. So I put the upper bound to 6x9⁶ to support the 6 digits. The rest is just letting it loop and finding if the on going sum is larger than the initial number.

Program.cs

using System;
using System.Diagnostics;

namespace Project_Euler_30
{
    internal class Program
    {
        // 5x9^5 has 6 digits, so the upper bound should be 6x9^6
        private const int UpperBound = 59049 * 6;

        private static readonly int[] powersCache = new int[] { 0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049 };

        private static void Main(string[] args)
        {
            Stopwatch sw = Stopwatch.StartNew();
            int result = 0;

            // start the loop at 243 since that is the lower bound (3^5) of a possible sum
            for(int i = powersCache[3]; i <= UpperBound; i++)
            {
                int sum = 0;
                int workingNumber = i;

                while(workingNumber > 0)
                {
                    int digit = workingNumber % 10;
                    workingNumber /= 10;

                    sum += powersCache[digit];

                    if(sum > i)
                    {
                        // passed the number, stop checking
                        break;
                    }
                }

                if(sum == i)
                {
                    result += i;
                }
            }
            sw.Stop();

            Console.WriteLine($"Sum of results: {result}");
            Console.WriteLine($"Took {sw.ElapsedMilliseconds}ms");
        }
    }
}