This project euler challenge states:

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.

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^{5} since there was no possible way it could be anything between 2^{5} and 3^{5}. The next step is finding an upper bound. I started by taking 5x9^{5} and found that the result contained 6 digits. So I put the upper bound to 6x9^{6} 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"); } } }

Recent Blog Activity

Blog Archive