All ** ∑n** numbers are Triangle Numbers. They’re called so, because they can be represented in the form of a triangular grid of points where the first row contains a single element and each subsequent row contains one more element than the previous one.

Problem 12 of Project Euler asks for **the first triangle number with more than 500 divisors.**

These are the **factors of the first seven triangle numbers**:

** ∑1 = 1**: 1

∑**2 =** **3**: 1,3

** ∑3 =** **6**: 1,2,3,6

** ∑4 =** **10**: 1,2,5,10

** ∑5 = ****15**: 1,3,5,15

** ∑6 = ****21**: 1,3,7,21

** ∑7 = ****28**: 1,2,4,7,14,28

Here’s how I proceeded:

**First Step:** Find the smallest number with 500 divisors. Seems like a good starting point to begin our search.

**Second Step:** Starting at the number found in the previous step, search for the next triangle number. Check to see whether this number has 500+ divisors. If yes, this is the number we were looking for, else…

**Third Step:** Check n for which ∑n = triangle number found in the previous step

**Fourth Step:** Add (n+1) to the last triangle number found, to find the next triangle number. Check whether this number has 500+ divisors. If yes, this number is the answer. If not, repeat Fourth Step till the process terminates.

Now for the details:

The** First Step** isn’t exactly a piece of cake, but necessary to reduce computation time. I solved this with a bit of mental math. The main tool for the feat is the **prime number decomposition theorem**:

Every integer N is the product of powers of prime numbers

**N = p ^{α}q^{β}· … · r^{γ}**

Where

**p, q, …, r**are prime, while

**α, β, …, γ**are positive integers. Such representation is unique up to the order of the prime factors.

If N is a power of a prime,

**N = p**, then it has

^{α}**α + 1**factors:

**1, p, …, p**

^{α-1}, p^{α}The total number of

**factors of N**equals

**(α + 1)(β + 1) … (γ + 1)**

**500 = 2 x 2 x 5 x 5 x 5**

So, the number in question should be of the form **abq ^{4}r**

**where**

^{4}s^{4}**a, b, q, r, s**are primes that minimize

**abq**

^{4}r**. This is satisfied by**

^{4}s^{4}**7x11x2**

^{4}x3

^{4}x5^{4}**= 62370000**. This marks the end of the

**First Step**which is where we start our search for our magic number.

The next 3 steps would need helper functions defined as below:

As can be seen from the above code, the algorithm to **calculate divisors of an integer** is as follows:

**1.** Start by inputting a number **n**

**2.** Let an int variable **limit** **=** **√n**

**3.** Run a loop from **i = 1 **to **i = limit**

** ****3.1** if **n** is divisible by **i**

**3.1.1** Add **i **to the list of divisors** **

**3.1.2** if **i** and **n/i** are unequal, add **n/i **to the list too.

**4.** End

Finally, executing the 4 steps mentioned earlier can be done like so (the code took less than **2***s* to arrive at the answer):

Ans: *76576500*