Powers of digits
Published on Sunday, July 31, 2011I was a bit stumped at first by problem 30, which 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.
The trick to implementing a brute force solution to this problem is to determine the maximum conceivable value that could match the problem parameters, so as to find a ceiling past which a loop checking every number should not continue. A useful heuristic is that you've reached the number 10x
, where said number is greater than 95 × x
, you've gone too far. I used this heuristic to find a ceiling and checked every number up to it by converting it to a string and adding n
5 for every character n
in the string.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Problem030
{
class Program
{
static void Main(string[] args)
{
int sumOfPoweredDigits;
int twoToTheFifth = (int)Math.Pow(2, 5);
int threeToTheFifth = (int)Math.Pow(3, 5);
int fourToTheFifth = (int)Math.Pow(4, 5);
int fiveToTheFifth = (int)Math.Pow(5, 5);
int sixToTheFifth = (int)Math.Pow(6, 5);
int sevenToTheFifth = (int)Math.Pow(7, 5);
int eightToTheFifth = (int)Math.Pow(8, 5);
int nineToTheFifth = (int)Math.Pow(9, 5);
int ceiling = 0;
int ceilingDigits = 0;
int total = 0;
do
{
ceilingDigits++;
ceiling += nineToTheFifth;
} while (Math.Pow(10, ceilingDigits) < ceiling);
for (int i = 2; i < ceiling; i++)
{
sumOfPoweredDigits = 0;
string number = i.ToString();
foreach (char c in number)
{
switch (c)
{
case '1':
sumOfPoweredDigits++;
break;
case '2':
sumOfPoweredDigits += twoToTheFifth;
break;
case '3':
sumOfPoweredDigits += threeToTheFifth;
break;
case '4':
sumOfPoweredDigits += fourToTheFifth;
break;
case '5':
sumOfPoweredDigits += fiveToTheFifth;
break;
case '6':
sumOfPoweredDigits += sixToTheFifth;
break;
case '7':
sumOfPoweredDigits += sevenToTheFifth;
break;
case '8':
sumOfPoweredDigits += eightToTheFifth;
break;
case '9':
sumOfPoweredDigits += nineToTheFifth;
break;
}
if (sumOfPoweredDigits > i)
break;
}
if (sumOfPoweredDigits == i)
{
total += i;
}
}
Console.WriteLine(total);
}
}
}