Spiral Problem

Date: 02/03/2003 at 22:24:43
From: Steve Prsa
Subject: Spiral problem

                 4 3 2 11
                 5 0 1 10
                 6 7 8 9

Given an x,y plane, with the number zero at the center, so it has 
coordinates (0,0) [for example the number 1 has coordinates (1,0) and
     
the number 2 would have coordinates (1,1)]. I have to write a computer 
program so that when given the coordinates, I can determine the number 
that is at that point.  

Let me try to clarify the spiral:

               . . .
             4 3 2 11
             5 0 1 10
             6 7 8 9

We have a cartesian plane (x,y plane). Zero is at the origin so it 
has the point (0,0). If we take the point (1,1), the number there is 
2. If we look at the number 6 in the grid, it has point (-1,-1). The 
number 11 is the point (2,1). This spiral goes on forever.  

I hope this clarifies what I'm asking about. My question again is, if 
given the coordinates, is there a formula to find the number that 
will be at those coordinates? 

Thank you again,
Steve

Date: 02/04/2003 at 14:05:13
From: Doctor Ian
Subject: Re: Spiral problem

Hi Steve, 

Let's extend your spiral a little more:

   36 - 35 - 34 - 33 - 32 - 31 - 30
                                  |
        16 - 15 - 14 - 13 - 12   29
         |                   |    |
        17    4 -  3 -  2   11   28
         |    |         |    |    |
        18    5    0 -  1   10   27
         |    |              |    |
        19    6 -  7 -  8 -  9   26
         |                        |
        20 - 21 - 22 - 23 - 24 - 25

So there's at least one pattern: coordinates (-n,n) correspond to 
point (2n^2).  

Here's another:  coordinates (n,-(n-1)) correspond to point (2n-1)^2. 

We can think of this as building up squares:

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

Now, suppose we're thinking about coordinates (a,b). The larger 
absolute value tells us which square we're on, e.g., 

  (3,2)  is on the 3rd square, since |3| > |2|

  (-1,-2) is on the second square, since |-2| > |-1|.  

If we know which square we're _on_, we know how many squares we've 
_skipped_ to get there, right?  

So, basically, if I'm the i'th guy on the k'th square, then my number 
must be 

  [i] + [the sum of the points on the first (k-1) squares]

If you can reduce finding each term in the sum to a single line of 
code, you've got the program you're looking for. 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/