Spiral neighbourhoods

Question

If we take the natural numbers and roll them up counter clock-wise into a spiral we end up with the following infinite spiral:

                  ....--57--56
                             |
36--35--34--33--32--31--30  55
 |                       |   |
37  16--15--14--13--12  29  54
 |   |               |   |   |
38  17   4---3---2  11  28  53
 |   |   |       |   |   |   |
39  18   5   0---1  10  27  52
 |   |   |           |   |   |
40  19   6---7---8---9  26  51
 |   |                   |   |
41  20--21--22--23--24--25  50
 |                           |
42--43--44--45--46--47--48--49

Given some number in that spiral your task is to determine its neighbours - meaning the element above, left, right and below it.

Example

If we have a look at 27 we can see that it has the following neighbours:

• above: 28
• left: 10
• right: 52
• below: 26

So the output would be: [28,10,52,26]

Rules

• Input will be a number \$n \geq 0\$ in any default I/O format
• Output will be a list/matrix/.. of that numbers' 4 neighbours in any (consistent!) order
• You may work with a spiral that starts with 1 instead of 0, however you should specify that in your answer

Examples

The output is in the format [above,left,right,below] and uses a 0-based spiral:

0  ->  [3,5,1,7]
1  ->  [2,0,10,8]
2  ->  [13,3,11,1]
3  ->  [14,4,2,0]
6  ->  [5,19,7,21]
16  ->  [35,37,15,17]
25  ->  [26,24,50,48]
27  ->  [28,10,52,26]
73  ->  [42,72,74,112]
101  ->  [100,146,64,102]
2000  ->  [1825,1999,2001,2183]
1000000  ->  [1004003,1004005,999999,1000001]

Answer 1

R, 156 bytes

function(n){g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))
x=g(sinpi)
y=g(cospi)
a=x[n]
b=y[n]
which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))}

Try it online!

• posted another R answer since it's a slightly different approach than @ngn
• 1-indexed
• neighbours are always sorted by ascending value
• saved 6 bytes removing round and using cospi(x)/sinpi(x) which are more precise than cos(x*pi)/sin(x*pi) in case of half numbers (0.5, 1.5 etc...)
• saved another byte removing the minus on y coordinates since the result is the same (just up/down neighbours are reversed)

---

Explanation :

If we look at the matrix coordinates of the values, considering the first value 0 placed at x=0, y=0, they are :

x = [0,  1,  1,  0, -1, -1, -1,  0,  1,  2,  2,  2,  2,  1,  0, ...] 
y = [0,  0,  1,  1,  1,  0, -1, -1, -1, -1,  0,  1,  2,  2,  2, ...]

The x coordinates follow the A174344 OEIS sequence with the recursive formula :

a(1) = 0, a(n) = a(n-1) + sin(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

The same formula holds for y matrix coordinates, but with cos instead of sin and negated :

a(1) = 0, a(n) = a(n-1) - cos(mod(floor(sqrt(4*(n-2)+1)),4)*pi/2)

So, in R we can translate the formula to this function, taking sinpi/cospi as parameter :

g=function(h)c(0,cumsum(h((4*(0:(n+2)^2)+1)^.5%%4%/%1/2)))

and we generate the two coordinates vectors (we don't negate the y coords since we'll get the same result, just with up/down neighbours reversed) :

x=g(sinpi)
y=g(cospi)

Note that we have generated (n+2)^2 coordinates, which are more than the minimum necessary coordinates containing both n and their neighbours (a tighter bound would be (floor(sqrt(n))+2)^2 but unfortunately is less "golfy").

Therefore, now that we have all the coordinates, we first search the coordinates a,b corresponding to our n :

a=x[n]
b=y[n]

finally we select the positions of their neighbours, i.e. :

• the up/down neighbours where x == a and y == b+1 or b-1
• the right/left neighbours where y == b and x == a+1 or a-1

using :

which(x==a&(y==b+1|y==b-1)|y==b&(x==a+1|x==a-1))

Answer 2

Perl 6, 94 83 bytes

{my \s=0,|[+] flat((1,i...)Zxx flat(1..Inf Z 1..Inf));map {first :k,s[$_]+$^d,s},i,-1,1,-i}

{my \s=0,|[\+] flat((1,*i...*)Zxx(1,1.5...*));map {first :k,s[$_]+$^d,s},i,-1,1,-i}

Try it online!

s is a lazy, infinite list of spiral coordinates, represented as complex numbers. It's constructed from two other infinite lists: 1, *i ... * makes the list 1, i, -1, -i .... 1, 1.5 ... * makes the list 1, 1.5, 2, 2.5, 3, 3.5 .... Zipping these two lists together with list replication produces the list of steps from each spiral coordinate to the next: 1, i, -1, -1, -i, -i, 1, 1, 1, i, i, i .... (The fractional parts of the right-hand arguments to the list replication operator are discarded.) Doing a triangular addition reduction ([\+]) on this list (and pasting 0 onto the front) produces the list of spiral coordinates.

Finally, starting from the complex number s[$_] ($_ being the sole argument to the function), we look up the indexes (first :k) in the spiral of the complex numbers which are offset from that number by i, -1, 1, and -i.

Answer 3

Brain-Flak, 238 bytes

((){[()]<((({}[((()))]<>)<<>{((([{}]({}))([{}]{})())[()]){({}[()])<>}{}}>)<<>({}<(((({}{})()){}<>({}))()())<>>)<>>()())<>{{}((()()()[({})]){}<>({}<{}>))(<>)}>}{}){<>((((())()())()())()())(<>)}{}{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

Try it online!

Output is in the order left, up, right, down.

Explanation

# If n is nonzero:
((){[()]<

  ((

    # Push 1 twice, and push n-1 onto other stack.
    ({}[((()))]<>)

    # Determine how many times spiral turns up to n, and whether we are on a corner.
    # This is like the standard modulus algorithm, but the "modulus" used
    # increases as 1, 1, 2, 2, 3, 3, ...
    <<>{((([{}]({}))([{}]{})())[()]){({}[()])<>}{}}>

  # Push n-1: this is the number behind n in the spiral.
  )<

    # While maintaining the "modulus" part of the result:
    <>({}<

      # Push n+2k+1 and n+2k+3 on top of n-1, where k is 3 more than the number of turns.
      # n+2k+1 is always the number to the right in the direction travelled.
      # If we are on a corner, n+2k+3 is the number straight ahead.
      (((({}{})()){}<>({}))()())<>

    >)<>

  # Push n+1.  If we are on a corner, we now have left, front, right, and back
  # on the stack (from top to bottom)
  >()())

  # If not on a corner:
  <>{{}

    # Remove n+2k+3 from the stack entirely, and push 6-2k+(n+1) on top of the stack.
    ((()()()[({})]){}<>({}<{}>))

  (<>)}

>}{})

# If n was zero instead:
{

  # Push 1, 3, 5, 7 on right stack, and implicitly use 1 (from if/else code) as k.
  <>((((())()())()())()())

(<>)}{}

# Roll stack k times to move to an absolute reference frame
# (switching which stack we're on each time for convenience)
{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

Answer 4

MATL, 15 bytes

2+1YLtG=1Y6Z+g)

Input and output are 1-based.

The output gives the left, down, up and right neighbours in that order.

Try it online! Or verify all test cases except the last two, which time out on TIO.

2+      % Implicit input: n. Add 2. This is needed so that
        % the spiral is big enough
1YL     % Spiral with side n+2. Gives a square matrix
t       % Duplicate
G=      % Compare with n, element-wise. Gives 1 for entry containing n
1Y6     % Push 3×3 mask with 4-neighbourhood
Z+      % 2D convolution, keeping size. Gives 1 for neighbours of the
        % entry that contained n
g       % Convert to logical, to be used as an index
)       % Index into copy of the spiral. Implicit display

Answer 5

R, 172 bytes

function(x,n=2*x+3,i=cumsum(rep(rep(c(1,n,-1,-n),l=2*n-1),n-seq(2*n-1)%/%2))){F[i]=n^2-1:n^2
m=matrix(F,n,n,T)
j=which(m==x,T)
c(m[j[1],j[2]+c(-1,1)],m[j[1]+c(-1,1),j[2]])}

Try it online!

This is R, so obviously the answer is 0-indexed.

Most of the work is creating the matrix. Code inspired by: https://rosettacode.org/wiki/Spiral_matrix#R

Answer 6

JavaScript (ES6), 165 bytes

Prints the indices with alert().

f=(n,x=w=y=n+2)=>y+w&&[0,-1,0,1].map((d,i)=>(g=(x,y,A=Math.abs)=>(k=A(A(x)-A(y))+A(x)+A(y))*k+(k+x+y)*(y>=x||-1))(x+d,y+~-i%2)-n||alert(g(x,y)))|f(n,x+w?x-1:(y--,w))

Try it online!

How?

For \$x, y \in \mathbb{Z}\$, we compute the 0-based index \$I_{x,y}\$ of the spiral with:

$$A_{x,y}=||x|-|y||+|x|+|y|$$ $$S_{x,y}=\begin{cases}1,&\text{if }y\ge x\\-1,&\text{if }y<x\end{cases}$$ $$I_{x,y}=A_{x,y}^2+(A_{x,y}+x+y)\times S_{x,y}$$

(adapted from this answer from math.stackexchange)

Answer 7

Python 2, 177 164 146 144 bytes

def f(n):N=int(n**.5);S=N*N;K=S+N;F=4*N;return[n+[F+3,[-1,1-F][n>K]][n>S],n+[F+5,-1][n>K],n+[[1,3-F][n<K],-1][0<n==S],n+[F+7,1][n<K]][::1-N%2*2]

Try it online!

Calculates u,l,r,d directly from n.

Answer 8

PHP (>=5.4), 208 bytes

<?$n=$argv[1];for(;$i++<($c=ceil(sqrt($n))+($c%2?2:3))**2;$i!=$n?:$x=-$v,$i!=$n?:$y=+$h,${hv[$m&1]}+=$m&2?-1:1,$k++<$p?:$p+=$m++%2+$k=0)$r[-$v][+$h]=$i;foreach([0,1,0,-1]as$k=>$i)echo$r[$x+$i][$y+~-$k%2].' ';

To run it:

php -n -d error_reporting=0 <filename> <n>

Example:

php -n -d error_reporting=0 spiral_neighbourhoods.php 2001

Or Try it online!

Notes:

• The -d error_reporting=0 option is used to not output notices/warnings.
• This spiral starts with 1.

---

How?

I'm generating the spiral with a modified version of this answer in a 2 dimensional array.

I decide on the size of the spiral based on the input n with a formula to always get an extra round of numbers in the spiral (guarantee for existence of above/below/left/right). An extra round of numbers means +2 in height and +2 in width of the 2 dimensional array.

So if n will be located in a spiral with maximum size of 3*3, then generated spiral will be 5*5.

Spiral size is c*c where c = ceil(sqrt(n)) + k, if ceil(sqrt(n)) is odd, then k is 2 and if ceil(sqrt(n)) is even, then k is 3.

For example, the above formula will result in this:

• If n = 1 then c = 3 and spiral size will be 3*3
• If n <= 9 then c = 5 and spiral size will be 5*5
• If n <= 25 then c = 7 and spiral size will be 7*7
• If n <= 49 then c = 9 and spiral size will be 9*9
• And so on ...

While generating the spiral, I store the x and y of n and after generation, I output the elements above/below/left/right of it.