Jump to content
  • Advertisement
Sign in to follow this  
Concentrate

Euler 28

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

If you intended to correct an error in the post then please contact us.

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 + 5

using 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
answer for the main problem.

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

Share this post


Link to post
Share on other sites
Advertisement
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:

sum(radius) = 1 + radius*4 + ((radius + 1) * radius / 2)*20 + ((radius * (radius - 1) * radius / 2) - (radius * (radius - 1) * (2*radius - 1) / 6))*4*8

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!