# Spiral neighbourhoods

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]


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

• "slightly different" :) – ngm Jul 23 '18 at 13:25
• @ngm: eheh... since the rosetta code you used is pretty "obscure" to me, I assumed is somehow generating the position indexes of the matrix in a different but similar fashion than my OEIS sequences :D – digEmAll Jul 23 '18 at 14:42

# 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.

# 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)
{({}[()]<<>({}<>)<>({}<({}<({}<>)>)>)<>>)}<>

• Very impressive! I guess you're not generating the whole spiral as others do, are you? – ბიმო Jul 21 '18 at 16:30

# 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

• 1YL- MATLAB has aspiral function? When did MATLAB turn into Mathematica?! – sundar - Reinstate Monica Jul 20 '18 at 17:44
• Yeah, I duckduckgo-ed it after seeing what 1YL meant, and this Rosetta code entry was the only place I could find to confirm that it's a MATLAB thing and not just a MATL convenience function. I was starting to think it might be something you added to MATL for golfing, until I saw that entry. – sundar - Reinstate Monica Jul 20 '18 at 18:55
• @sundar Weird that it's not documented anymore – Luis Mendo Jul 20 '18 at 19:02

# 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,j+c(-1,1)],m[j+c(-1,1),j])}


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

# 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}$$

• This seems to work fine with smaller numbers, but I get an error when testing this with a large number like 2000. Error on tio.run: RangeError: Maximum call stack size exceeded and error in browser console: InternalError: too much recursion. Am I doing something wrong? – Night2 Jul 22 '18 at 12:26
• @Night2 The number of iterations grows in $4n^2$, so the call stack quickly overflows. The same kind of restriction applies to most JS recursive answers, although the exact limit depends on the platform it's running on. – Arnauld Jul 22 '18 at 12:35

# Python 2, 177164 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.

# PHP (>=5.4), 208 bytes

<?$n=$argv;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


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.