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*

Great write up, but I spent the longest time trying to figure out how the “isTriangleNumber” function actually did its work. After a bit of googling, I found that it’s just a known formula for exactly that test. It may be intuitive for some, but it was completely lost on me, and with the bar set so high with the theory behind Step 1, I thought I had to be missing something.

It might be helpful for the next guy to add in a bit about the theory behind Step 2 as well. Thanks!

LikeLike

Your first step looks bizarre but works correctly in this case since 500 is a composite number with many primes and low power. But what if I rephrase the original question to “find the first triangle number with more than 499 divisors”? Now you realize that 499 is a prime number, so your first starting point would be:

N = p^(499-1) = 2^498 = some very large number with 149 digits in base 10.

Which is already way too large for the answer.

The error here is that you miss to see that a total number of divisors of N is not an increasing order as N increased, e.g., 12 is the first number to have 6 divisors, while 16 is the first number to have 5 divisors.

So in order to find a number X that has larger number of divisors than N, you can’t make an assumption that you can start at number Y, where Y < X, and Y has number of divisors less than or equal to N.

Besides, this very first problem on Project Euler doesn’t require you to reduce a starting point at all! I run your code against my normal iterative method which finds number of divisors starts from 1,3,6,10,15,… the differ in result time is insignificant.

Also the majority time of your code is spent on “divisors(n)” function, which could be a lot faster by factorize a number into a list of prime numbers first, count occurrence for each prime, then use your mention theorem to find a number of divisors. Instead of listing every possible numbers lesser than N and check if that number is a divisor.

LikeLike