Grind Report 12

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

*WARNING: This contains the solution!*

I believe there are a few different approaches for this problem. One is a complete brute force solution of checking each number that divides into the triangle number. This would be kind of slow and I actually did not even really consider it.

The approach I used was much more direct. Determining a triangle number was essentially given since we always had the previous triangle number. The tricky part of this problem was determining how many divisors a number has.

How many divisors a number has? With this approach to the question it is very easy to get the number of divisors. But you have to know prime numbers... those things sound familiar... In problem 7, Grind Report 8, an algorithm was created to make a list of prime numbers - just what we need!

With a list of prime numbers we can run through them and factor the number. Meanwhile, we add up each prime number exponent and multiply them all together to come up with the solution. Here is the code.

#include <iostream>
#include <math.h>
using namespace std;

const int TARGET = 200;
int primes[TARGET];

int calculateDivisorCount(int number)
{
 //setup
 int total = 1;
 int count = 0;
 int max = number / 2;
 for (int i = 0; i < TARGET; ++i)
 {
  //if the number is done being factored then break;
  //if a the prime number currently being considered (primes[i] is greather
  //than the number / 2 then that means the number is prime
  if ((number == 1 && count == 0) || primes[i] > max)
   break;
  //check to see if the current prime number is a factor
  if (number % primes[i] == 0)
  {
   //lessen the number to continue the factor tree
   number /= primes[i];
   //increase the exponent of the current prime number
   count++;
   //repeat the current prime number
   --i;
  }
  else if (count != 0)
  {
   //update the total divisors by multiplying it by the number of exponents of this prime number
   total *= (count + 1);
   count = 0;
  }
 }
 //if total is 1 that means the number is a prime and thus it has 2 divisors (1 and itself)
 if (total == 1)
  return 2;
 return total;
}

int main()
{
 primes[0] = 2;
 primes[TARGET - 1] = -1;
 int number = 3;
 int foundCount = 1;
 bool isPrime = false;
 while (primes[TARGET - 1] == -1)
 {
  double max = sqrt((float)number);
  //assume a number is prime until proven guilty
  isPrime = true;
  for (int i = 0; i < foundCount; ++i)
  {
   //break if the number is divisible by an already found prime number (guilty)
   if (number % primes[i] == 0)
   {
    isPrime = false;
    break;
   }
   //check to see if the square root of the number is less than or equal to the current prime number.
   //if so then break. This means the number is a prime.
   if (primes[i] >= max)
    break;
  }
  //add the prime number
  if (isPrime)
   primes[foundCount++] = number;
  //increment the number by 2 (to stay odd)
  number += 2;
 }

 //sum is the triangle number
 int sum = 0;
 int i = 1;
 while (true)
 {
  sum += i;
  ++i;
  if (calculateDivisorCount(sum) > 500)
   break;
 }
 int answer = sum;
 cout << "Answer: " << answer << endl;
}

I was pretty happy with this solution. It is very fast and I think the method I used to calculate the divisor count is kind of neat :)

*saved game*