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*