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⁴ + 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.

*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*

Grind Report 29

Problem 29

Consider all integer combinations of a^b for 2 <= a <= 5 and 2 <= b <= 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 <= a <= 100 and 2 <= b <= 100?

*WARNING: This contains the solution!*

While attempting this problem I came up with two solutions - but only one actually completely worked... As usual, using C++ runs into some problems here because of the limitation on integer size.

My first solution (the semifunctional one) placed the focus on the repeated terms. I used the fact that an exponent can be broken up such as

2^32 = (2^4)^8 = 16^8

With this it is possible to find which terms are repeated without ever actually calculating the value of a^b. So with this it is easy to simply keep a boolean collection of the different combinations and if one has been encountered before. Such as in the example above when 2^32 (a = 2, b = 32) is run it will see that this is equal to 4^16 and 16^8. Consequently [4][16] and [16][8] both need to be marked as repeats. At the end it is as easy as counting the repeats and subtracting them from the max number of possible terms (99x99).

Here is the code but keep in mind that this code does not return the correct answer. While attempting to debug the solution I came across another, much simplier, solution. That I'll discuss after this.

#include <iostream>
#include <vector>

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

int PowerWithinMAX(int a, int b);

int main()
{
vector<vector<bool>> encountered;
 //create the list of encountered combinations - vector<vector<bool>>
 for (int i = 0; i < MAX + 1; ++i)
  encountered.push_back(vector<bool>(MAX + 1, false));
 
 int repeatCount = 0;
 for (int a = MIN; a <= MAX; ++a)
 {
  for (int b = MIN; b <= MAX; ++b)
  {
   //if a^b has previously been encountered before
   //then increment repeat count and continue
   if (encountered[a][b])
   {
    ++repeatCount;
    continue;
   }
   //check to see if b can be broken up into pieces
   //ie. 2^32 = (2^4)^8 = 16^8
   //if so then mark that as being encountered ([16][8])
   for (int i = 2; i < b / 2; ++i)
   {
    //if i is a divisor of b
    if (b % i == 0)
    {
     //check to see if the power is within the max
     int c = PowerWithinMAX(a, i);
     if (c)
      encountered[c][b / i] = true;
    }
   }
  }
 }
 int ans = 0;
 for (int i = 0; i <= MAX; ++i)
  for (int j = 0; j <= MAX; ++j)
   if (encountered[i][j])
    ++ans;
 
 int answer = (MAX - MIN + 1) * (MAX - MIN + 1) - ans;
 cout << answer;
}

int PowerWithinMAX(int a, int b)
{
 int solution = 1;
 //calculates a^b until solution is > 100
 while (solution <= MAX && b > 0)
 {
  solution *= a;
  b--;
 }
 //if b > 0 (true) then the solution is greater than MAX
 if (solution > MAX)
  return 0;
 else
  return solution;
}

The working method using some more standard library goodness to take care of mostly everything. Every possible combination of a^b is calculated using pow(a, b) and then stored into a set. Once done the set.size() is the unique number of terms. The reason why this works is that when using double it is true that it is not precise enough to give the correct term, but it is precise enough that all terms are unique unless they are actually a repeated term.

Because this is so simple the code is pretty small.

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

using std::set;
using std::cout;

const int MIN = 2;
const int MAX = 100;

int main()
{
 set<double> answer;
 for (double a = MIN; a <= MAX; ++a)
  for (double b = MIN; b <= MAX; ++b)
   answer.insert(pow(a, b));
 cout << answer.size();
}

I will probably go back and fix up the first solution and get it working eventually. I am curious what the problem with the algorithm is. In the meantime I'll continue to move onward.

*saved game*