# How would you approach this?

• October 9th, 2011, 11:08 PM
Staticity
How would you approach this?
So, I just finished Problem 28 on Project Euler (Please click on this to see the problem).. And I am quite proud of my algorithm! But, I'm curious about how yal would approach this problem!! Just comment with your step by step logic.

I'll gladly post my algorithm after seeing some of yal's approaches :D
• October 10th, 2011, 12:00 AM
helloworld922
Re: How would you approach this?
Mathematical formulas for computing the value at each diagonal:

n^2-x*(n-1), where n is the width of the sub-spiral and x is which diagonal (0 is top-left, going counter-clock wise).

Simply sum up all spirals from n=3:2:1001 and add on the 1 for the center.
• October 10th, 2011, 12:18 AM
Staticity
Re: How would you approach this?
Oh wow this is interesting... I bet there are several formulas like this one that I could implement into my later algorithms.. Nice HelloWorld :)

Here's my approach:
Code :

```public class prob28 { public static void main(String args[]){   double sum = 0; double inc = 2; double limit = 3;   for(int i = 1; i <= 1001*1001; i+=inc){ if(i%(limit*limit) == 0){ inc+=2; limit+=2; } sum+=i; } System.out.println(sum);   } }```

Looking at the spiral given.. You can make a few inferences:

1. The spiral will end at a square number of every odd number.. 1^2 = 1 -> 3^2 = 9 -> 5^2 = 25
2. All of the above numbers are the end of each individual perfect square..
3. Also, since the dimensions are increasing by odd numbers, the distance between each corner will increase by 2.. Here's the pattern:

Increments of 2: 1, 3, 5, 7, 9 (reach perfect odd square)
Increments of 4: 13, 17, 21, 25 (reach perfect odd square)
Increments of 6: 31, 37, ... etc.

So that's basically what my code represents! :D I thought it was pretty crafty of me
• October 10th, 2011, 01:09 AM
helloworld922
Re: How would you approach this?
Clever :) It's basically the same idea except you left it in the recurrence relationship form, and I had removed the recurrence relationships. Both equally correct and quick to compute.