Project Euler Problem 12 Solution

Project Euler & HackerRank Problem 12 Solution

Highly divisible triangular number
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

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:

 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:

The two factors of the triangle formula

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

Total divisors of a triangle number

We use separate formulas for even and odd n to guarantee the division by 2 is a whole number.

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 45,000 was 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

HackerRank Project Euler 12 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

Last Word

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 (3+1)(1+1) = 8.

In general, the number of divisors for n (including 1 and n) is: Total divisors for n where prime numbers are prime numbers.

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

Total divisors for T_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.