Highly Divisible Triangular Number — Project Euler (Problem 12)

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.

TriangularNumber_900

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 abq4r4s4 where a, b, q, r, s are primes that minimize abq4r4s4. This is satisfied by 7x11x24x34x54 = 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 2s to arrive at the answer):

Ans: 76576500

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s