# 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 `n`th 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.

-

# Jelly, 11 10 bytes

``````’Æ½ð²+ḷ‘Ḥ_
``````

Another Jelly answer on my phone.

``````’Æ½ð²+ḷ‘Ḥ_   A monadic hook:
’Æ½          Helper link. Input: n
’             n-1
Æ½            Atop integer square root. Call this m.
ð         Start a new dyadic link. Inputs: m, n
²+ḷ‘Ḥ_    Main link:
²+ḷ       Square m, add it to itself,
‘      and add one.
Ḥ     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 at 20:26
Learn APL or J first. Chains are actually easier than trains because the functions all have fixed arity. – lirtosiast Feb 2 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 at 20:30
How the hell did you type that on your phone!? That's more impressive than the code itself is! – Dr Green Eggs and Iron Man Feb 3 at 3:55

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

-

# 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. – ETHproductions Feb 3 at 0:28
@ETHproductions Thanks, I was wondering to myself how to get that `--n` in there... – Neil Feb 3 at 0:53
@ETHproductions Heh, I managed to shave 2 bytes from your answer. – Neil Feb 3 at 1:03

# Pyth, 21 bytes

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

Try it online!

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

-

# MATL, 13 16 bytes

``````qX^Y[tQ*Q2*G-
``````

Based on Lynn's CJam answer.

Try it online!

``````q       % input n. Subtract 1
X^      % square root
Y[      % floor
tQ      % duplicate and add 1
*       % multiply
Q       % add 1
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      % '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
``````
-

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

-