Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


Is there a formula or method of doing this?

share|cite|improve this question
Possible duplicate of… – lhf Jun 26 '12 at 1:58
up vote 4 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:


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|cite|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)
        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


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

As you can see from Brian's answer, the formula for it is complex. But there is a very simple recursive algorithm you can use:

  • for each step, record both your position and your orientation
  • for n = 0, start at (0,0), facing east
  • for n = 1, the spiral is (0,0): east; (0,1): east
  • for n > 1, calculate the spiral for n-1. Look to your right.
    • if the space is occupied by a point of the spiral, take a step forward
    • if the space is free, turn right, then take a step forward

It is very easy to extend to other starting orientations, and also to create a left turning spiral. Here is a Scala implementation of the algorithm. I tried to optimize it for readability, not efficiency.

object Orientation extends Enumeration {
  val north = Value("north")
  val east = Value("east")
  val south = Value("south")
  val west = Value("west")

  val orderedValues = Vector(north, east, south, west)

  def turnRight(fromOrientation: Orientation.Value): Orientation.Value = orderedValues(
    (orderedValues.indexOf(fromOrientation) + 1) % 4)

  def turnLeft(fromOrientation: Orientation.Value): Orientation.Value = orderedValues(
    (orderedValues.indexOf(fromOrientation) +3) % 4)

  def oneStepOffset(inOrientation: Orientation.Value): (Int, Int) = inOrientation match {
    case Orientation.north => (0, 1)
    case Orientation.east => (1, 0)
    case Orientation.south => (0, -1)
    case Orientation.west => (-1, 0)

object Direction extends Enumeration {
  val straight = Value("straight")
  val right = Value("right")
  val left = Value("left")

def spiral(n: Int, initialOrientation: Orientation.Value = Orientation.east, turningDirection: Direction.Value = Direction.right): List[(Int, Int)] = {

  if (turningDirection == Direction.straight) throw new IllegalArgumentException("The spiral must turn left or right")
  if (n < 0) throw new IllegalArgumentException("The spiral only takes a positive integer as the number of steps")

  class Step(
    val position: (Int, Int),
    val orientation: Orientation.Value)

  def nextPosition(lastStep: Step, direction: Direction.Value): (Int, Int) = {
    val newOrientation = direction match {
      case Direction.straight => lastStep.orientation
      case Direction.right => Orientation.turnRight(lastStep.orientation)
      case Direction.left => Orientation.turnLeft(lastStep.orientation)

    val offset = Orientation.oneStepOffset(newOrientation)

    return (
      lastStep.position._1 + offset._1,
      lastStep.position._2 + offset._2)

  def takeStep(lastStep: Step, occupiedPositions: Seq[(Int, Int)]): Step = {
    val positionAfterTurning = nextPosition(lastStep, turningDirection)
    val nextStep = if (occupiedPositions.contains(positionAfterTurning)) {
      new Step(nextPosition(lastStep, Direction.straight), lastStep.orientation)
    } else {
      val newOrientation = turningDirection match {
        case Direction.left => Orientation.turnLeft(lastStep.orientation)
        case Direction.right => Orientation.turnRight(lastStep.orientation)
      new Step(positionAfterTurning, newOrientation)
    return nextStep

  def calculateSpiral(upTo: Int): List[Step] = upTo match {
    case 0 => new Step((0, 0), initialOrientation) :: Nil
    case 1 => new Step(Orientation.oneStepOffset(initialOrientation), initialOrientation) :: new Step((0, 0), initialOrientation) :: Nil
    case x if x > 1 => {
      val spiralUntilNow = calculateSpiral(upTo - 1)
      val nextStep = takeStep(spiralUntilNow.head, => step.position))
      (nextStep :: spiralUntilNow)

  return (calculateSpiral(n).map(step => step.position)).reverse
share|cite|improve this answer
I don't have the code handy, but this is basically what I ended up doing. By persisting a few variables it's also fairly straightforward to allow for pausing/resuming. – Bob Jan 15 '15 at 16:33

Your Answer


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.