# Project Euler Problem 12 in F#

After a brief digression with an RPN Calculator, here we are again with a new Project Euler problem:

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?

Again, this problem is relatively simple to solve and it's about finding an algorithm with decent performances.

## The naive (slow) solution

• Considering that triangle numbers are a mathematical sequence defined as follows:
$$t_n = t_{n-1} + n$$ where $$t_0 = 0$$, then we easily define an F# sequence that yields triangle numbers using Seq.unfold.
• We then define a function all_factors_slow_rec to calculate all factors (not just primes) of a given number. The slow solution presented in the first listing starts from a number $$n$$ and then by brute force tries all the numbers down to $$1$$ as a candidate factor.
• Once we have these two pieces together, it is just a matter of enumerating all possible triangle numbers, finding for each their factors (using Seq.map) and finally determining the first triangle number having at least 500 factors (using Seq.tryFindIndex). If $$i$$ is the index of such a number, we then go back to the original sequence of triangles to extract the $$i^{th}$$ element.

## An improved version

The bottleneck of the previous solution is the naive approach to find all the factors of a number. On my machines this solution takes several minutes.

Better performances can be obtained observing that in order to determine all the factors of a number we don't have try all smaller numbers. As a matter of fact, the following is true (considering n the number to be factorized):

• if $$n / x = y$$, obviously both $$x$$ and $$y$$ are factors, so I don't have to probe y anymore
• If I start probing from 2 going up, I can stop probing when I have reached $$\sqrt n$$. In fact, any number bigger than $$\sqrt n$$ must have been already found probing a smaller number.

Suppose for example that we have to factor the number 36 (one of the triangle numbers):

• 1 is always a factor -> factors = {1, 36}
• 2 * 18 = 36 -> factors = {1, 36, 2, 18}
• 3 * 12 = 36 -> factors = {1, 36, 2, 18, 3, 12 }
• 4 * 9 = 36 -> factors = {1, 36, 2, 18, 3, 12, 4, 9}
• 5 does not divide -> factors = {1, 36, 2, 18, 3, 12, 4, 9}
• 6 * 6 = 36 -> factors = {1, 36, 2, 18, 3, 12, 4, 9, 6}

We can stop here because if 7 divided 36 evenly, we would have already found a number x < 6 such that 7 * x = 36.

The improved version runs on my machine in less than 1 second.

Updated: