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 , which you can subscribe to ! 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! ProjectEuler.net here 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 which has more than 500 . First things first, let’s have a better look at what a triangular number is and what a divisor is. triangular number divisors 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 . Here are some examples: you can always arrange them as a triangle 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 , who stated that the sum of consecutive integers is equal to: Gauss 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 (or ) of a number it’s really simple: it’s For example, 3 is a divisor of 18, because we can multiply 3 and 6 to obtain 18 again. divisor factor n, a number that can be multiplied by another integer to give out again. j k n However, 5 is not a divisor of 18, because there is no number that multiplied with 5 gives out 18. k By the definition, we also obtain an important property: if is a divisor of because it can be multiplied by to obtain then also is a divisor of because it can be multiplied by to obtain j n k n, k n j n. ( in fact, can always be 1 and be ). This way we can be sure that a number has always at least two divisors and n j k j k n Also, to put it in another way, . So, for example, 18/3 = 6, and the remainder is 0. a number is a divisor of the number if the remainder of is equal to 0 j n n / j We can formalize better this concept with saying that is a divisor of if In other words, we obtain this second property: modular arithmetic j n n % j = 0. The third and last property we are interested in is that This is pretty simple to understand. From the first property, we know that factors are somehow “linked” together in the range 1,…,n. there can be no divisor of a number greater than rather than itself. n n/2, n This is because again, if it’s because Therefore, also Let’s take 18 again as an example, find its divisors, and color them to reflect this property. j \ n, j * k = n. k \ n. So, for instance, if and the other way around if this means that the smallest we can use, besides 1, is 2, which gives us the biggest possible, (9 in our case) This works: j = 3, k = 6, j = 6, k = 3, j k n/2 . 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 by 2 (because being odd will give us a rational number); this means we can only use which will always give us results n j > 2, k < n/2. Finally, For example, when a possible factor will produce another factor We’ll discuss more about this case later in the code part. there is only one case in which and can be equal: when is a square number. j k n n = 36, j = 6 k = 6. These concepts are pretty trivial, of course, but they will be very important in our solution! The Code The code will be written in , 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 . Go 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 and returns an array of integers , which will contain our divisors. After that, we append to the trivial factors, namely 1 and itself. n out out n Then we start looping from 2 to (from the second property; also note that we are not interested in itself because in case is even, will be added to the divisors by the iteration: this is why we stop at and not ). j n/2 n/2 n k = n/2 j = 2 j<n/2 j≤ n/2 This way, we can check for divisors only in the first half of , speeding up the process quite a little. n At each loop, we check 3 things: The third if statement actually checks if , in other words, if 0 ≡ n (mod j). If so, we found a factor, and we add to the list. We can also append its counterpart to the list, by calculating and then moving on to the next ; n%j==0 j k n/j j The second if statement checks whether is a square, and so is the root of . If so, only one divisor will be added to , so to avoid duplicates, and then the algorithm moves on. n j n j out Suppose : if this little block would be missing, the third if statement would be triggered, causing to receive and , thus, creating a duplicate. n = 36 out j = 6 k = n/j = 36/6 = 6 The first if statement is the most complex: its purpose is to check if we are starting to have repeating pairs. If so, we can instantly break the loop, for our factor will all already be present in . j-k out Specifically about this third point, there are two cases to check: whether or . out[len(out)-1] == j out[len(out)-2] == j The first case is the classic one: take the number T₇ = 28 for example: When , it will be equal to the last value inserted. Therefore, we can break the loop. j = 7 The second case only occurs when we found a square . Take 36 again, for example: n When , it will be equal to the last value appended before the square root of , which appears only once. Therefore, at this point, we can break the loop. j = 9 n Finally, we can simply to have our divisors. return out Applying the Results Now that we have our function, we can apply it to every triangular number. We are going to create a counter which will serve as a generator for our triangular numbers. We calculate the associated triangular number with the Gauss equation and check for how many divisors it has. c tn If it’s more than 500, we return that as result. tn https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go But…there’s a catch! besides presenting math riddles and problems, . ProjectEuler.net is really a lovely project: 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, . 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! 😅 I don’t think it would be fair to just give out the solution to copy-paste and get the achievement Time Complexity I’m confident that there are many better solutions because I feel this one is a pretty terrible shot! The function runs in linear time: since it depends on the size of the instance , and it also runs at most loops; we can consider it to be an O(n). FindDivisor n n/2 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 becomes the argument or our function, and we run at most loops inside it, we can rewrite the time complexity as O(tn*tn/2) = O(tn²/2) = O(tn²). So a , unluckily! tn n/2 quadratic time solution 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

Too Long; Didn't Read

Making security fun one episode at a time

Daily Coding Problem: Triangular Numbers and Big Divisors

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

Daily Coding Problem: Triangular Numbers and Big Divisors

Too Long; Didn't Read

Nicola Moro

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES