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:
1:13:1,36:1,2,3,610:1,2,5,1015:1,3,5,1521:1,3,7,2128: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?
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
Sn=n(a1+an)2and that means for triangle numbers:
Tn=n(n+1)21,3,6,10... T1=1×(1+1)2=1×(2)2=1T2=2×(2+1)2=2×(3)2=3T3=3×(3+1)2=3×(4)2=6T4=4×(4+1)2=4×(5)2=10
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α×qβ×...rγIt is also true that any number, m, that is a power of a prime, p, m=pα, m will have α+1 factors. For example:
5=51, factors ↦1,5↦50,518=23, factors ↦1,2,4,8↦20,21,22,239=32, factors ↦1,3,9↦30,31,32Now consider a number that is composed of multiple primes:
n=pα×qβ×...rγThe number of total divisors can be determined by the powers of the prime decomposition using the rule of product
, so n will have:
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
Tn=n(n+1)2we 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(n2)×D(n+1) if n is even.
D(t)=D(n)×D(n+12) 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