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 realized that factoring large triangle numbers was going to take way too long. The problem’s choice for triangle numbers had to be significant and there must be some property that would lend itself to a fast calculation of the number of divisors.

In fact, knowing that the two consecutive factors of the triangle formula, n and n+1, are inherently co-prime was key to a fast solution. Consider: If q>1 divides n then dividing n+1 by q leaves a remainder of 1, so q does not divide n+1 making n and n+1 co-prime.

Now, if the two factors are coprime, we can find the divisors for the triangle number by multiplying the divisors for each of the factors—a much easier and faster task. Here is how the two factors were separated:

The two factors of the triangle formula

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

Total divisors of a triangle number

Also, since we can only find the divisors for whole numbers, the algorithm has to select a formula that will yield a whole number when dividing 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 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 the first triangle number to have over 1 ≤ N ≤ 1000 divisors. This extends the number of divisors from 500 and runs 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.