Rozważ następującą sekwencję:

0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

Wygląda całkiem bez wzoru, prawda? Oto jak to działa. Zaczynając od 0, podskakuj nliczby całkowite, nzaczynając od 1. To kolejny numer w sekwencji. Następnie dodaj wszystkie „pomijane” liczby, które nie były jeszcze widoczne w kolejności rosnącej. Następnie zwiększaj ni przeskakuj od ostatniej dołączonej liczby. Powtórz ten wzór.

Na przykład, kiedy docieramy 11, jesteśmy na n=5. Zwiększamy nsię n=6, wskoczyć do 17, następnie dołączyć 13 14 15 16od tych, które nie zostały jeszcze widoczne. Nasz następny skok to n=7kolejny element w sekwencji 23.

Wyzwanie

Biorąc pod uwagę dane wejściowe x, wypisz xth termin tej sekwencji, pierwsze xwarunki sekwencji lub zbuduj nieskończoną listę terminów sekwencji. Możesz wybrać indeksowanie 0 lub 1.

I / O i reguły

• Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
• Można założyć, że dane wejściowe i wyjściowe pasują do rodzimego typu liczb w twoim języku.
• Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

JavaScript (ES7), 41 bajtów

Zwraca n-ty ciąg sekwencji, indeksowany 0.

n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

Wypróbuj online!

W jaki sposób?

Główny przypadek: $n > 3$

Pierwsze cztery terminy sekwencji są wyjątkowe, więc odłóżmy je na razie na bok.

Dla sekwencja wygląda następująco:$n > 3$

 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

Możemy zauważyć, że w rzeczywistości istnieją dwie przeplecione podsekwencje:

• Większość wartości należy do podsekwencji dla której mamy po prostu:$A$

  $$A(n) = n - 1$$

• Niektóre inne wartości należą do podsekwencji (wyróżnionej nawiasami na powyższym diagramie), której indeksy są zgodne z sekwencją arytmetyczną 3, 3, 4, 6, 9, 13, 18, 24 ... i dla których mamy:$B$

  $$B(n,k) = n + k - 1$$

  gdzie jest indeksem w ciągu głównego, a k jest indeksem w pod-sekwencji B .$n$$k$$B$

Wskaźniki w sekwencji głównej są podane przez:$B$

Biorąc pod uwagę , wiemy, że odpowiadający termin w sekwencji głównej należy do B, jeśli n jest całkowitym rozwiązaniem równania kwadratowego:$n$$B$$n$

którego osobą dyskryminującą jest:

i którego pozytywnym rozwiązaniem jest:

Oczekujemy być liczbą całkowitą. Stąd test:$\sqrt{\Delta}$

(d = (n-- * 8 - 23) ** .5) % 1

Przypadki specjalne: $0 \le n \le 3$

Dla dyskryminator jest ujemny, a przyjmowanie pierwiastka kwadratowego daje wynik w NaN . Dla n = 3 dyskryminatorem jest$n < 3$$n = 3$ . Dlatego te pierwsze cztery terminy sekwencji są uważane za należące do podsekwencji$1$$B$ .

Gdybyśmy po prostu zastosowali naszą standardową formułę n - ~ d / 2 , otrzymalibyśmy:

zamiast:

Dlatego XOR te wyniki XOR z $0,1,2\text{ and }1$ .

Łuska , 12 bajtów

Θṁṙ_1C+ḣ2tNN

Wypróbuj online!

Wyprowadza jako nieskończoną listę. Oto wersja, która drukuje pierwsze N. .

Wyjaśnienie

Θṁṙ_1C + ḣ2tNN - Pełny program. Nie pobiera danych wejściowych, wyjściowych do STDOUT.
         tN - Zbuduj nieskończoną listę liczb naturalnych, zaczynając od 2.
      + ḣ2 - I dodaj do niego [1, 2]. Wydajność [1,2,2,3,4,5,6,7,8,9,10,11, ...].
     CN - Potnij nieskończoną listę liczb całkowitych dodatnich na części
               rozmiary Wydajność [[1], [2,3], [4,5], [6,7,8], [9,10,11,12], ...].
 ṁ - Następnie zmapuj i spłaszcz wyniki.
  ṙ_1 - Obróć każdy w prawo o 1 jednostkę.
               Wydajność [1,3,2,5,4,8,6,7,12,9,10,11, ...]
Θ - Prepend a 0. Wydajność [0,1,3,2,5,4,8,6,7,12,9,10,11, ...]

Haskell , 43 bajty

0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

Wypróbuj online!

Definiuje nieskończoną listę:

  0:1:3:2:(5!3)
≡ 0:1:3:2:5:4:(8!4)
≡ 0:1:3:2:5:4:8:6:7:(12!5)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) …

Galaretka , 15 bajtów

+‘ɼṪRṙ-œ|@
0Ç¡ḣ

Jest to pełny program, który, biorąc pod uwagę n , wypisuje pierwsze n elementów sekwencji.

Wypróbuj online!

Jak to działa

0Ç¡ḣ        Main link. Argument: n

0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.


+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)

 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.

C (gcc), 73 67 64 bajtów

t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}

Wypróbuj online!

Definiuje funkcję, fktóra pobiera indeksowanie 0 ni generuje nliczbę th w sekwencji.

Możemy przeanalizować sekwencję w następujący sposób:

f(n)  = n   where n = 0, 1

f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2

f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...

f(n)  = n-1 // for all cases not yet covered

Najpierw zajmiemy się środkową sekcją:

for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);

Zauważ, że argumenty po lewej stronie (4, 6, 9, 13, ...) są zgodne ze wzorem: najpierw dodaj dwa, następnie dodaj trzy, następnie dodaj cztery i tak dalej. Zaczynamy od t=4i dodajemy d(która zaczyna się od 2) każdą iterację pętli, zwiększając dw tym procesie.

Ciało pętli jest bardziej interesujące. Pamiętaj, że chcemy zmapować 4 do 5, 6 do 8, 9 do 12 itd .; to tylko dodanie, d-1jeśli xjest t. Jednak ta logika występuje przed ostatnim przypadkiem, f(n) = n - 1więc wiemy, że odejmiemy 1 na końcu. Dlatego możemy po prostu dodać dif x == t( x-t||(x+=d)). Jednakże, musimy też wyrwać się z pętli natychmiast po tym - więc dodać , że aby ddostać się absurdu wyglądzie d+=x+=d, który zawsze sprawi, że d<xwarunek nie powiedzie się.

Obejmuje to wszystko oprócz pierwszych czterech wartości. Patrząc na nie dwójkowo, otrzymujemy:

00 -> 00
01 -> 01
10 -> 11
11 -> 10

Chcemy więc odwrócić ostatni kawałek, jeśli 2 <= x < 4. Dokonuje się tego za pomocą x^x/2. x/2daje drugi najmniej znaczący bit, więc XOR to z oryginalnym numerem odwraca ostatni bit, jeśli liczba wynosi 2 lub 3.

Galaretka ,  13  10 bajtów

-3 Dzięki Dennisowi (użyj indeksowania 0, aby zapisać 2 z konfiguracji sumy łącznej i ostatecznego zmniejszenia)

Ḷ»2Äi+_>2$

Monadyczny link akceptujący liczbę całkowitą, 0 -indexed n , która zwraca liczbę całkowitą, a (n)

Wypróbuj online!Lub zobacz zestaw testowy

Perl 5 z -pl, 70 bajtów

$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]

Wypróbuj online!

MATL , 22 bajty

1y:"t0)@+h5M:yX-h]qw:)

Zwraca pierwsze nwarunki sekwencji.

Wypróbuj online!

Wyjaśnienie

1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display

Haskell , 51 bajtów

0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]

Wypróbuj online!

Trochę dłużej niż odpowiedź Haskell Lynna , ale inne podejście może być interesujące.

Rubinowy , 73 bajty

f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}

Wypróbuj online!

Funkcja rekurencyjna, która zwraca pierwsze x liczb z listy.

QBasic, 58 bajtów

DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP

Wydaje na czas nieokreślony. Możesz dodać SLEEP 1wewnątrz pętli lub zrobić toLOOP WHILE b<100 coś takiego, aby zobaczyć wyniki.

To po prostu implementuje specyfikację. Zauważ, że liczby, do których wracamy, zawsze będą liczbami między ostatnią przeskakiwaną liczbą a przeskakiwaną liczbą przed nią. Przechowujemy więc te granice jako ai bi używamy FORpętli, aby wydrukować wszystkie liczby między nimi.

05AB1E , 14 bajtów

0)sƒ¤N+LÁ«}Ùs£

Wypróbuj online!

R , 70 bajtów

function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}

Wypróbuj online!

• 1-indeksowany
• -4 bajty przy użyciu F stałej dzięki sugestii @JAD
• -5 bajtów odwracających listę dzięki sugestii @Giuseppe
• -2 bajty usuwające niepotrzebne nawiasy klamrowe w pętli for dzięki sugestii @JAD
• -2 bajty setdiffzamiastx[x %in% y]

Poprzednia wersja (79 bajtów)

Python 2 , 123 bajty

def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s    

Wypróbuj online!

Biorąc pod uwagę wejście x, wypisz pierwsze x wyrażenia sekwencji,

Uczę się języka Python, a dzięki tym wyzwaniom wszystko staje się ciekawsze.

Edycja: gol trochę białych znaków

Galareta , 16 bajtów

RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

Wypróbuj online!

Jeden bajt dłuższy niż istniejąca odpowiedź Jelly, ale to może być trochę golfa. RÄṬŻk²Ḋ$może być krótszy.

18 bajtów

RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

Dłuższy, ale inny.

Rubinowy , 63 bajty

->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}

Wypróbuj online!

0-indeksowane. Prawdopodobnie można go zagrać w golfa.

Perl 6 , 52 bajtów

(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

Wypróbuj online!

To wyrażenie generatora używa ...operatora. Wyszukuje luki w poprzedniej sekwencji @_poprzez ((^max @_)∖@_).min.?key:

      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2

Jest ?to konieczne dla wartości początkowej, która nie ma .key. Jeśli nie zostaną znalezione luki, to dodaje n (tutaj w $zmiennej) do ostatniej wartości na liście, plus jeden dla off o 0 błędów.

Python 3 , 104 bajty

def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1

Wypróbuj online!

Biorąc pod uwagę wejście x, wypisz pierwsze x „sekwencje”