Project Euler Problem 12 Statement
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:
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?
While investigating a solution, I quickly discovered that factoring large triangle numbers was taking way too long. The problem’s choice for triangle numbers must be significant and we will have to find some property that would lend itself to a fast calculation for the number of divisors.
In fact, knowing that the two consecutive factors in the triangle formula, n and n+1, are inherently co-prime was key to a fast solution. Consider: When q is greater than one and divides n then dividing n+1 by q leaves a remainder of 1. Therefore, n and n+1 are co-prime.
Now, if the two factors are coprime, we can find the number of divisors for the triangle number by multiplying the number of divisors for each of the factors—a much easier and faster task. Here's how we separate the two factors:
And here is the calculation for the total number of divisors:
We are using two separate formulas to guarantee an even divisibility by 2.
The only part I don’t like is having to guess an n (the index of a triangle number) that’s big enough to find a solution. In this case 42,500 was arbitrarily big enough for solving the number of divisors greater than 1,000. We are using an iterative approach to filling the list,
d, with divisors. Below, I mention how to use primes to find the divisors more quickly.
HackerRank wants us to find the first triangle number to have over 1 ≤ N ≤ 1000 divisors; extending the number of divisors from 500 and running 10 test cases. This algorithm calculates the answer for 1000 in 70ms.
Python Source Code
def f(L, nMax=42500): d = *nMax for n in range(2, nMax): for j in range(n, nMax, n): d[j]+= 1 nDiv = d[n-1]*d[n//2] if n%2==0 else d[(n-1)//2]*d[n] if nDiv > L: return (n-1)*n//2 for _ in range(int(input())): print (f(int(input())))
You can use prime factors to find the total number of divisors for n. For example, if n=24: 24 = 2331 and the number of divisors can be calculated as
In general, the number of divisors for n (including 1 and n) is: where are prime factors of n.
Now, if we were required to find the first triangle number with the number of divisors > 100,000 then using primes is faster. And incorporating our understanding from the above discussion we know that
for gcd(m, n) = 1. That is, d is multiplicative when m and n are co-prime. And since m and n are much smaller than the triangle number itself, calculating the number of divisors for the two factors of the triangle number is much faster.