Screenshot-2018-11-03-at-00.15.35

I couldn't find a short and reasonable explanation for this problem. That is why I'm writing this simple article which is essentially distilled from a bunch of stackexchange answers. I won't give you the solution, but rather point you in the right direction.

This was the first problem that I spent more than 20 minutes on. I assume that most people (myself included) tried brute-forcing our way through this, just to realise that it would take a couple of hours to get the solution.

I do think that this problem is unapropriate for the 12th problem, because all of the previous ones are trivial, while this one all of a sudden requires you to flex your maths dramatically.

The maths behind Problem 12

We are going to use two important premises.

1. Coprime numbers

Coprime numbers are numbers which only have 1 common divisor. Take 5 and 6 for example. Only number 1 divides them both.

The neat thing about coprime numbers is that if you want to get the number of divisors (not prime divisors, all divisors!) of their product, it is the product of the number of divisors of individual coprime numbers in the first place.

let a and b be coprime
num_divisors(a*b) = num_divisors(a) * num_divisors(b)

2. Triangle numbers and coprimes

n-th triangle number is essentially a sum of all the numbers up to n. There is a formula for that: sum up to n = [n*(n+1)]/2

The main thing to notice is that you can rewrite/refactor this formula in order to have it as a multiplication of two coprime numbers (I hope you see where we are going with this).

If n is even, we have n/2 * (n+1), where n/2 and (n+1) are coprimes. Try and figure yourself why we rewrite it in this fashion.
If n is odd, we have n * (n+1)/2. Again, figure this one out yourself.

The solution

Great. Now we just iterate n from 1, and, depending if its even or not, we calculate which two coprime numbers when multiplied give us n-th triangle number. Then we calculate number of their divisors, multiply it - and voila! We have the number of divisors for n-th triangle number.

With this approach we basically have "divide and conquer" strategy - instead of finding divisors of n-th triangle number (let n be big), we find two coprimes which when multiplied give our triangle number. And then we just multiply the number of their divisors instead.

Essentially we just moved the ball from the "big numbers" field into the "small numbers" field - hence the performance improvement :)

Stjepan