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, 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.