# Project Euler 12 Solution: Highly divisible triangular number

Problem 12

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?

## Solution

The number of divisors of a natural number $$n$$ is given by tau(n) or $$\tau(n)$$ or sometimes $$\delta(n)$$ as mentioned here already. Every natural number can be expressed as the product of their $$k$$ prime factors like this:

$n = \prod\limits_{i=1}^k p_i^{e_i}$

Then the number of divisors is given by

$\tau(n) = \prod\limits_{i=1}^k (e_i+1)$

So we need a prime factorization and simply need a product with their exponents. By modifying the factorize function from Problem 3 can, we can calculate the product easily:

function tau(num) {

var n = num;
var i = 2;
var p = 1;

if (num === 1) return 1;

while (i * i <= n) {
var c = 1;
while (n % i === 0) {
n/= i;
c++;
}
i++;
p*= c;
}

if (n === num || n > 1)
p*= 1 + 1;

return p;
}


With this function, we can formulate the final solution:

function solution(x) {

var n = 1;
var d = 1;

while (tau(d) <= x) {
n++;
d+= n;
}
return d;
}
solution(500);


One improvement could be to prepare an array of primes to loop over, to not linearly scan for primes.

« Back to problem overview