# Spiral Permutation Sequence

We can roll up the natural numbers in a rectangular spiral:

 17--16--15--14--13
|               |
18   5---4---3  12
|   |       |   |
19   6   1---2  11
|   |           |
20   7---8---9--10
|
21--22--23--24--25


But now that we have them on a rectangular grid we can unwind the spiral in a different order, e.g. going clockwise, starting north:

 17  16--15--14--13
|   |           |
18   5   4---3  12
|   |   |   |   |
19   6   1   2  11
|   |       |   |
20   7---8---9  10
|               |
21--22--23--24--25


The resulting sequence is clearly a permutation of the natural numbers:

1, 4, 3, 2, 9, 8, 7, 6, 5, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, 22, 21, 20, 19, 18, 17, ...


Your task is to compute this sequence. (OEIS A020703, but spoiler warning: it contains another interesting definition and several formulae that you might want to figure out yourself.)

Fun fact: all 8 possible unwinding orders have their own OEIS entry.

## The Challenge

Given a positive integer n, return the nth element of the above sequence.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Standard rules apply.

## Test Cases

1       1
2       4
3       3
4       2
5       9
6       8
7       7
8       6
9       5
100     82
111     111
633     669
1000    986
5000    4942
9802    10000
10000   9802


For a complete list up to and including n = 11131 see the b-file on OEIS.

# Japt, 2019 16 bytes

V=U¬c)²-V *2-U+2


Test it online!

Based on the observation that

F(N) = ceil(N^.5) * (ceil(N^.5)-1) - N + 2

Or, rather, that

F(N) = the first square greater than or equal to N, minus its square root, minus N, plus 2.

I don't know if this explanation is on the OEIS page, as I haven't looked at it yet.

# Jelly, 11 10 bytes

’Æ½ð²+ḷ‘Ḥ_


Another Jelly answer on my phone.

’Æ½ð²+ḷ‘Ḥ_   A monadic hook:
’             n-1
Æ½            Atop integer square root. Call this m.
²+ḷ       Square m, add it to itself,
Ḥ     Double the result
_    and subtract n.


Try it here.

• Any tips on getting started with Jelly? I can't tell how the forks/hooks get parsed at all.
– Lynn
Feb 2, 2016 at 20:26
• Learn APL or J first. Chains are actually easier than trains because the functions all have fixed arity. Feb 2, 2016 at 20:30
• I see. Yeah, I have J experience. I suppose I will try to read jelly.py and figure out which chains are supported.
– Lynn
Feb 2, 2016 at 20:30
• How the hell did you type that on your phone!? That's more impressive than the code itself is! Feb 3, 2016 at 3:55

# Julia, 28 bytes

n->2((m=isqrt(n-1))^2+m+1)-n


This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

We define m to be the largest integer such that m2n-1, i.e. the integer square root of n-1 (isqrt). We can then simplify the OEIS expression 2 (m + 1) m - n + 2 down to simply 2 (m2 + m + 1) - n.

Try it online

# CJam, 14 bytes

qi_(mQ7Ybb2*\-


Using Alex's approach: 2*(m^2+m+1)-n where m = isqrt(n-1).

## ES7, 3128 26 bytes

n=>(m=--n**.5|0)*++m*2-~-n


I had independently discovered Alex's formula but I can't prove it because I wasn't near a computer at the time.

Edit: Saved 3 bytes partly thanks to @ETHproductions. Saved a further 2 bytes.

• n=>((m=--n**.5|0)+m*m)*2-n+1 would work, I think. Feb 3, 2016 at 0:28
• @ETHproductions Thanks, I was wondering to myself how to get that --n in there...
– Neil
Feb 3, 2016 at 0:53
• @ETHproductions Heh, I managed to shave 2 bytes from your answer.
– Neil
Feb 3, 2016 at 1:03

# APL (Dyalog Extended), 2519 14 bytes

{2⊥⍨3⍴⌊√⍵-1}-⊢


-5 bytes from Bubbler.

Try it online!

A direct implementation of the last function mentioned on the OEIS page:

$$\a(n)=2×\Big(\big\lfloor\sqrt{n-1}\big\rfloor+1\Big)×\big\lfloor\sqrt{n-1}\big\rfloor-n+2\$$

## Explanation:

{(2-⍵)+2×(1+⌊√⍵-1)×⌊√⍵-1} ⍵ → n
⌊√⍵-1  floor of root of n-1
(1+⌊√⍵-1)×       times 1 + floor of root of n-1
2×                 times 2
(2-⍵)                    plus 2-n


Try it online!

• If you remove the redundant parentheses (remember APL's long right-scope, a.k.a. "right-to-left" rule), you may find that you've not translated the formula right.
Sep 8, 2020 at 9:50
• yup, it was wrong. I think this solution works correctly. Thanks for telling me. Sep 8, 2020 at 10:28
• 19: {2-⍵-2×1(+×⊢)⌊√⍵-1}
Sep 8, 2020 at 10:34
• I think {2⊥⍨3⍴⌊√⍵-1}-⊢ should work? Sep 8, 2020 at 10:41
• Yup it does. Try it online! Sep 8, 2020 at 10:43

# Pyth, 21 bytes

K2-h+^.E@QKK^t.E@QKKQ


Try it online!

Nothing fancy going on. Same method as in the JAPT answer.

# Brachylog, 20 bytes

-1$r$[I*I+I+1=*2-?=.


This uses the same technique as pretty much all other answers.

### Explanation

-1                   § Build the expression Input - 1
$r § Square root of Input - 1$[I              § Unify I with the floor of this square root
*I+I+1        § Build the expression I * I + I + 1
=*2-?   § Evaluate the previous expression (say, M) and build the expression
§ M * 2 - Input
=. § Unify the output with the evaluation of M * 2 - Input


A midly interesting fact about this answer is that it is easier and shorter to use = rather than parentheses.

# MATL, 16 13 bytes

qX^Y[tQ*Q2*G-


Try it online! (Y[ has been replaced by k according to changes in the language)

q       % input n. Subtract 1
X^      % square root
Y[      % floor
tQ      % duplicate and add 1
*       % multiply
2*      % multiply by 2
G-      % subtract n


This uses a different approach than other answers (16 bytes):

6Y3iQG2\+YLt!G=)


It explicitly generates the two spiral matrices (actually, vertically flipped versions of them, but that doesn't affect the output). The first one is

17    16    15    14    13
18     5     4     3    12
19     6     1     2    11
20     7     8     9    10
21    22    23    24    25


and the second one traces the modified path:

25    10    11    12    13
24     9     2     3    14
23     8     1     4    15
22     7     6     5    16
21    20    19    18    17


To find the n-th number of the sequence it suffices to find n in the second matrix and pick the corresponding number in the first. The matrices need to be big enough so that n appears, and should have odd size so that the origin (number 1) is in the same position in both.

Try it online too! (6Y3 has been moved according to changes in the language)

6Y3      % 'spiral' string
i        % input n
QG2\+    % round up to an odd number large enough
YL       % generate spiral matrix of that size: first matrix
t!       % duplicate and transpose: second matrix
G=       % logical index that locates n in the second matrix
)        % use that index into first matrix