Euler 28

[CMinus]

I am trying to solve Project Euler Problem No.28
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

I have made a better Algorithm For Summing without generating the Spiral
My Code is here

#include<iostream>

using namespace std;

int main ()
{
	long sum=1;
	int multiplier =0;
	int addition=1;
	for (int col=0;col<500;col++)
	{
		multiplier++;
	for (int times = 0;times<4;times++)
		
	{
		
		
		addition += 2*multiplier;
	    
		sum+=addition;
		}
	
	}
	cout<<sum;
	getchar();
	return 0;
}

This Code works perfectly !

[Gaminic]

For one thing, you probably should avoid having globals and locals with the same name (see 'x' and 'y' variables).

Secondly, I see things like [x+1] (up) and y[+1] (right). Given the problem that "it works until 73*73", I'm guessing you're going one step too far.

(P.S. there's a better way to do this than generating the entire sequence!)

[ne555]

My algorithm is to go Down While The left column elements != 0
Go left While The upper row elements !=0 & etc...

Ad infinitum.

[CMinus]

I have made a better Algorithm For Summing without generating the Spiral

#include<iostream>

using namespace std;

int main ()
{
	long sum=1;
	int multiplier =0;
	int addition=1;
	for (int col=0;col<500;col++)
	{
		multiplier++;
	for (int times = 0;times<4;times++)
		
	{
		
		
		addition += 2*multiplier;
	    
		sum+=addition;
		}
	
	}
	cout<<sum;
	getchar();
	return 0;
}

If any one wants to check it
@ne55 It's not infinitum there is If Structure to stop it !!

[Gaminic]

@ne55 It's not infinitum there is If Structure to stop it !!

Where?

[CMinus]

if (spiral[xsize-1][0]==0)
	down();

If this Is Not True It Will stop !!
Whatever The Another Solution is much better !!
@Gaminic Thanks for Ur Answer!

[eklavya sharma 2]

The best way to solve this question is math

57      58      59      60      61      62      63      64      65

56      31      32      33      34      35      36      37      66

55      30      13      14      15      16      17      38      67

54      29      12       3       4       5      18      39      68

53      28      11       2       1       6      19      40      69

52      27      10       9       8       7      20      41      70

51      26      25      24      23      22      21      42      71

50      49      48      47      46      45      44      43      72

81      80      79      78      77      76      75      74      73

You will notice that numbers from the center to the lower-left corner are odd perfect squares
They have the general formula (2n-1)² (taking the center to be at index 1)

Write numbers from the center to any corner in a line:
Example, upper left corner
1 3 13 31 57
Take their differences
2 10 18 26
Again take differences
8 8 8

The differences come out to be constant.
Hence it is a series where differences of successive terms are in Arithmetic Progression

Let the general term be f(n)=an²+bn+c
f(1)=a+b+c
f(2)=4a+2b+c
f(3)=9a+3b+c

Solve the 3 equations to get
a=4, b=-10, c=7

Hence, general term is 4n²-10n+7

To obtain the sum of the numbers, summate the series
(ie. replace n² by n(n+1)(2n+1)/6, n by n(n+1)/2, and multiply constant term by n)
(ans: n(4n²-9n+8)/3)

Similarly find other sums
upper-right: n(4n²-6n+5)/3
lower-right: n(4n²-3n+2)/3
lower-left: n(2n-1)(2n+1)/3

Add them and subtract 3 to get

(16n³-18n²+14n-9)/3

For the pattern given above, substitute n=5 to get the sum as 537
If n=3, sum=101

So you have a simple formula in which you can put values. No need for a lengthy program!