Daily Coding Problem: Triangular Numbers and Big Divisors

Welcome back everyone with another problem to solve! Today, we’ll talk about triangular numbers and their divisors: especially huge ones!

While we can admire my fabulous artistic representation of triangular numbers in nature, let’s have our usual disclaimers:

This problem is provided by the wonderful website ProjectEuler.net, which you can subscribe to here! There are more than 800 math and coding problems to solve and a vast archive of discussions about them. It is literally the perfect tool to scrap your head around and learn something new! Go check it out and try to solve your challenges too!
I’m not an expert programmer: just a guy who enjoys writing about this kind of stuff and likes to share his shots. I’m sure this won’t be the optimal solution, so if you have a better one or any idea about how to optimize it you are more than welcome if you want to share!

Enough talking, let’s see what today’s problem has to offer:

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:

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?

The problem is quite straightforward: we are asked to understand what is the first triangular number which has more than 500 divisors. First things first, let’s have a better look at what a triangular number is and what a divisor is.

Triangular Numbers

Triangular numbers are a particular subset of numbers that are formed by the sum of all the natural numbers up to a certain one. They are called triangular because you can always arrange them as a triangle. Here are some examples:

In the image above, it’s the 3rd, the 4th, and the 5th triangular numbers. So, for example, the 3rd number is formed as 1+2+3 = 6, the 4th as 1+2+3+4 = 10, and so on. Generally speaking then, the nᵗʰ triangular number, Tₙ, is equal to

This is, of course, one of the most famous series in mathematics, presented also by Gauss, who stated that the sum of consecutive integers is equal to:

So basically, if we want to calculate the 3rd triangular number, for example, we simply calculate 3*4/2 = 6. This will be very helpful once we’ll start writing our solution!

The Divisors

To give a definition of the divisor (or factor) of a number n, it’s really simple: it’s a number j that can be multiplied by another integer k to give out n again. For example, 3 is a divisor of 18, because we can multiply 3 and 6 to obtain 18 again.

However, 5 is not a divisor of 18, because there is no number k that multiplied with 5 gives out 18.

By the definition, we also obtain an important property: if j is a divisor of n because it can be multiplied by k to obtain n, then also k is a divisor of n because it can be multiplied by j to obtain n.

This way we can be sure that a number n has always at least two divisors j and k ( in fact, j can always be 1 and k be n).

Also, to put it in another way, a number j is a divisor of the number n if the remainder of n / j is equal to 0. So, for example, 18/3 = 6, and the remainder is 0.

We can formalize better this concept with modular arithmetic saying that j is a divisor of n if n % j = 0. In other words, we obtain this second property:

The third and last property we are interested in is that there can be no divisor of a number n greater than n/2, rather than n itself. This is pretty simple to understand. From the first property, we know that factors are somehow “linked” together in the range 1,…,n.

This is because again, if j \ n, it’s because j * k = n. Therefore, also k \ n. Let’s take 18 again as an example, find its divisors, and color them to reflect this property.

So, for instance, if j = 3, k = 6, and the other way around if j = 6, k = 3, this means that the smallest j we can use, besides 1, is 2, which gives us the biggest k possible, n/2 (9 in our case). This works:

for even numbers, in which case the biggest factor will be exactly equal to half of n;

for odd numbers: if we can’t divide n by 2 (because being odd will give us a rational number); this means we can only use j > 2, which will always give us results k < n/2.

Finally, there is only one case in which j and k can be equal: when n is a square number. For example, when n = 36, a possible factor j = 6 will produce another factor k = 6. We’ll discuss more about this case later in the code part.

These concepts are pretty trivial, of course, but they will be very important in our solution!

The Code

The code will be written in Go, for it’s really a fast language that still maintains a great level of readability. We will split the solution in two: first, we’ll create a function to find the divisors of a number, and then we will apply it to the triangular numbers.

Let’s see the function first:

https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true

We create our function which accepts an integer n and returns an array of integers out , which will contain our divisors. After that, we append to out the trivial factors, namely 1 and n itself.

Then we start looping j from 2 to n/2 (from the second property; also note that we are not interested in n/2 itself because in case n is even, k = n/2 will be added to the divisors by the j = 2 iteration: this is why we stop at j<n/2 and not j≤ n/2 ).

This way, we can check for divisors only in the first half of n , speeding up the process quite a little.

At each loop, we check 3 things:

The third if statement actually checks if n%j==0 , in other words, if 0 ≡ n (mod j). If so, we found a factor, and we add j to the list. We can also append its counterpart k to the list, by calculating n/j and then moving on to the next j ;

The second if statement checks whether n is a square, and so j is the root of n . If so, only one divisor j will be added to out , so to avoid duplicates, and then the algorithm moves on.

Suppose n = 36: if this little block would be missing, the third if statement would be triggered, causing out to receive j = 6 and k = n/j = 36/6 = 6 , thus, creating a duplicate.

The first if statement is the most complex: its purpose is to check if we are starting to have repeating j-k pairs. If so, we can instantly break the loop, for our factor will all already be present in out .

Specifically about this third point, there are two cases to check: whether out[len(out)-1] == j or out[len(out)-2] == j .

The first case is the classic one: take the number T₇ = 28 for example:

When j = 7 , it will be equal to the last value inserted. Therefore, we can break the loop.

The second case only occurs when we found a square n . Take 36 again, for example:

When j = 9 , it will be equal to the last value appended before the square root of n , which appears only once. Therefore, at this point, we can break the loop.

Finally, we can simply return out to have our divisors.

Applying the Results

Now that we have our function, we can apply it to every triangular number. We are going to create a counter c which will serve as a generator for our triangular numbers. We calculate the associated triangular number tn with the Gauss equation and check for how many divisors it has.

If it’s more than 500, we return that tn as result.

https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go

But…there’s a catch!

ProjectEuler.net is really a lovely project: besides presenting math riddles and problems, their main focus is to provide a tool to start learning, thinking, and reasoning about math.

And I love that: they are so committed that publishing results and guides for their problems is actually forbidden (this is one of the first 100 problems, so I understand it is permitted).

Given this, I don’t think it would be fair to just give out the solution to copy-paste and get the achievement. For this reason, I’m not giving you the actual solution: try it out for yourself and try to come up with a better algorithm than mine (There are plenty of them). Sorry guys! 😅

Time Complexity

I’m confident that there are many better solutions because I feel this one is a pretty terrible shot!

The FindDivisor function runs in linear time: since it depends on the size of the instance n , and it also runs at most n/2 loops; we can consider it to be an O(n).

However, we must calculate each triangular number first, which also takes O(tn) time, where tn is the result (the last one we actually calculate). Given this, approximately the time complexity of the whole algorithm should be O(tn*n).

Since tn becomes the argument or our function, and we run at most n/2 loops inside it, we can rewrite the time complexity as O(tn*tn/2) = O(tn²/2) = O(tn²). So a quadratic time solution, unluckily!

I was surprised though that even if the algorithm is about that kind of complexity, it runs pretty fast nonetheless. To give out a result on my machine (AMD Ryzen 5, avg. ck. 2700 MHz) it took 322.564227 ms.

Trying to find the first triangular number exceeding 1000 divisors took 3.827144472 seconds though, so it’s clearly visible that the time consumption is ramping up rapidly.

Conclusion

We finally made it! I hope you guys enjoyed the article, and I hope you could take something interesting from it: if so, please leave a clap or two and share the article with someone who could be interested in this topic!

A big shoutout to ProjectEuler again for the fantastic job: I really want to suggest you go and check out what they can offer; I’m sure you’ll find it super interesting!

And as always, thanks for reading.

Nicola