Możemy zwinąć liczby naturalne w prostokątną 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

Ale teraz, gdy mamy je na prostokątnej siatce, możemy rozwinąć spiralę w innej kolejności, np. Idąc zgodnie z ruchem wskazówek zegara, zaczynając na północ:

 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

Wynikowa sekwencja jest wyraźnie permutacją liczb naturalnych:

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

Twoim zadaniem jest obliczenie tej sekwencji. ( OEIS A020703 , ale ostrzeżenie spoilera: zawiera kolejną ciekawą definicję i kilka formuł, które możesz chcieć samemu wymyślić).

Ciekawostka: wszystkie 8 możliwych zamówień odwijania ma własny wpis OEIS.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą n, zwróć nelement th powyższej sekwencji.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

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

Aby uzyskać pełną listę, włącznie n = 11131 z plikiem b na OEIS .

Galaretka, 11 10 bajtów

’ƽð²+ḷ‘Ḥ_

Kolejna galaretka odpowiada na mój telefon.

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

Wypróbuj tutaj .

Japt, 20 19 16 bajtów

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

Przetestuj online!

Na podstawie obserwacji, że

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

A raczej to

F (N) = pierwszy kwadrat większy lub równy N, minus jego pierwiastek kwadratowy, minus N, plus 2.

Nie wiem, czy to wyjaśnienie znajduje się na stronie OEIS, ponieważ jeszcze go nie przeglądałem.

Julia, 28 bajtów

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

Jest to funkcja lambda, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.

Definiujemy m jako największą liczbę całkowitą taką, że m ² ≤ n -1, tj. Liczba całkowita pierwiastek kwadratowy z n -1 ( isqrt). Następnie możemy uprościć wyrażenie OEIS 2 ( m + 1) m - n + 2 do po prostu 2 ( m ² + m + 1) - n .

Wypróbuj online

CJam, 14 bajtów

qi_(mQ7Ybb2*\-

Korzystanie z podejścia Alexa: 2*(m^2+m+1)-ngdzie m = isqrt(n-1).

ES7, 31 28 26 bajtów

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

Niezależnie odkryłem formułę Alexa, ale nie mogę tego udowodnić, ponieważ nie byłem wtedy w pobliżu komputera.

Edycja: Zapisano 3 bajty częściowo dzięki produktom @ETH. Zapisano kolejne 2 bajty.

Pyth, 21 bajtów

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

Wypróbuj online!

Nie dzieje się nic szczególnego. Ta sama metoda, co w odpowiedzi JAPT.

MATL , 16 13 bajtów

qX^Y[tQ*Q2*G-

Oparte na Lynn na CJam .

Wypróbuj online! (Y[został zastąpiony przezk zgodnie ze zmianami języka)

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

Wykorzystuje to inne podejście niż inne odpowiedzi ( 16 bajtów ):

6Y3iQG2\+YLt!G=)

Wyraźnie generuje dwie macierze spiralne (w rzeczywistości ich odwrócone w pionie wersje, ale to nie wpływa na wynik). Pierwszy to

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

a drugi śledzi zmodyfikowaną ścieżkę:

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

Aby znaleźć n-ty numer sekwencji, wystarczy znaleźć nw drugiej macierzy i wybrać odpowiednią liczbę w pierwszej. Matryce muszą być wystarczająco duże, aby się npojawiały i powinny mieć nieparzyste rozmiar, aby początek (liczba 1) w tym samym miejscu w obu.

Wypróbuj też online ! (6Y3został przeniesiony zgodnie ze zmianami języka)

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 bajtów

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

Wykorzystuje tę samą technikę, co prawie wszystkie inne odpowiedzi.

Wyjaśnienie

-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

Średnio interesującym faktem na temat tej odpowiedzi jest to, że łatwiej i krócej jest używać =niż nawiasów.