Wprowadzenie (może zostać zignorowane)

Ustawienie wszystkich dodatnich liczb całkowitych w regularnej kolejności (1, 2, 3, ...) jest trochę nudne, prawda? Oto szereg wyzwań dotyczących permutacji (przetasowań) wszystkich liczb całkowitych dodatnich. Jest to szóste wyzwanie z tej serii (linki do pierwszego , drugiego , trzeciego , czwartego i piątego wyzwania).

To wyzwanie ma łagodny motyw wielkanocny (ponieważ jest Wielkanoc). Inspirację czerpałem z tego wysoce zdobionego (i moim zdaniem dość brzydkiego) jaja gęsiego.

Przypomniało mi to spiralę Ulama , w której wszystkie dodatnie liczby całkowite są umieszczone w spirali przeciwnie do ruchu wskazówek zegara. Ta spirala ma kilka interesujących cech związanych z liczbami pierwszymi, ale nie ma to znaczenia dla tego wyzwania.

Przechodzimy do permutacji dodatnich liczb całkowitych tego wyzwania, jeśli weźmiemy liczby ze spirali Ulam i prześledzimy wszystkie liczby całkowite w spirali obracającej się zgodnie z ruchem wskazówek zegara , zaczynając od 1. W ten sposób otrzymujemy:

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

Jeśli narysujesz obie spirale, uzyskasz coś w rodzaju nieskończonej siatki spiral (skorupek jaj) ( zwróć uwagę na odnośnik do Nowego Porządku ).

$a(n)$$n$$a(n)$

Zadanie

$n$$a(n)$$a(n)$

$a(0) = 1; a(1) = 6$

Przypadki testowe

Input | Output
---------------
1     |  1
5     |  3
20    |  10
50    |  72
78    |  76
123   |  155
1234  |  1324
3000  |  2996
9999  |  9903
29890 |  29796

Zasady

• Wejścia i wyjścia są liczbami całkowitymi.
• Twój program powinien co najmniej obsługiwać dane wejściowe w zakresie od 1 do 32767).
• Nieprawidłowe dane wejściowe (0, liczby zmiennoprzecinkowe, ciągi, wartości ujemne itp.) Mogą prowadzić do nieprzewidzianych wyników, błędów lub (nie) zdefiniowanego zachowania.
• Obowiązują domyślne reguły we / wy .
• Domyślne luki są zabronione.
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach

Galaretka ,  16 14 11 10 9  8 bajtów

-1 dzięki Lynn (Mod 2, logiczny NIE, dodawanie do siebie: Ḃ¬+-> bitowe LUB 1: |1)

|1×r)ẎQi

Monadycznego link przyjmującą liczbę całkowitą n, która daje w wyniku liczbę całkowitą a(n).

$\lceil\frac n2\rceil$

½‘|1×rƲ€ẎQi$\lceil\frac{\lfloor\sqrt n\rfloor+1}2\rceil$

W jaki sposób?

Permutacja polega na przyjmowaniu liczb naturalnych w odwróconych odcinkach długości [1,5,3,11,5,17,7,23,9,29,11,35,13,...]- nieparzystych liczb całkowitych dodatnich przeplatanych dodatnimi liczbami całkowitymi przystającymi do pięciu modułów szóstych, tj [1, 2*3-1, 3, 4*3-1, 5, 6*3-1, 7, 8*3-1, 9, ...].

Jest to to samo, co konkatenacja, a następnie deduplikacja odwróconych zakresów [1..x]gdzie xskumulowane sumy długości odcinków (tj. Maksimum każdego wycinka) - [1,6,9,20,25,42,49,72,81,110,121,156,169,...]czyli nieparzyste liczby całkowite do kwadratu przeplatane liczbami parzystymi pomnożonymi przez siebie, tj [1*1, 2*3, 3*3, 4*5, 5*5, 6*7, 7*7,...].

Ponieważ różnice są większe niż 1, możemy zapisać bajt (odwrócenie), budując zakresy [x..k]bezpośrednio, gdzie kjest indeksem 1 wycinka indeksu.

$P(n) = v \iff P(v) = n$n|1×r)ẎQị@n|1×r)ẎQi

|1×r)ẎQi - Link: integer, n       e.g. 10
    )    - for each k in [1..n]:  vs = [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
|1       -   bitwise-OR (k) with 1     [ 1, 3, 3, 5, 5, 7, 7, 9, 9,11]
  ×      -   multiply (by k)           [ 1, 6, 9,20,25,42,49,72,81,110]
   r     -   inclusive range (to k)    [[1],[6..2],[9..3],[20..4],...,[110..10]]
     Ẏ   - tighten                     [1,6,5,4,3,2,9,8,7,6,5,4,3,20,...,4,......,110,...,10]
      Q  - de-duplicate                [1,6,5,4,3,2,9,8,7,20,...,10,......,110,...82]
       i - first index with value (n)  20

JavaScript (ES7),  46 45  41 bajtów

0-indeksowane.

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Wypróbuj online!

W jaki sposób?

Jest to oparte na formule 1-indeksowanej stosowanej w przykładowych programach A090861 .

$x_n$$0$

$$x_n=\left\lfloor\frac{\sqrt{n-1}+1}{2}\right\rfloor$$

Wypróbuj online!

$k_n$$6$$-2$

$$k_n=\begin{cases} -2&\text{if }n\le 4{x_n}^2+2x_n\\ 6&\text{otherwise} \end{cases}$$

Wypróbuj online!

$a_n$

$$a_n=8{x_n}^2+k_nx_n+2-n$$

Wypróbuj online!

Co można przetłumaczyć na:

n=>8*(x=(n-1)**.5+1>>1)*x+(n<=4*x*x+2*x?-2:6)*x+2-n

Dzięki indeksowi 0 można od razu zaoszczędzić 5 bajtów:

n=>8*(x=n**.5+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n

Formułę można dodatkowo uprościć, używając:

$${x'}_n=2\times\left\lfloor\frac{\sqrt{n}+1}{2}\right\rfloor$$

które można wyrazić jako:

x=n**.5+1&~1

prowadzący do:

n=>2*(x=n**.5+1&~1)*x+(n<x*x+x?-1:3)*x+1-n

i w końcu:

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Wolfram Language (Mathematica) , 60 bajtów

8(s=⌊(⌊Sqrt[#-1]⌋+1)/2⌋)^2-#+2+If[#<=4s^2+2s,-2,6]s&

Wypróbuj online!

MATL , 12 11 bajtów

Eq1YL!tPG=)

Wypróbuj online!

Bardzo nieefektywna pamięć. Poprzedzenie X^kczyni go bardziej wydajne .

C # (interaktywny kompilator Visual C #) , 67 bajtów

n=>8*(x=(int)Math.Sqrt(--n)+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n;int x;

Wypróbuj online!

Python 3.8, 104 74 65 60 57 bajtów

lambda n:(-2,6)[n>4*(x:=(n**.5+1)//2)*x+2*x]*x+2+~n+8*x*x

Edycja: Podziękowania dla Johnathana Allana za uzyskanie od 74 do 57 bajtów!

To rozwiązanie wykorzystuje indeksowanie oparte na 0.

Python 3.8 (wersja wstępna) , 53 bajty

Bezpośredni port odpowiedzi JavaScript Arnaulda , idź do góry, i / lub odpowiedź Mathematica J42161217 i / lub odpowiedź Python Kapocsi :)

lambda n:((x:=int(n**.5+1)&-2)*2-(n<x*x+x)*4+3)*x+1-n

0-indeksowane.

Wypróbuj online!

Befunge, 67 57 bajtów

To rozwiązanie zakłada indeksowanie wartości wejściowych w oparciu o 0.

p&v-*8p00:+1g00:<
0:<@.-\+1*g00+*<|`
0g6*\`!8*2+00g4^>$:0

Wypróbuj online!

Wyjaśnienie

Zaczynamy od obliczenia „promienia”, przy którym wejście n znajduje się w pętli:

radius = 0
while n > 0
  radius += 1
  n -= radius*8

Na końcu pętli poprzednia wartość n jest przesunięciem w spiralę w tym promieniu:

offset = n + radius*8

Następnie możemy ustalić, czy znajdujemy się w górnej czy dolnej części spirali w następujący sposób:

bottom = offset >= radius*6

A gdy mamy już wszystkie te szczegóły, wartość spirali oblicza się za pomocą:

value = ((bottom?10:2) + 4*radius)*radius + 1 - offset

Promień jest jedyną wartością, którą musimy przechowywać jako „zmienną”, ograniczając ją do maksymalnej wartości 127 w Befunge-93, więc ten algorytm może obsłużyć dane wejściowe do 65024.

Japt , 15 bajtów

Port z roztworem galaretki Jonathana. 1-indeksowany.

gUòȲ+X*v)õÃcÔâ

Spróbuj

gUòȲ+X*v)õÃcÔâ     :Implicit input of integer U
g                   :Index into
 Uò                 :  Range [0,U]
   È                :  Map each X
    ²               :    Square X
     +X*            :    Add X multiplied by
        v           :    1 if X is divisible by 2, 0 otherwise
         )          :    Group result
          õ         :    Range [1,result]
           Ã        :  End map
            c       :  Flatten
             Ô      :    After reversing each
              â     :  Deduplicate

C ++ (gcc) , 88 bajtów

#import<cmath>
int a(int n){int x=(sqrt(n-1)+1)/2;return x*(8*(x+(n>4*x*x+2*x))-2)+2-n;}

1-indeksowany; używa formuły na stronie OEIS, ale zmanipulowano, aby zapisać kilka bajtów.

Wypróbuj online!