Public Group

# Euler 28

This topic is 2867 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Problem # 28 . By using some linear algebra, i came up with some equations that
supposedly maps onto the diagonals of those spiral. The equations I came up with
are these :
4*(n*n) - 6*n + 3; //TL   [maps i = 1....n] -> [1 7 21 ...]4*(n*n) - 4*n + 1; //TR   [maps i = 1....n] -> [1 9 25 ...]4*(n*n) - 10*n + 7; //BR  [maps i = 1....n] -> [1 3 13 ...]4*(n*n) - 8*n + 5; //RL   [maps i = 1....n] -> [1 5 17 ...]

I have a feeling that those function might be off by a little, but am not sure.

So using those function, i got the correct answer for the example shown in the
euler #28 website. This is the code I used :
#include <iostream>//top left equation : 4n^2 - 6n + 3//top right equation: 4n^2 - 4n + 1//bottom right equation : 4n^2 - 10n + 7//bottom left equation :  4n^2 - 8n + 5using namespace std;int main(){		const int SQUARE_SIZE = 5;		//from observing, to me it seems like this is the equation for the number of diagnols	const int DIAGONAL_SIZE = SQUARE_SIZE - 2; 		size_t totalSum = 1; //all share the same value starting	//the function starts at i = 1, but since they all map to the same	//beginning value of 1, thus n starts at 2, otherwise there would be	//three extra value addded	for(int n = 2; n <= DIAGONAL_SIZE; ++n){		totalSum += 4*(n*n) - 6*n + 3; //TL		totalSum += 4*(n*n) - 4*n + 1; //TR		totalSum += 4*(n*n) - 10*n + 7; //BR		totalSum += 4*(n*n) - 8*n + 5; //RL	}	cout << "Total Sum =  " << totalSum << endl;	return 0;}

Can anyone double check my function because it did not give me the correct

[EDIT] just realized that I could have combined those 4 equations to produce 1 equation, 16*(n*n) - 28*n + 16;
[/EDIT]

##### Share on other sites
I was pretty close to that problem (I'm at 25), so I thought I'd do it too.

However, after working on it for an hour or two, I figured a way to not use a loop! It required quite some time to work this out, but without a loop it's really a very simple algorithm! It's thus O(1) and not O(n) like yours.

This is the code:
#include <iostream>int main(){    unsigned int size = 1001; // odd    unsigned int radius = (size - 1) / 2; // the example is radius 2    unsigned int sum = ((16 * radius * radius * radius) + (30 * radius * radius) + (26 * radius) + 3) / 3;    std::cerr << "Sum of " << size << "x" << size << " spiral is " << sum << "\n";    return 0;}

To give you a bit of a hint; the following radius' give these sums:
0 => 1
1 => 1 + 4*1 + (2 + 4 + 6 + 8) = 1 + 4 + 20 = 25
2 => 1 + 2*((4*1) + (2 + 4 + 6 + 8)) + (10 + 12 + 14 + 16) = 1 + 2*4 + 3*20 + 4*8 = 101
3 => 1 + 3*((4*1) + (2 + 4 + 6 + 8)) + 2*(10 + 12 + 14 + 16) + (18 + 20 + 22 + 24) = 1 + 3*4 + 6*20 + 16*8 = 261
4 => 1 + 4*4 + 10*20 + 40*8 = 537
5 => 1 + 5*4 + 15*20 + 80*8 = 961

You need to track the above with pen and paper and see why it's like that. Then what you do next is writing the coefficients of 4, 20 and 8 in terms of the radius. This appears to be:

When you work that out, you get the formula in my source.
This is really fun! ;)

PS: there is of course also other ways to get to that formula. For example, the top-right diagonal consists of squares (1, 9, 25, 49, 81) of odd numbers (1, 3, 5, 7, 9). If you find the correlation between the radius and the sum of each of the diagonals, you can add them together and find the same formula.

• 16
• 13
• 23
• 10
• 19