Wednesday, July 29, 2009

Grind Report 30

Problem 30

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.

*WARNING: This contains the solution!*

This was a fairly simple problem. My approach was extreme brute force using some recursion. I first consider every possible number with one digit, then two digits and so on. Every number I consider I check to see if the number matches the criteria for being a special number.

As I look back at my solution I think that recursion was probably not the best method but I'll let it stay as it is.

One important thing to do in this problem is precalculate the digits to the 5th power and store them in an array. This is somewhat obvious but still helps cut down the cost.

#include <iostream>
#include <vector>
#include <math.h>

using std::vector;
using std::cout;

const double N = 5;
const int MAXDIGITS = 6;

vector<int> nthpow;
int solution;

void CheckDigitCombinations(int digitCount, int digitTotal, int num, int sumOfDigits);

int main()
{
//precalculate the nth power of all single digits [0-9]
for (double i = 0; i < 10; ++i)
nthpow.push_back((int)pow(i, N));

for (int digitCount = 1; digitCount <= MAXDIGITS; ++digitCount)
CheckDigitCombinations(digitCount, digitCount, 0, 0);

cout << solution;
}

void CheckDigitCombinations(int digitCount, int digitTotal, int num, int sumOfDigits)
{

for (int digit = 0; digit < 10; ++digit)
{
int number = num;
int sum = sumOfDigits;
if (digitCount == digitTotal && !digit)
continue;
//add on the extra digit (doesn't change anything for digit #1)
number *= 10;
number += digit;
sum += nthpow[digit];
if (digitCount > 1)
CheckDigitCombinations(digitCount - 1, digitTotal, number, sum);
if (sum == number && sum != 1 && digitCount == 1)
solution += number;
}
}

*saved game*

1 comment: