Project Euler – 012: Triangle Numbers

 

This was originally posted in May 2015. Updated on 25 May 2016 for clarity.

I’m working on Project Euler which challenges users to use, create, or creatively reinvent algorithms to solve math problems. Problem #12 reads:

Highly Divisible Triangular Number

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?

Note: For any integer n, the triangle number is equal to (n * (n+1)) / 2.

A lot of scratch paper went into following formula for finding the number of divisors which make up a number (triangle or otherwise). The steps are as follows:

1. Create an array of the prime factors which make up that number; include all repeating digits.

Example: Using the 7th triangle number, 28, the prime factors array is [ 2 2 7 ].

2. Find the number of times each integer appears in a group of like integers.

Example: There are two 2’s and one 7. This gives {2:2, 7:1}.

3. Add 1 to the number count of each integer group.

Example: {2:2+1, 7:1+1} => {2:3, 7:2}. The reason for doing this is that, if you take just the 2’s in their own array [ 2 2 ], they make up [ 1 2 4 ] which are the 3 divisors of 2×2 (or 4). The number count n of an integer group always returns n + 1 unique divisors.

4. Multiply the repeating-integer divisor count values together.

Example: {2:3, 7:2} => 3 * 2 = 6.

5. The product of the multiplication of number count values provides the number of divisors in the original number.

Example: The number 28 divides evenly (meaning the division results in an integer) with the following numbers: [ 1 2 4 7 14 28 ]. Note that there are 6 divisors, as expected.

The previous steps account for all the math necessary to solve the problem. The rest of the work is just implementation.

Check out the simplified JavaScript implementation.


The following is the post in its original form. God help you.

What’s the best way to spend Spring Break? Some may say, “Cancun.” But they’d be wrong. It is, in fact, solving math problems and writing programs. So that is what I did.

Just before the week-long break, I continued working on Project Euler which challenges users to use, create, or creatively reinvent algorithms to solve math problems. Problem #12 was next in line for me. The problem reads:

Highly Divisible Triangular Number

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?

Note: For any integer n, the triangle number is equal to (n * (n+1)) / 2.

I made it a point to research just enough to understand the terms of the problem, but no more.

I decided to write this in C++ since that is what I’m studying for my computer science class this semester. After reading the problem several times to make sure I understood it, I opened up my text editor and began typing away. Winging it. Rookie style.

After typing the first things my brain thought were the right approach, I tested my program. As a test case, I ran the program searching for the first triangle number with over 100 divisors. The program completed in under 3 seconds. But when testing for over 500 divisors, I waited. And I waited. And I made some pasta. And I watched some Peep Show. And I forgot about my program running.

41 minutes later a little box popped up on my screen with a very large number. I submitted the number as my answer to Problem 12 and, lo and behold, I had done it! I successfully wrote an algorithm that solved the problem. But I felt neutral. Sure, I got the right answer, but a 41-minute run-time is silly. I figured I could probably solve the problem by hand in 41 minutes.

So I took a notebook to a coffee shop and started scribbling number trees. Finding the primes that made up the 1 and 2-digit triangle numbers. Finding how many possible combinations could be made from different prime numbers. I use letters to illustrate:

[A] = A (1 possible result)
[AB] = A, B, AB (3 possible results)
[ABC] = A, B, C, AB, AC, BC, ABC (7 poss)
[ABCD] = A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD (15 poss)

These numbers are familiar. I noticed this was just (2^n)-1, something that appears all the time in the world of computers. The perfect 2^n is obtained by remembering to always include 1 in the list, because 1 is a divisor of every number. If instead of [AB], I use [2, 3], I know that since 1 is implicit, 2 and 3 are given, and 6 is the only result obtained by multiplying 2 * 3. The array of multiples [1, 2, 3, 6] includes 4 possibilities. 2^2. Awesome.

This worked for telling me how many unique combinations (or multiples) I could get out of a prime number array if none of the digits repeated. If the prime array was made up of 3 unique numbers like [2, 3, 7], we know immediately that we have 2^3 = 8 multiples: [1 2 3 6 7 14 21 42]. However, the problem arises when you have some repeating prime numbers. For instance, the number 28 (the 7th triangle number) can be broken down into the following prime array: [2, 2, 7]. My next task was to find a consistent way to account for the change in the number of unique multiples that occurs when numbers in the prime array repeated (like the 2’s here).

[2, 2, 7] gives us [1 2 4 7 14 28] = 6 unique possibilities. After blowing through a lot of scratch paper, I realized that if you take the prime numbers which repeat, in this case [2 2] and find the number of unique multiples you get [1 2 4], only 3. Let x = 3. We started with [2, 2, 7] which matches the pattern for 2^3, but we dropped the [7]. It helped me to think of this as effectively subtracting one from the exponent, so now we have 2^2. But we have to get back to the original 2^n where n is originally 3. We can do this by taking the number of unique multiples made from the repeating numbers (in the case of [2 2], we get 3 multiples: 1, 2, and 4) and, for each digit to get back to our original n in 2^n (only one time, in this case), we multiply x by 2 and then set x = the new number as in [ x = x * 2 ]. So x = ( 3 * 2) = 6. This matches what we know about [2, 2, 7]’s unique multiples.

This pattern continued to work through different variations, so I’m calling it solid. For example: [2, 2, 3, 3, 7] matches the pattern for 2^n where n = 5. But [2, 2] has y = 3 multiples ([1, 2, 4]) and [3, 3] has z = 3 multiples ([1, 3, 9)]. Let x = y * z = 9. And we dropped one number [5] from 2^n where n = 5. To get back to that, we multiple x * 2 and set it equal to the resulting number. x = ( 9 * 2 ) = 18.

The prime array [2, 2, 3, 3, 7] gives the unique multiples [1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 126, 252], which totals 18.

After this mental leg-work, I was ready to rewrite my program. After a short while, I had an algorithm which completed, correctly, in under 3 seconds. In short, I spent hours in order to save 41 minutes. It felt great. My code can be viewed here.

As I said before, I researched only enough to understand the terms of the problem. On the positive side, this forced me to think for myself. (After looking up a solution, it’s easy to say, “Of course. That makes sense. I would have done that or something similar.”) On the negative side, there are so many shortcuts to problems like. I could have saved a lot of time researching the math. One such shortcut is this: every integer has the same number of multiples below its square root as above its square. (Thanks, Evan.) In the end, I’m very happy I chose to not look anything up. I learned a lot and gained some confidence in problem solving.