Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I don't know exactly how to describe it, but in a programmatic way I want to spiral outward from coordinates 0,0 to infinity (for practical purposes, though really I only need to go to about +/-100,000:+/-100,000)

So if this is my grid:

[-1, 1][ 0, 1][ 1, 1][ 2, 1]
[-1, 0][ 0, 0][ 1, 0][ 2, 0]
[-1,-1][ 0,-1][ 1,-1][ 2,-1]

I want to spiral in an order sort of like:

[7][8][9][10]
[6][1][2][11]
[5][4][3][12]
etc...

Is there a formula or method of doing this?

share|improve this question
    
Possible duplicate of math.stackexchange.com/questions/42942/… –  lhf Jun 26 '12 at 1:58

2 Answers 2

up vote 2 down vote accepted

Here’s a recipe for finding the coordinates of your position after $n$ steps along the spiral.

It’s simpler to number the positions on the spiral starting at $0$: position $0$ is $\langle 0,0\rangle$, the origin, position $1$ is $\langle 1,0\rangle$, position $2$ is $\langle 1,-1\rangle$, and so on. Using $R,D,L$, and $U$ to indicate steps Right, Down, Left, and Up, respectively, we see the following pattern:

$$RD\,|LLUU\,\|\,RRRDDD\,|LLLLUUUU\,\|\,RRRRRDDDDD\,|LLLLLLUUUUUU\;\|\dots\;,$$

or with exponents to denote repetition, $R^1D^1|L^2U^2\|R^3D^3|L^4U^4\|R^5D^5|L^6U^6\|\dots\;$. I’ll call each $RDLU$ group a block; the first block is the initial $RDLLUU$, and I’ve displayed the first three full blocks above.

Clearly the first $m$ blocks comprise a total of $2\sum_{k=1}^mk=m(m+1)$ steps. It’s also not hard to see that the $k$-th block is $R^{2k+1}D^{2k+1}L^{2k+2}U^{2k+2}$, so that the net effect of the block is to move you one step up and to the left. Since the starting position after $0$ blocks is $\langle 0,0\rangle$, the starting position after $k$ full blocks is $\langle -k,k\rangle$.

Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<n\le(2k+2)(2k+3)\;;$$ at this point you’ve gone through $k$ blocks plus an additional $n-2k(2k+1)$ steps. After some straightforward but slightly tedious algebra we find that you’re at

$$\begin{cases} \langle n-4k^2-3k,k\rangle,&\text{if }2k(2k+1)<n\le(2k+1)^2\\ \langle k+1,4k^2+5k+1-n\rangle,&\text{if }(2k+1)^2<n\le 2(k+1)(2k+1)\\ \langle 4k^2+7k+3-n,-k-1\rangle,&\text{if }2(k+1)(2k+1)<n\le4(k+1)^2\\ \langle -k-1,n-4k^2-9k-5\rangle,&\text{if }4(k+1)^2<n\le2(k+1)(2k+3)\;. \end{cases}$$

To find $k$ easily, let $m=\lfloor\sqrt n\rfloor$. If $m$ is odd, $k=\frac12(m-1)$. If $m$ is even, and $n\ge m(m+1)$, then $k=\frac{m}2$; otherwise, $k=\frac{m}2-1$.

share|improve this answer
    
Yikes that is a bit more complex than I expected, hopefully I can put it to use! –  Bob Jun 26 '12 at 2:40

Here is some code that finds the $n$-th point in the spiral. Unfortunately it spirals the other way but perhaps it helps anyway.

function spiral(n)
        k=ceil((sqrt(n)-1)/2)
        t=2*k+1
        m=t^2 
        t=t-1
        if n>=m-t then return k-(m-n),-k        else m=m-t end
        if n>=m-t then return -k,-k+(m-n)       else m=m-t end
        if n>=m-t then return -k+(m-n),k else return k,k-(m-n-t) end
end

See http://upload.wikimedia.org/wikipedia/commons/1/1d/Ulam_spiral_howto_all_numbers.svg.

share|improve this answer
    
Thanks that is helpful! –  Bob Jun 26 '12 at 2:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.