Project Euler – Problem 28

24 04 2009

I don’t have much to rant about, Linux has been behaving itself, and with finals coming most of my free time is spent on homework and studying. However, I did get around to solving a couple Euler Problems, so I thought I’d fill the awkward silence of my blog with one of them (although it’s so easy, I don’t expect anyone to be Googling for it).

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 both diagonals is 101.

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

At first glance I thought about how to generate the spiral inside an array, but after a second more of observation I decided there was no reason to. It’s fairly clear that each loop of the spiral increases the dimensions of the square by 2, meaning the corners are differing from each other by 2 more each time around the spiral. The corners then, can be found by just starting with the sum equal to 1, incrementing the current number by 2 and adding it to the sum (repeating four times), then by 4 four times, then by 6 four times.. you get the picture. Here it is thrown together in C, short and to the point.

#include 
#define SPIRAL_SIZE 1000

int main() {
	int incr, i;
	unsigned int sum = 1;
	unsigned int current_num = 1;

	for (incr = 2; incr <= SPIRAL_SIZE; incr+=2) {
		for (i = 1; i <= 4; i++) {
			current_num = current_num + incr;
			sum = sum + current_num;
		}
	}
	printf("Result: %d\n", sum);
}
Advertisements