Triangular Numbers

A couple days ago, a friend of mine came to me with a Project Euler problem on Triangular Numbers. He had solved it but for some reason, his solution ran for too long. He asked me to solve alongside. Being my lazy self, I asked for his code so I could optimize that instead of writing the whole solution from scratch. He gladly gave it to me. So happy, less work. It did not turn out that way though…

First was a couple test runs and profiling on his solution. Finding the first triangular number with more than 200 divisors took about 3.5 minutes to complete. Feeling brave, I tested it out on the desired triangular number with more than 500 divisors. Mistake. I had time to go down to the nearby convenience and get some groceries before coming back to watch the tool finish its computation. It took a stunning 18 minutes!

Reading the code, it looked pretty standard and followed everything the problem described Triangular numbers to be. I tried using a recursive approach to finding the triangular numbers but the stack level ran too deep. A little more research about triangular numbers revealed they are in our everyday life. From billiards to Pascal’s Triangle (I knew they had to be in there somewhere) and so on. Even some stunning facts too. Seeing how basic this was, and with time on my hands, I pulled out a multiplication table and voila! They were sitting right there in a descending staircase pattern.


[nth] triangleNumber
. . if n == 1, return 1
. . int i = 3, j = 1, count = 1
. . while true
. . . . return i * j, unless count < n
. . . . count++
. . . . return i * (j++), unless count < n
. . . . count++, i += 2, j++

This is my generator function for triangular numbers. It got the job done faster and the tool now ran for 3.3 minutes for the 200 divisors test case. The current divisor function was the generic one. If you have a desired number, n, which you want to find its number of divisors, loop through all numbers from 1 to n. If any of the numbers can divide n without remainders, this is a divisor; so increase the divisor count.

Staring at this piece of code, I made some tea and turned up some jazz.

Then I realized, divisors do something spectacular, they divide, what’s the use of traversing the whole spectrum when you can go only halfway and get the same results. Honestly, this was the laziness talking. But I stuck with it nonetheless. After a little brain tinkering, jazz music and zoning off for a little while, I came up with this pseudocode translated from my code. Don’t :


divisors of n
. . int numberOfDivisors(0), i(1), limit(n)
. . while i < limit
. . . . if i divides n without any remainder
. . . . . . increase numberOfDivisors by 1
. . . . . . decrease limit to n / i
. . . . i = i + 1
. . return numberOfDivisors * 2

This shrinks the traverse space as she computes. She’s like my little AI (Artificial Intelligence); she learns on-the-go. She reduced the runtime of the 500 divisors test case from 18 minutes to 305904 micro seconds (about 0.3s).

Obviously, every smart algorithm has it’s downfalls. This baby has a serious weak point when it comes to prime numbers. Her worst input would be a list of prime numbers as there is no reduction possible. But since triangular numbers are not prime, she served her purpose perfectly while being poetic about it.

Advertisements

Share your knowledge

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