This post is going to be a pretty short one. Now that I have tasted blood again, I managed to “solve” another Project Euler problem just before hitting the hay last night. I’m still working on the supposed to be easy ones though.

I put “solved” in quotation marks due to the massive sledgehammer which I used for arriving at the solution…a simple for-loop. Does 1 satisfy the given definition? What about 2? And 3? Bang! Bang! Bang!

Using a dumb loop was the first thought that occurred to me on how I could solve this challenge and I didn’t get any smarter in the end.

I started by consulting Wolfram MathWorld to find out more about this numerical phenomenon. Just to discover Narcissistic Numbers. Which is NOT the solution to this given problem.

An n-digit number that is the sum of the nth powers of its digits is called an n-narcissistic number.

Below this definition MathWorld displays a nice little table of all the numbers that satisfy this definition up to n equals 39.

That was easy. For n equals 5 the numbers I was looking for are 54748, 92727, 93084.

Unfortunately…

These are not the numbers you’re looking for.

Obi -Wan Kenobi

Or to be a bit more precise, these are not the only numbers required to reach the target sum.

After several failed attempts to submit 240559 (54748 + 92727 + 93084) I came to the conclusion that most likely I am not smarter than Project Euler and started thinking about what I was missing here.

If you read the problem description carefully, it becomes clear that your search is not limited to n-narcissistic numbers only. For example 4150 is just fine as well:

4150: 4⁵ + 1⁵ + 5⁵ + 0⁵ = 4150.

The number doesn’t have to be precisely n-digits long. I hope this helps.

Now I have to read the forum posts as usual. And then move on to the next problem on my list, Coin sums.

Last year I made the decision to blog less about Project Euler problems. Especially to stop posting full blown solutions including source code. Still, I want to share interesting challenges and my attempts at solving them.

Number 28, Number spiral diagonals, falls into the category of problems I had to study at least three times just to understand what the description actually wanted to tell me. I’m pretty sure that I’m not the only human being on this planet scratching his head after reading the following lines for the first time:

Get it? No? Let me explain. Start with the number 1 in the center and then continue clockwise with the next number, 2. Just write it next to the first number. Continue with 3 and 4.

Keep going and you will have created a 3 x 3 spiral grid.

Add even more numbers…

Done. A 5 x 5 grid of spirally arranged numbers from 1 to 25. That’s all!

Now let’s have a look at all four diagonals.

Create the sum of all highlighted numbers: 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25. The result is 101.

So far so good. But what about the sum of the diagonals of a 1001 x 1001 spiral grid? This is the actual challenge!

Warning: If you just wanted to understand the problem but prefer to figure it out all by yourself, stop reading now! No implementation details will be given, but enough information to spoil all the fun for you.

My first approach was to simply use Excel. Without any coding at all. Just to get the number and to see how big it actually is. But after approximately two dull minutes of typing numbers into a spreadsheet I threw in the towel. Trying to create such a huge spiral manually is just plain dump. Stupid me.

Then I started banging my head against the wall trying to figure out how to create such a grid programatically. Should I use a list of lists? But how to continue? Therefore back to the drawing board.

I started paying closer attention to the properties of the given 5 x 5 spiral grid. Obviously you start with the 1 in the center. This number is part of every diagonal. It will be counted only once. Therefore the solution most likely looks similar to this highly sophisticated snippet of code: int result = 1 + foo;

First, I tried to reduce the challenge to the smallest possible spiral, a 3 x 3 grid. The numbers located along the diagonals are 3, 5, 7, 9.

Back to the 5 x 5 version: 13, 17, 21, 25.

Next, I created a 7 x 7 spiral on paper. The new diagonal numbers are 31, 37, 43 and 49.

Observation 1: It doesn’t matter how big the spiral gets, for every layer only four numbers are of interest, the corner numbers that are part of the diagonal. 

Which is kind of obvious.

Observation 2: The numbers of interest follow a pattern.

3 x 3 spiral: The next relevant number is the current number + 2.
5 x 5 spiral: The next relevant number is the current number + 4.
7 x 7 spiral: The next relevant number is the current number + 6.

For every additional grid layer the gap between these numbers increases by 2 (2, 4, 6…).

But how to continue from here? That’s not enough to implement a solution yet. What happens after I complete the first 3 x 3 spiral. The last number I need to consider is 9? The first number of interest of the 5 x 5 layer is 13. For the 7 x 7 layer it will be 31.

First numbers of each layer: 3, 13, 31…
Last numbers of each layer: 9, 25, 49…

What if I combine these numbers? Because that’s what I actually need. Based on my second observation I can easily compute the missing numbers for each layer, but I need a starting point.

9 → 13: A difference of 4.
25 → 31: A differente of 6.
49 → 57: A difference of 8.
81 →  91: A difference of 10.

Observation 3: I am able to compute the first relevant number of each layer based on the last number of the previous layer. The gap between these numbers increases by 2 as well. I need to keep count of the layers though.

And this should actually be enough to implement a working solution.

Unfortunately the third observation just occurred to me while typing these lines. While playing with pen and paper I just didn’t see it. But I still solved the challenge using a fourth observation.

I added a few additional layers to my 7 x 7 spiral grid…

…with the focus on potential patterns inherited in the diagonals. Let’s have a look at the top left one: (1), 7, 21, 43, 73, 111…

And that’s what I noticed:

7 → 21: 14 (initial gap)
21 → 43: 22 (14 + 8)
43 → 73: 30 (22 + 8)
73 → 111: 38 (30 + 8)

And this pattern is true for each and every diagonal.

Observation 4: Every diagonal follows the same pattern. The first step from the 3 x 3 to the 5 x5 layer is unique for each diagonal but then the current gap is always the previous gap + 8.

And that’s the observation I used for coding my solution.

So far I didn’t have a look at the Project Euler forum. But I’m pretty sure the spiral numbers challenge holds far more secrets than I could figure out by myself.