Sekwencja skoków

19

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

code-golf sequence AdmBorkBork
źródło

Najwyraźniej nie (jeszcze?) Na OEIS

JayCe

@JayCe Nie jestem zaskoczony - to dość arbitralna sekwencja.

AdmBorkBork

Odpowiedzi:

24

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$ $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$ $B(n,k) = n + k - 1$
gdzie jest indeksem w ciągu głównego, a jest indeksem w pod-sekwencji . $n$ $k$ $B$

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

n_{k} = \frac{k^{2} - k + 6}{2}

$n_k = \frac{k^2 - k + 6}{2}$

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

x^{2} - x + 6 - 2 n = 0

$x^2 - x + 6 - 2n = 0$

którego osobą dyskryminującą jest:

Δ = 1 - 4 (6 - 2 n) = 8 n - 23

$\Delta = 1 - 4(6 - 2n) = 8n - 23$

i którego pozytywnym rozwiązaniem jest:

x = \frac{1 + \sqrt{Δ}}{2}

$x = \frac{1 + \sqrt{\Delta}}{2}$

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 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:

- \frac{1}{2}, \frac{1}{2}, \frac{3}{2}, 3

$-\frac 1 2, \frac 1 2, \frac 3 2, 3$

zamiast:

0, 1, 3, 2

$0, 1, 3, 2$

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

Arnauld
źródło

10

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

Pan Xcoder
źródło

7

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) …

Lynn
źródło

4

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.

Dennis
źródło

3

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.

Klamka
źródło

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

Jonathan Allan
źródło

Ładny! Miałem ḶÄ+3i+’, ale nie miałem pojęcia, jak radzić sobie z przypadkowymi skrzynkami.

Dennis

Mam też Ḷ»ạ¥3za Ḋ3,2;- Odczuwana jak nie powinno być terser do tego kawałka.

Jonathan Allan

Ḷ»2Äi+_>2$zapisuje 3 bajty z indeksowaniem opartym na 0.

Dennis

Och, świetny golf! Utknąłem w ziemi z 1 indeksem.

Jonathan Allan

2

Perl 5 z `-pl`, 70 bajtów

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

Wypróbuj online!

Dom Hastings
źródło

2

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

Luis Mendo
źródło

Na koniec podoba mi się smilie, teraz chcę, aby wszystkie moje programy MATL zakończyły się uśmiechem. :)

sundar - Przywróć Monikę

@sundar Tak, cieszę się, że jest to dość powszechny idiom w MATL :-D

Luis Mendo

2

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.

Laikoni
źródło

1

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.

crashoz
źródło

1

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.

DLosc
źródło

1

05AB1E , 14 bajtów

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

Wypróbuj online!

Emigna
źródło

1

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)

digEmAll
źródło

2

79 bajtów

JAD

@JAD: Zawsze zapomniałem użyć F / T ... Nie mogę nic na to

poradzić

1

Konstruowanie listy w odwrotnych zapisach 5 bytespowoduje wiele ostrzeżeń!

Giuseppe

Nie jest nawet niebezpieczne, jeśli F/Tnie zostaną ponownie zdefiniowane w definicji funkcji. Nie modyfikuje (IIRC) globalnej wartości dlaF/T

JAD

1

72 bajty

JAD

1

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

Medium Cog
źródło

Witamy w PPCG! Można pozbyć się trochę więcej przestrzeni w for n in range(1,z) if len(s) < z]; return s: for n in range(1,z)if len(s)<z];return s.

Laikoni

0

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.

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

Dłuższy, ale inny.

dylnan
źródło

0

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.

Przywróć Monikę - notmaynard
źródło

0

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.

Phil H.
źródło

0

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”

frosqh
źródło