From
Project Euler:
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?
A way to solve this problem is fairly straight-forward: progress through all the triangle numbers, figure out their divisors, and count them. A simple brute force method is to just enumerate all the numbers up to $\sqrt{n}$, and for each one that divides $n$, add 2 to our count (one for this number, and one for $n$ divided by it). The corner case is if $n$ is square, just count the square root once:
(defn num-divisors [n]
(loop [current 1
total 0]
(cond
(> current (Math/sqrt n)) total
(== current (Math/sqrt n)) (+ 1 total)
:else (recur
(+ 1 current)
(+ total
(if (== 0 (mod n current)) 2 0))))))
We can then do a simple search through all the triangle numbers to get the first one that has at least 500 divisors:
(defn search-brute-force [limit]
(loop [n 1
triangle 1]
(let [d (num-divisors n)]
(if (> d limit)
triangle
(recur (+ 1 n)
(+ triangle (+ 1 n)))))))
Unfortunately, this goes well past the one minute limit. Let's see if we can speed this up a bit. Take the formula for a triangle number $T_n$:
$$
T_n = \sum_{i=1}^n = \frac{n(n + 1)}{2}
$$
From this formula we can infer a few other interesting details. Whenever you have two sequential numbers one of them will be even and the other will be odd. Any even number will be divisible by 2, so the 2 in the denominator will get cancelled out by that and we'll be left with a divisor of $T_n$. The odd number left over will also be a divisor.
To write this out more explicitly, if $n$ is even then $\frac{n}{2}$ and $n + 1$ are divisors of $T_n$; if $n$ is odd then $n$ and $\frac{n + 1}{2}$ are divisors of $T_n$.
Next we'll want to dig into the properties of divisors. Any number can be broken down into a product of prime numbers, and some of those primes might be duplicated (for example, 4 = 2 * 2). So we can write any number $n$ like this:
$$
n = p_1^{c_1} * p_2^{c_2} * ...
$$
Then for each prime $p_i$, there's going to be $c_i$ factors of $n$ from that prime: $p_i$, $p_i^2$, $p_i^3$, all the way up to $c_i$. Each one of those can multiply with every other factor of $n$ to produce another factor (for example with $n = 28$ you can have $2 * 7$ to produce 14). So the number of divisors $d(n)$ is $c_i + 1$ multiplied by all the other possibilities:
$$
d(n) = (c_1 + 1) * (c_2 + 1) * ...
$$
Lastly, if you have two numbers $a$ and $b$ that are co-prime with one another, this means that they do not share any divisors other than 1. Therefore none of the $p_i$s are the same, so the number of divisors is just the product of the number of divisors for $a$ and $b$ separately. Since $n$ and $n + 1$ are necessarily coprime, we can just multiply the number of divisors of $n$ with the number of divisors of $n + 1$, dividing the even one by 2 to remove the denominator in the formula for $T_n$:
$$
d(T_n) = \left\{
\begin{array}{ll}
d(\frac{n}{2}) * d(n + 1) & n\ even \\
d(n) * d(\frac{n + 1}{2}) & n\ odd
\end{array}
\right.
$$
These two numbers should be quite a lot smaller than $T_n$, so the search time will be much faster.
Let's write out a little function to calculate the number of divisors of a triangle number:
(defn num-triangle-divisors [n]
(if (even? n)
(* (num-divisors (quot n 2))
(num-divisors (+ 1 n)))
(* (num-divisors n)
(num-divisors (quot (+ 1 n) 2)))))
And then tweak our search function to use this instead:
(defn search-triangle [limit]
(loop [n 1
triangle 1]
(let [d (num-triangle-divisors n)]
(if (> d limit)
triangle
(recur (+ 1 n)
(+ triangle (+ 1 n)))))))
This one is much faster, even with the 3s or so it takes for lein to start up:
$ time lein run
76576500
real 0m3.848s
user 0m4.687s
sys 0m0.355s