Wir können die natürlichen Zahlen in einer rechteckigen Spirale aufrollen:

 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

Aber jetzt, wo wir sie auf einem rechteckigen Gitter haben, können wir die Spirale in einer anderen Reihenfolge abwickeln, z. B. im Uhrzeigersinn, beginnend in Richtung Norden:

 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

Die resultierende Sequenz ist eindeutig eine Permutation der natürlichen Zahlen:

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

Ihre Aufgabe ist es, diese Sequenz zu berechnen. ( OEIS A020703 , aber Spoiler-Warnung: Es enthält eine weitere interessante Definition und mehrere Formeln, die Sie vielleicht selbst herausfinden möchten.)

Tolle Tatsache: Alle 8 möglichen Abwicklungsaufträge haben einen eigenen OEIS-Eintrag.

Die Herausforderung

Bei einer positiven Ganzzahl ngeben Sie das nth-Element der obigen Sequenz zurück.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Es gelten die Standardregeln für Code-Golf .

Testfälle

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

Eine vollständige Liste bis einschließlich finden n = 11131 Sie in der B-Datei zu OEIS .

Jelly, 11 bis 10 Bytes

’ƽð²+ḷ‘Ḥ_

Noch eine Gelee-Antwort auf meinem Handy.

’ƽð²+ḷ‘Ḥ_   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.

Probieren Sie es hier aus .

Japt, 20 - 19 - 16 Bytes

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

Online testen!

Basierend auf der Beobachtung, dass

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

Oder vielmehr das

F (N) = das erste Quadrat größer oder gleich N minus seiner Quadratwurzel minus N plus 2.

Ich weiß nicht, ob sich diese Erklärung auf der OEIS-Seite befindet, da ich sie noch nicht angeschaut habe.

Julia, 28 Bytes

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

Dies ist eine Lambda-Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Wir definieren m als die größte ganze Zahl, so dass m ² ≤ n –1 ist, dh die ganze Quadratwurzel von n –1 ( isqrt). Wir können dann den OEIS-Ausdruck 2 ( m + 1) m - n + 2 auf einfach 2 ( m ² + m + 1) - n vereinfachen .

Probieren Sie es online aus

CJam, 14 Bytes

qi_(mQ7Ybb2*\-

Mit Alex 'Ansatz: 2*(m^2+m+1)-nwo m = isqrt(n-1).

ES7, 31 28 26 Bytes

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

Ich hatte Alex 'Formel unabhängig entdeckt, kann sie aber nicht beweisen, weil ich zu diesem Zeitpunkt nicht in der Nähe eines Computers war.

Bearbeiten: 3 Bytes zum Teil dank @ETHproductions gespeichert. Weitere 2 Bytes gespeichert.

Pyth, 21 Bytes

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

Probieren Sie es online!

Es ist nichts Besonderes los. Gleiche Methode wie in der JAPT-Antwort.

MATL , 16 13 Bytes

qX^Y[tQ*Q2*G-

Basierend auf Lynns CJam-Antwort .

Probieren Sie es online! (Y[wurde ersetzt durchknach Änderungen in der Sprache)

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

Dies verwendet einen anderen Ansatz als andere Antworten ( 16 Bytes ):

6Y3iQG2\+YLt!G=)

Die beiden Spiralmatrizen werden explizit generiert (tatsächlich vertikal gespiegelte Versionen davon, dies hat jedoch keine Auswirkungen auf die Ausgabe). Der erste ist

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

und der zweite verfolgt den modifizierten Pfad:

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

Um die n-te Nummer der Sequenz zu finden, genügt es, nin der zweiten Matrix zu suchen und die entsprechende Nummer in der ersten auszuwählen. Die Matrizen müssen groß genug sein, damit sie nangezeigt werden, und sollten eine ungerade Größe haben, damit der Ursprung (die Zahl 1) in beiden Fällen an derselben Position liegt.

Probieren Sie es auch online aus ! (6Y3wurde aufgrund von Sprachänderungen verschoben)

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-?=.

Dies verwendet die gleiche Technik wie so ziemlich alle anderen Antworten.

Erläuterung

-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

Eine halbwegs interessante Tatsache zu dieser Antwort ist, dass die Verwendung einfacher und kürzer ist =als Klammern.