Duncan's blog

February 1, 2009

Project Euler problem 28

Filed under: Coldfusion,Project Euler — duncan @ 7:37 pm
Tags: , , ,

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

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

There’s various ways to look at this problem. One thing I noticed was that, in the example above, the numbers we’re adding go:
1,
3, 5, 7, 9,
13, 17, 21, 25

So, excluding the 1 in the centre, we have four numbers that increment by 2, then four numbers that increment by 4. If we made the spiral wider, the next set of four numbers would increment by 6, and so on. I used that observation as the basis for this CFML:

<cfset total = 1>
<cfset runningtotal = 1>

<cfset length = 1001>

<cfloop index="i" from="2" to="#(length-1)#" step="2">
	<cfloop index="j" from="1" to="4">
		<cfset runningtotal = runningtotal + i>

		<cfset total = total + runningtotal>
	</cfloop>
</cfloop>

<cfoutput>#total#</cfoutput>

I’m using two variables here, one is our grand total. The other is a running total. So on each iteration of the outer loop, our running total will have increased by (4 * 2), (4 * 4), (4 * 6), etc… The grand total will have all instances of running total added to it.

There’s neater ways this could have been expressed, but this was how I chose to do it; it’s simple and fast.

A word of warning: even though the problem states “What is the sum of both diagonals“, that’s not really the solution they’re looking for. If you were to add up the two diagonals in the example above, you’d have:
Diagonal 1: 21 + 7 + 1 + 3 + 13 = 45
Diagonal 2: 17 + 5 + 1 + 9 + 25 = 57
Adding those two values would give you 102, not 101. This is because you’d have added 1 twice. What the problem really wants here is the sum of all the unique values of both diagonals.

Advertisements

5 Comments »

  1. The sum is also given by a formula : for a n by n spiral, S = (4*n^3+3*n^2+8*n-9)/6.

    Comment by ggse — July 15, 2009 @ 10:57 am | Reply

  2. […] problem has some similarities to problem 28. In that case the spiral went clockwise; this one it goes anti-clockwise. For our purposes […]

    Pingback by Project Euler problem 58 « Duncan’s blog — December 13, 2009 @ 9:08 am | Reply

  3. This 3 years after the last post so I don’t know if any one is following this. With to above formula, I now have two ways to come up with the same answer that gets rejected. Please allow me to post both python programs.

    S=1
    for i in range(3,10002,2):
    t=i*i
    t2 = t-(i-1)
    t3 = t2-(i-1)
    t4 = t3-(i-1)
    S = S+t+t2+t3+t4

    print S

    # and
    n=10001
    S = (4*n**3+3*n**2+8*n-9)/6
    print S
    ###########

    And the answer I get is: 666916710001

    Any Ideas?

    Comment by Daniel Robert Webb — April 24, 2012 @ 3:16 am | Reply

  4. […] previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler: problem 28 (PHP) | Duncan's blog — October 7, 2014 @ 8:00 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: