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 code-golf 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.