Problem Twenty Eight

4 Dec

Here’s problem twenty eight:

Question: What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral?

My initial solution to this problem was quite different from my final one. I intended to make the spiral into a one-dimensional list, and since the diagonal digits occur at a regular rate, a couple of counters could keep track of which position was actually on a diagonal. This was slightly more complicated than I foresaw, but it did succeed in the end, albeit very messily. Looking through the answer forums, I discovered another way of approaching this problem. The spiral could be seen as concentric squares, and all that was needed was to find the corners of each square.

Take a look:

result = 1
for i in range(3, 1002, 2):
	result += (i*i) + (i*i-i+1) + (i*i-2*i+2) + (i*i-3*i+3) 

I think you’ll agree that this is rather succinct (perhaps not the result += line, but I did not combine the expressions algebraically for sake of clarity). Viewing the spiral as a bunch of concentric squares, the dimensions are 1×1, 3×3, 5×5 … 1001×1001. It is unnecessary to calculate the value of the center of the square, which is why the for loop starts with (a square of length) 3 and result is initialized to 1. It is incremented by two, and you can see why by looking at the dimensions of the squares.

Now we have to find the values of the corners of a square with dimensions ixi. It’s important to note that the square is still technically constructed from a spiral; the numbers start from the center and spiral outward; they do not start on the border of the square. If the square is constructed in this manner, then we know somewhat intuitively that the top right corner is simply i2, or i*i. The top left corner’s equation was pretty much found by guess and check. The bottom two corners were slightly harder to find just by looking at the pattern of numbers, so I resorted to using the ever-handy regression function on my TI-84. These two equations were found to be i2-2i+2 and i2-3i+3, respectively. We add all of these corners into the result variable, and print at the end.

Answer: 669171001


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: