General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 12 – Highly Divisible Triangular Numbers
My workflow and macros:
Macro1:
Macro2:
Answer: 76576500
Last Week's Favourite Solution:
Many weird and wonderful solutions from last week made it another tough call. The solutions that stood out most were those which were able to arrive at a solution without having to create 4 separate streams. In particular, @DaisukeTsuchiya's method of creating a list to determine the potential adjustments to each number's coordinates needed, then appending this onto the main data stream, stood out for its simple yet streamlined nature. Please find this solution on page one of last week's post or click here.
Definitions:
- Triangular Numbers: A triangular number is a number that can be represented by a pattern of dots arranged in a triangle.
- Coprime: Two or more numbers are considered coprime if their only common positive factor is one.
- Basic property of divisibility:
Let's say we have 3 numbers, such as a, b and c – where:
a x b = c
Now, let's introduce another number k.
Consider the case where a is divisible by k.
Based on the first formula, we can say that (as a x b = c) c is divisible by a.
As a is divisible by k, and c is divisible by a. c is also divisible by k. In other words, all factors of a, are also factors of c.
Mathematical Theory:
Two things to note before we begin. Firstly, my workflow took over 9 minutes to run, so based on the one-minute target set by Project Euler, I have technically failed ☹️. With that being said, we’d love to hear how you get on, so feel free to include the run time in your reply. Secondly, despite what the run time may suggest, this is by far the most technical post yet. I hope you're ready!
Step 1 How to calculate a Triangular Number:
As stated in the definitions, a triangular number is a number that can be represented by a pattern of dots arranged in a triangle, with the first triangular number being 1. To keep the “triangular shape”, to get the second number, we must put 2 more dots on the bottom. Hence, the second triangular number is 3 (1 + 2).
The third triangular number requires 3 more dots to be added to the bottom, taking the value up to 6 (1 + 2 + 3). The next few triangular numbers are as follows:
- 4th triangular number: 1 + 2 + 3 + 4 = 10
- 5th triangular number: 1 + 2 + 3 + 4 + 5 = 15
- 6th triangular number: 1 + 2 + 3 + 4 + 5 + 6 = 21
Hopefully, you can now see a pattern emerging. The “Nth” triangle number is the sum of all the numbers less than or equal to N. The numbers 1….N form an arithmetic sequence and as you may recall from Problem 6, we looked at the Arithmetic Series equation, to help us easily calculate their values.
Arithmetic series:
Therefore, the Nth triangle number = 0.5 x n x (n + 1).
Now it's one thing claiming this works, but it's another thing testing it, so let's use the formula to find the 4th, 5th and 6th triangular numbers to see if the answers match.
- 4th triangular number: 0.5 x 4 x 5 = 2 x 5 = 10
- 5th triangular number: 0.5 x 5 x 6 = 5 x 3 = 15
- 6th triangular number: 0.5 x 6 x 7 = 3 x 7 = 21
Now we know that the Nth triangle number = 0.5 x n x (n + 1), we can use the basic property of divisibility to help us.
Step 2 Examining the triangle number formula:
In order to apply the basic rule of divisibility, we must have integer (whole number) values only. Because the formula divides by 2, we need to make sure the result is always a whole number before we can use the divisibility rule.
As we know, an integer is either even or odd, so let's check both cases.
N Is even:
If n is even, we can express it as follows: n = 2m, where m is any whole number
In this case, the formula becomes:
m and (2m+1) are both integer values, so for even numbers, we can apply the basic rule of divisibility.
N Is odd:
If n is odd, we can express it as follows: n = 2m + 1, where m is any whole number
The formula can then be expressed as follows:
Similarly to before, we now have two whole numbers multiples together, (2m+1) and (m+1), therefore we can apply the basic rule of divisibility.
So, what we have proven?
No matter weather n is even or odd, the triangular number formula always contains two whole numbers multiplied by each other.
From this point forward, we will discuss the case where n is even only meaning n/2 and (n + 1) are both integers:
All the work applies in the same way for the cases where n is odd.
Step 3 Applying the basic rule of divisibility:
As we now know that n/2 and (n+1) are both integers, we can apply the basic rule of divisibility. All factors of n/2 and all factors of (n+1) are also factors of the nth triangle number
As all factors of n/2 and (n+1) are also factors of Tn, they must also have all the same prime factors. So if we can list all the prime factors of n/2 and (n+1) we will have found all the prime factors of Tn.
But why is this helpful? Well, we can actually find out the number of factors a number has by using its prime factors. The formula that helps us do this is often called, divisor function formula. It works as follows:
If a number n has a prime factorisation:
Then the total number of factors of n is given by:
To take an example. The number 60 has the following prime factorisation:
As you can see, the 2 is squared, but the 3 and the 5 are just to the power of 1. Therefore, 6 must have the following number of factors.
By finding all the prime factors of n/2 and (n+1) we can then apply the formula. We don’t need to worry about n/2 or (n+1) sharing any prime factors, as they are coprime. (any two adjacent numbers are coprime). By applying the formula we know if we have reached the 500 factor minimum threshold. If not, we need to look at a different number.
Method:
1) Enter your starting value. I decided to play it safe and begin searching at the 500th triangular number
2) Feed the data into an iterative macro, and configure it display to the minimum number of required factors.
3) Inside the first macro, we calculate both n and (n+1). Then divide the even value by two and feed both numbers into the macro we created back in problem 5, which lists all the prime factors. (The reason for doing this is explained in the theory section above)
4) Now that we have all the prime numbers listed, we have to find the number of times each prime number appears.
5) Now, to actually implement the formula, we must add one to each of these counts (powers) and multiply them all together.
6) Finally, we must filter to see if the value was over 500, and if it is now, we must add one to the nth triangular number value.
7) Running the above as an iterative, will eventually tell you which term is the first triangular number with over 500 factors. All that’s left to do is implement the formula to find its actual value.
8) Submit your answer to the Project Euler Website!
Summary:
Combining what we previously learnt about series, as well as utilising the Divisor Function Formula, we were able to figure out which term the answer was on, before even computing the value of any triangular numbers themselves.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
This was the first one I had to go learn some math for... I like how even with the quicker problems these force you to learn the math tricks. No need to dive into too much of a detailed description though it appears as @Pilsner already has us covered.
Main Workflow
Recycled Factor Macro
I went with a more brute force solution but it ran in 7.6 seconds :D
I generated all the numbers 1 to 15k and then did a Multi-Row to get the triangle maths. I skipped the first 10k values, because they probably weren't my answer (I can't remember if there were multiple skip first x values or if I just did 10k and hoped for the best). Then I fed the triangle sums into my previously developed macro which finds all the factors of a number. It has 2 outputs - 1 shows the list of factors and the other does a distinct count of all the factors - that's the one that I used here. Then I just filtered for where the Count > 500 and found the lowest.
Team Brute Force
Nicely done, @Pilsner! The coprime component of this problem is a very useful insight. I utilized the same fact, but via... String Coding! I optimized my factorizing Generate Rows code
As was mentioned in the OP, I could have added another formula tool to half the even values prior to Searching for Factors, but this workflow processes 15,000 records in 1.4 seconds, which wouldn't change much at all, and I wanted to shave off a tool.
Still loving going through these problems!
I solved it with a brute-force approach.
