Ian Dorian Macleod
Problem 12
Problem Statement

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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?

Approach

C++ implementation

#include <stdc++.h>
using namespace std;

int numfactors(int n) {
int sum = 0;
int high = n;
int low = 1;
while(high > low) {
if (n % low == 0) {
sum += 2;
high = n / low;
}
low++;
}
return sum;
}

vector next_triangle(vector in) {
in[1] = in[1]+in[0];
in[0]++;
return in;
}

int main() {

vector curr(2);
curr.push_back(1);
curr.push_back(1);
while(numfactors(curr[1]) < 500) {
curr = next_triangle(curr);
}
cout << curr[1] << endl;
return 0;
}

You can also download the source code for this problem here and compile it on your local machine.
Further Analysis