Project Euler - Problem 12 - Solution Explained

Highly Divisible Triangular Number
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?

I broke this problem down into mini-problems.  All of which were related to one primary concern: A triangular number with 500 factors is probably really really big.  Those mini-problems are as follows:

1. How do I convert $n$ to its corresponding triangular number without having to sum up all the preceding numbers in the series?
2. How do I calculate the number of factors of $n$ without actually having to figure out what each of those factors are?
3. Is there any way to run my functions on $n$ instead of its corresponding triangular number?

Once I solved the mini-problems, solving the actual problem was quite trivial.

1. Converting $n$ to it's corresponding triangular number.

Luckily, there is a well known formula for converting numbers to their corresponding triangular number.  The intuition behind the formula can be found here.  If $n$ represents any integer and $T(n)$ represents it's corresponding triangular number, then: $$T(n) = \dfrac {n\times (n+1)}{2}$$ The formula allows us to avoid having to use the addition operation for every integer preceding the one we're interested in.  Implementing the equation is also fairly straight forward.

function tri(num) {
  return (num * (num + 1)) / 2;
}

2. Counting the factors of $n$.

I did find an easy way to count the factors of $n$ without ever having to find what it's factors actually are.  The intuition behind the method can be found here.  If $n$ represents any integer, $D(n)$ represents the number of factors of $n$, while $P(n)$ represents the prime composition of $n$, and $p$ represents some prime number with exponent $x$ then: $$P(n)=p_1^{x_1}\times p_2^{x_2}\times p_3^{x_3}\times \dots$$$$D(n) = (x_1 + 1) \times(x_2 + 1) \times(x_3 + 1) \times \dots$$ I must admit, coming up with an algorithm to implement the above method was a lot more difficult than I was anticipating.  The algorithm is implemented below and it may not be immediately obvious how it's works.  I have annotated it as best I can.  I needed a list of prime numbers which I previously calculated for problem #7.  If you plan on implementing this algorithm, you can find a list of prime numbers here.

function factorCount(num) {
  let count = 1;
  for (let prime of primes) {     // See note A.
    if ((prime * prime) > num) {  // See note B.
      count *= 2;                 // See note C.
      break;
    }
    let exponent = 0;             // See note D.
    while (num % prime == 0) {    // See note E.
      exponent++;
      num /= prime;
    }
    if (exponent > 0) {           // See note F.
      count *= exponent + 1;      // See note G.
    }
    if (num == 1) {               // See note H.
      break;
    }
  }
  return count;                   // See note I.
}

Notes on the above algorithm.

1. I needed a list of prime numbers to implement this algorithm.  In this example, the global constant primes represents an array of prime numbers in ascending order, starting at 2, and ending at 104743.
2. First, we need to establish an exit condition so that we won't need to iterate over the entire list of primes.  Since we only need to search from $1 \longrightarrow \sqrt{n}$ to find factors of $n$, the very first prime whose square is greater than $n$ tells us that we no longer need to evaluate any primes at that point or beyond.
3. We double the count since every factor of $n$ has a co-factor after $\sqrt{n}$.
4. We must now determine the exponent of the prime we are evaluating. We start our exponent counter at 0.
5. So long as $n$ is divisible by our prime, we can increment our counter while dividing out the prime.  To help visualize this: Imagine that $n=8$ and we are evaluating the prime $p=2$.  To get our exponent, we progressively divide $n/p$ while also increasing our exponent counter by 1 each time the division occurs.  At the end of this process, our exponent counter will equal 3.  This makes sense because $8 = 2\times 2\times 2 = 2^3$
6. Before we proceed, we need to check if the counter moved at all.  This tells us whether $n$ was divisible by the prime. If it wasn't divisible, we cannot apply the method.
7. Now that we have determined the exponent.  We can finally apply the method!
8. Lastly, we need to break out of the loop if $n=1$.  Think back to the $n=8$, $p=2$ example (from note E).  When all of the $p$'s are divided out of $n$, $n=1$.  At that point, there is no sense trying to evaluate the next prime.
9. Since the variable count now equals the number of factors of $n$, we can return it.

3. Working with $n$ instead of $T(n)$.

Let's say that $n$ is any positive integer, $T(n)$ is the corresponding triangular number of $n$, and $D(n)$ is the number of factors of $n$.  Than, this Euler problem is asking us to find the $T(n)$ for which $D(T(n)) > 500$.  The question is, how do we find $D(T(n))$ efficiently?
Since $T(n)$ is many, many times larger than $n$, we can speed up our calculation dramatically if we could just work with $n$.  The strategy is to use $T(n) = \dfrac {n\times (n+1)}{2}$ to find $D(T(n))$ in terms of $n$.  If we do the math, then: $$D(T(n)) = D\left (\dfrac {n\times (n+1)}{2}\right )=$$$$D\left (\dfrac {n}{2}\right )\times D(n+1)\implies \text{if }n\text{ is even}$$$$D(n)\times D\left (\dfrac {n+1}{2}\right )\implies \text{if }n\text{ is odd}$$If we use our factorCount function above to represent the $D(n)$ the resulting code can take any integer and spit out the number of factors of it's corresponding triangular number.  The code is as follows:

function triFactorCount(num) {
  let term1, term2;
  if (num % 2 == 0) {
    term1 = factorCount(num / 2);
    term2 = factorCount(num + 1);
  } else {
    term1 = factorCount(num);
    term2 = factorCount((num + 1) / 2);
  }
  return term1 * term2;
}

Putting it all together!

This is my solution to Project Euler, Problem 12.  I'll be using the tri and triFactorCount functions as they've been defined above.

let num = 1;

while (triFactorCount(num) < 500) {
 num++;
}

console.log(tri(num));