Euleryx Problem 28 – Number Spiral Diagonals
My workflow:
Spoiler
Workflow:
Answer: 669171001
Last Week's Favourite Solution:
Some very different approaches last week, including very well optimised solutions using pure base A tools/functions! Although it does require an extra input, @AkimasaKajitani's solution has won last weeks favourite, as by simply generating a list of prime numbers ahead of time, the workflow was made much simpler and quicker to run! Please find both solutions on page one of last week's post or click here.
Mathematical Theory:
This challenge revolves around summing a sequence of numbers. Back in Problem 6, we have already visited some formulas to help with this, assuming we already have a general formula. The difficulty with this challenge, is that we don’t even begin with that. So, step one for this challenge is to see if we can figure out a formula to find the total value per “layer” of the spiral.
Looking at the “top right” value on each layer, you may notice that they are square numbers, in fact, they for the sequence of all odd numbers squared (1, 9, 25, 49, 81 ….). Because the first layer of the spiral, doesn’t really form a grid, as it only contains the single digit 1, I’m going to ignore it for now, as its easy enough to add back on at the end. This leaves the sequence as (9, 25, 49, 81….). As odd numbers can be denoted as (2n+1), the formula for the nth term of this sequence is:
Now, on each layer, we are so far only considering the top right corner. But now that we know this, we can calculate the others. If we are on layer n (where the 3x3 grid is layer 1), the top left corner can be calculated by doing
Continuing round anti-clockwise, the other two corners are
This means that on each layer, the 4 corners add up to:
Now that we have a formula to calculate the total on each layer, we can implement some of the formulas form Project 6.
At the moment this isn’t very easy operate on, so let’s look at rearranging this expression.
Using the formulas form Project 6 (and adding the 1 back in, from the inner most layer):
All that remains is to figure out the value of n. As mentioned, n in this case, is being treated as the number of layers (starting with the 3 x 3 as layer 1). Considering each layer get wider by 2 digits, we know the number of layers is:
Yes some of these formulas could be simplified further but they are now in a form which we can input directly into a formula tool.
Method:
1) This was another challenge which could be handled via a simgle formula tool, if the initial pattern was identified & generalised. With this in mind, all that’s required for the input data is the grid dimensions.
2) By updating N to represent the number of “layers” as oppse to the dimensions, then implementing the formulas derived above, we can sum the values to arrive at the answer!
3 Submit your answer to the Project Euler Website!
Summary:
The solution above required a few key steps. Firstly we had to spot the pattern and create a formula, to calculate the total on a given layer. Once we had these formulas, the problem became easier as it was a case of using what we had previously visited, regarding series, then rearranging the equations.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
