Determine position of number in a grid of numbers centered around 0 and increasing in spiral

math

Solution

First we need to determine which cycle (distance from center) and sector (north, east, south or west) we are in. Then we can determine the exact position of the number.

The first numbers in each cycle is as follows: `1, 9, 25`

This is a quadratic sequence: `first(n) = (2n-1)^2 = 4n^2 - 4n + 1`

The inverse of this is the cycle-number: `cycle(i) = floor((sqrt(i) + 1) / 2)`

The length of a cycle is: `length(n) = first(n+1) - first(n) = 8n`

The sector will then be: `sector(i) = floor(4 * (i - first(cycle(i))) / length(cycle(i)))`

Finally, to get the position, we need to extrapolate from the position of the first number in the cycle and sector.

To put it all together:

def first(cycle):
    x = 2 * cycle - 1
    return x * x

def cycle(index):
    return (isqrt(index) + 1)//2

def length(cycle):
    return 8 * cycle

def sector(index):
    c = cycle(index)
    offset = index - first(c)
    n = length(c)
    return 4 * offset / n

def position(index):
    c = cycle(index)
    s = sector(index)
    offset = index - first(c) - s * length(c) // 4
    if s == 0: #north
        return -c, -c + offset + 1
    if s == 1: #east
        return -c + offset + 1, c
    if s == 2: #south
        return c, c - offset - 1
    # else, west
    return c - offset - 1, -c

def isqrt(x):
    """Calculates the integer square root of a number"""
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

Example:

>>> position(9)
(-2, -1)
>>> position(4)
(1, 1)
>>> position(123456)
(-176, 80)

Problem

I've got the following grid of numbers centered around 0 and increasing in spiral. I need an algorithm which would receive number in spiral and return x; y - numbers of moves how to get to that number from 0. For example for number 9 it would return -2; -1. For 4 it would be 1; 1. ``` 25|26|... etc. 24| 9|10|11|12 23| 8| 1| 2|13 22| 7| 0| 3|14 21| 6| 5| 4|15 20|19|18|17|16 ``` This spiral can be slightly changed if it would help the algorithm to be better. Use whatever language you like. I would really appreciate mathematical explanation. Thank you.

Original source