Problem 12

Highly divisible triangular number

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:
$\begin{align*} 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 \\ \end{align*}$
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?

https://projecteuler.net/problem=12

Triangle Numbers

function triangleN(n) {
  var sum = n;
  while (n--) {
    sum+=n;
  }
  return sum;
}
triangleN(7);
// 28

Actually we don’t need this. If we refer back to Problem 1, we can generalize any term in an arithmetic series

$S_n = \frac {n(a_1+a_n)}2$

and that means for triangle numbers:

$T_n = \frac {n(n+1)}2$

$1,3,6,10...$ $\begin{align*} T_1 & = \frac {1\times(1+1)}2 = \frac {1\times(2)}2 = 1 \\ T_2 & = \frac {2\times(2+1)}2 = \frac {2\times(3)}2 = 3 \\ T_3 & = \frac {3\times(3+1)}2 = \frac {3\times(4)}2 = 6 \\ T_4 & = \frac {4\times(4+1)}2 = \frac {4\times(5)}2 = 10 \\ \end{align*}$

function triangleN(n) {
  return n * (n + 1) / 2;
}

Number of Factors

The naive approach to finding how many factors a number has is to trial divide the number, $n$ , by numbers from $1$ to $n$ .

function numFactors(n) {
  var counter = 0, i = 0;
  while (i++ < n) {
    if (n % i === 0) counter++;
  }
  return counter;
}

This method is actually too slow for us to use to brute force an answer. We can use some information from Problem 5 to help us. We learned that any number $n$ can be decomposed using prime numbers.

$n = p^\alpha \times q^\beta \times ... r^\gamma$

It is also true that any number, $m$ , that is a power of a prime, $p$ , $m=p^\alpha$ , $m$ will have $\alpha+1$ factors. For example:

$\begin{align*} 5 & = 5^1, \text{ factors } \mapsto 1, 5 & \mapsto & 5^0, 5^1 \\ 8 & = 2^3, \text{ factors } \mapsto 1, 2, 4, 8 & \mapsto & 2^0, 2^1, 2^2, 2^3 \\ 9 & = 3^2, \text{ factors } \mapsto 1, 3, 9 & \mapsto & 3^0, 3^1, 3^2 \end{align*}$

Now consider a number that is composed of multiple primes:

$n = p^\alpha \times q^\beta \times ... r^\gamma$

The number of total divisors can be determined by the powers of the prime decomposition using the rule of product, so $n$ will have:

$\text{num_factors} = (\alpha+1)\times(\beta+1)\times...(\gamma+1)$

Brute Force

var Factor = (function(n) {
  function factor(n) {
    var factors = Object.create(null),
        primes = Primes.primesTo(Math.floor(Math.sqrt(n)) + 1),
        i = 0,
        prime = primes[i],
        power;
    factors[1] = 1;
    while (prime * prime < n) {
      power = 0;
      while (n % prime === 0) {
        power++;
        n = n / prime;
      }
      if (power > 0) factors[prime] = power;
      if (n === 1) break;
      prime = primes[++i];
    }
    factors[n] = 1;
    return factors;
  }

  return {
    factor: factor
  }
})();

function numFactors(n) {
  var primeFactors = Factor.factor(n),
      count = 1;
  for (var factor in primeFactors) {
    if (factor !== "1") {
      count *= (primeFactors[factor]+1);
    }
  }
  return count;
}

function triangleN(n) {
  return n * (n + 1) / 2;
}

function euler12() {
  var i = 0;
  while(numFactors(triangleN(++i)) < 500);
  return triangleN(i);
}
timer(euler12);
// euler12 x 1: 2146.722ms
// 76576500

Optimizations

Each triangle number we are checking, when being factored is re generating the primes that it needs to check. Let’s try pre-generating a list of prime numbers.

var Factor = (function(n) {
  function factor(n, primes) {
    var factors = Object.create(null),
        i = 0,
        prime = primes[i],
        power;
    factors[1] = 1;
    while (prime * prime <= n) {
      power = 0;
      while (n % prime === 0) {
        power++;
        n = n / prime;
      }
      if (power > 0) factors[prime] = power;
      if (n === 1) break;
      prime = primes[++i];
    }
    factors[n] = 1;
    return factors;
  }

  return {
    factor: factor
  }
})();

function numFactors(n, primes) {
  var primeFactors = Factor.factor(n, primes),
      count = 1;
  for (var factor in primeFactors) {
    if (factor !== "1") {
      count *= (primeFactors[factor]+1);
    }
  }
  return count;
}

function euler12() {
  var primes = Primes.primesTo(65536),
      i = 0;
  while(numFactors(triangleN(++i), primes) < 500);
  return triangleN(i);
}
timer(euler12);
// euler12 x 1: 128.406ms
// 76576500

Let’s try not using our prime factor function and count the number of divisors as we go.

function numFactors(n, primes) {
  if (n < 3) return n;
  var i = -1, count = 1, power, prime;
  while (true) {
    prime = primes[++i];
    if (prime * prime > n) {
      count *= 2;
      break;
    }
    power = 0;
    while (n % prime === 0) {
      power++;
      n = n / prime;
    }
    if (power > 0) count *= (power + 1);
    if (n === 1) break;
  }
  return count;
}

function euler12() {
  var primes = Primes.primesTo(65536),
      i = 0;
  while(numFactors(triangleN(++i), primes) < 500);
  return triangleN(i);
}
timer(euler12);
// euler12 x 1: 11.027ms
// 76576500

Math

Looking again at the generalization for the triangle numbers

$T_n = \frac{n (n+1)}2$

we can use the fact that $n$ and $n+1$ are co-prime, meaning they do not share any common prime factors. Because of this, we can generalize the number of total divisors for a triangle number as:

$D(t) = D(\frac n2) \times D(n+1)$ if n is even.

$D(t) = D(n) \times D(\frac {n+1}2)$ if n+1 is even.

function euler12() {
  var primes = Primes.primesTo(65536),
      n = 0;
      factors = -1;
  while(factors < 500) {
    n++;
    if (n % 2) { // n is odd
      factors = numFactors(n, primes) * numFactors((n + 1) / 2, primes);
    } else { // n is even
      factors = numFactors(n / 2, primes) * numFactors(n + 1, primes);
    }
  }
  return triangleN(n);
}
timer(euler12);
// euler12 x 1: 7.033ms
// 76576500