Project Euler Problem 12 Solution: Highly divisible triangular number

Project Euler Problem 12 Statement

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?

Solution

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:

$$\frac{n(n+1)}{2}=\begin{cases} \frac{n}{2} \cdot (n+1), & n \text{ is even} \\ n \cdot \frac{n+1}{2}, & n+1 \text{ is even} \end{cases} $$

And here is the calculation for the total number of divisors:

$$d\left(\frac{n(n+1)}{2}\right)=\begin{cases} d\left(\frac{n}{2}\right) \cdot d(n+1), & n \text{ is even} \\ d(n) \cdot d\left(\frac{n+1}{2}\right), & n+1 \text{ is even} \end{cases}$$

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 version

Solves all test cases for Hackerrank Project Euler Problem 12

HackerRank Project Euler 12 wants us to find the first triangle number to have over 1 ≤ N ≤ 1000 divisors; running 10 test cases.

Python Source Code

def f(L, nMax=42500):
    d = [1]*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())))

Last Word

You can use prime factors to find the total number of divisors for $n$. For example, if $n=24 = 2^3\cdot 3^1$ and the number of divisors can be calculated as $(3+1)(1+1) = 8$.

In general, the number of divisors for n (including $1$ and $n$) is: $p_1^{a_1}p_2^{a_2}...p_n^{a_n} = (a_1 + 1)(a_2+1)...(a_n+1)$ where $p_1, p_2, ..., p_n$ 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

$$d(mn) = d(m) \cdot d(n)$$

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.