General Discussions
Discuss any topics that are not product-specific here.
With this one being perhaps my favourite problem yet, I had to solve it twice! Feel free to download my solution and take a look, or read below to see my mathematical approach to the problem.
Euleryx Problem 6 - Sum Square Difference
My workflows and answer:
Answer: 25164150
Last Weeks Favourite Solution:
After another prime number related challenge last week there was such a range of approaches. With a 3 tool solution that managed to take advantage of both the message tool, and "Cancel Running Workflow on Error" Runtime setting, our favourite solution was by @AkimasaKajitani. Having never seen the message tool used in such a practical manner, we had to cast a spotlight on this solution. Find it on page one of last weeks post, or click here.
Definitions:
On the face of it this problem doesn’t seem to be complicated; however, depending on your route to a solution, there are some key concepts we must first introduce.
- Square: A number multiplied by itself
- Sequence: A list of numbers arranged in a specific order, typically defined by a rule or formula.
- Series: A series is the sum of the terms in a sequence.
- General term: (sometimes called the nth term) is a formula that allows you to compute any term in a sequence, based solely on its position. (i.e. if your sequence is even numbers, 2, 4, 6 …. The general term would 2n, therefore to find the 20th term, you would set n = 20, then calculate 2 * 20. Hence the 20th term = 40)
Mathematical Theory:
Let's begin by taking a look at a series. As mentioned above, a series is the sum of the terms in a sequence. This can be expressed mathematically by defining the following values:
- Index (term value): k
- Ending value: n
- General term:
, (think of it like a function, just like you might have y = 2x + 1 as a function,
The formula then looks something like this:
Which simply reads, sum all the terms in your sequence, beginning at 0 and ending at n.
To give an example, lets look at one of the simplest cases, called the Arithmetic Series. The sequence here is simply 1, 2, 3, 4, 5….., n. There for the general term is simply expressed as 
If you were asked to calculate the sum of the first 5 terms of this sequence, you could write:
Therefore, we get the answer, 15. But what if you were asked to find the sum of the first 100 or even 1000 terms? That’s where the trick to this problem comes in. Some series have special formulas to help us find this sum quickly. Here are some useful examples:
Arithmetic series:
Quadratic series (square numbers):
But do these actually work?
Well, we can check the equation for the Arithmetic series, by using the same example as earlier.
Which is the same answer as we got before!
Whilst I won't cover the proofs in this post, if you're interested, I encourage you to explore the series further. There is a brief description provided by Project Euler upon submission of a correct answer.
Method:
Using what we have just learnt, the method for this week's problem actually becomes incredibly simple: so simple, it can pretty much be achieved in a single formula tool.
- Enter the value we want to sum up to. In this case, 100 (as specified by the question).
- Enter the formula we have just learnt into the formula tool, I,e:
Sum of Squares:
Square of Sum:
- Subtract the sum of squares from the squared sum to reveal your answer.
- Submit your answer to the Project Euler Website!
Summary:
Whilst the brute force method here is still relatively quick, by applying some mathematical theory surrounding series, we have been able to get an answer in just one tool, and one row of data!
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
As promised on Project 1, hopefully, the one tool solution makes more sense now. If it's still a little unclear, please let me explain.
Recap: Project 1 asked us to find the sum of all multiples of 3 and 5, below 1000.
1) As @gawa pointed out, we can apply De Morgan's Law here, which explains that we can write this problem as follows:
Sum(Multiples of 3) + Sum(Multiples of 5) - Sum (Multiples of 15) = Sum (Multiples of 3 or 5)
2) Using the Arithmetic Series discussed above, this can be rewritten as follows:
3) By taking the coefficients (numbers 3, 5 and 15) outside of the sum, this can be rewritten again, as follows: (note I used Floor(999/5) = 199 and Floor(999/15) = 66, as we only deal with whole numbers)
4) Finally, implementing the Arithmetic Series formula we have just learnt, we get the following:
(3 * ((1/2) * 333 * (333 + 1))) + (5 * ((1/2) * 199 * (199 + 1))) - (15 * ((1/2) * 66 * (66 + 1)))
