Die Abfolge des Hochspringens

19

Betrachten Sie die folgende Reihenfolge:

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

Sieht ziemlich musterlos aus, oder? So funktioniert das. Beginnen Sie mit 0, springen Sie nganzzahlig auf, und nbeginnen Sie mit 1. Das ist die nächste Nummer in der Sequenz. Fügen Sie dann alle "übersprungenen" Zahlen hinzu, die noch nicht in aufsteigender Reihenfolge angezeigt wurden. Dann inkrementieren nund von der letzten angehängten Zahl springen. Wiederholen Sie dieses Muster.

Wenn wir zum Beispiel erreichen 11, sind wir bei n=5. Wir erhöhen nsein n=6, springen bis zu 17, dann append 13 14 15 16da diese noch nicht gesehen worden. Unser nächster Sprung ist n=7, also ist das nächste Element in der Sequenz 23.

Die Herausforderung

Geben Sie bei gegebener Eingabe xden xdritten Ausdruck dieser Sequenz und die ersten xAusdrücke der Sequenz aus oder erstellen Sie eine unendliche Liste der Ausdrücke der Sequenz. Sie können zwischen 0- und 1-Indexierung wählen.

I / O und Regeln

Die Eingabe und Ausgabe kann durch jede bequeme Methode erfolgen .
Es kann davon ausgegangen werden, dass die Eingabe und Ausgabe in den Native Number-Typ Ihrer Sprache passt.
Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
Standardlücken sind verboten.
Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.

code-golf sequence AdmBorkBork
quelle

Es ist anscheinend nicht (noch?) Auf OEIS

JayCe

@ JayCe Ich bin nicht überrascht - es ist eine ziemlich willkürliche Sequenz.

AdmBorkBork

Antworten:

24

JavaScript (ES7), 41 Byte

Gibt den n-ten Term der Sequenz mit dem Index 0 zurück.

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

Probieren Sie es online!

Wie?

Hauptfall: $n > 3$

Die ersten vier Terme der Sequenz sind etwas Besonderes. Lassen Sie uns sie daher zunächst beiseite legen.

Für sieht die Sequenz so aus: $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   -  -  - ...

Wir können feststellen, dass es tatsächlich zwei verschachtelte Teilsequenzen gibt:

Die meisten Werte gehören zur Subsequenz für die wir einfach haben: $A$

$EIN (n) = n - 1$ $A(n) = n - 1$
Einige andere Werte gehören zur Subsequenz (im obigen Diagramm mit Klammern markiert), deren Indizes der arithmetischen Sequenz 3, 3, 4, 6, 9, 13, 18, 24 folgen ... und für die wir haben: $B$

$B (n, k) = n + k - 1$ $B(n,k) = n + k - 1$
wobei der Index in der Hauptreihe und ist der Index in der Subsequenz . $n$ $k$ $B$

Die Indizes von in der Hauptsequenz sind gegeben durch: $B$

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

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

Wenn , wissen wir, dass der entsprechende Term in der Hauptsequenz zu gehört, wenn eine ganzzahlige Lösung der quadratischen Gleichung ist: $n$ $B$ $n$

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

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

dessen Diskriminante ist:

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

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

und dessen positive Lösung ist:

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

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

Wir erwarten, dass eine ganze Zahl ist. Daher der Test: $\sqrt{\Delta}$

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

Sonderfälle: $0 \le n \le 3$

Für ist die Diskriminante negativ und ihre Quadratwurzel ergibt NaN . Für ist die Diskriminante . Daher wird angenommen, dass diese ersten vier Terme der Sequenz zur Teilsequenz . $n < 3$ $n = 3$ $1$ $B$

Wenn wir nur unsere Standardformel n - ~ d / 2 anwenden , erhalten wir:

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

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

anstatt:

0, 1, 3, 2

$0, 1, 3, 2$

Aus diesem Grund XOR wir diese Ergebnisse mit . $0,1,2\text{ and }1$

Arnauld
quelle

10

Schale , 12 Bytes

Θṁṙ_1C+ḣ2tNN

Probieren Sie es online!

Ausgaben als unendliche Liste. Hier ist eine Version, die das erste N ausgibt .

Erläuterung

Θṁṙ_1C + ḣ2tNN - Volles Programm. Nimmt keine Eingabe, gibt STDOUT aus.
         tN - Konstruiere die unendliche Liste natürlicher Zahlen, beginnend mit 2.
      + ḣ2 - Und füge [1, 2] hinzu. Ausbeuten [1,2,2,3,4,5,6,7,8,9,10,11, ...].
     CN - Schneide die unendliche Liste positiver Ganzzahlen in Teile davon
               Größen. Ausbeuten [[1], [2,3], [4,5], [6,7,8], [9,10,11,12], ...].
 ṁ - Ordnen Sie die Ergebnisse danach zu und reduzieren Sie sie.
  ṙ_1 - Jeweils um 1 Einheit nach rechts drehen.
               Ausbeuten [1,3,2,5,4,8,6,7,12,9,10,11, ...]
Θ - 0 voranstellen. Ausbeuten [0,1,3,2,5,4,8,6,7,12,9,10,11, ...]

Mr. Xcoder
quelle

7

Haskell , 43 Bytes

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

Probieren Sie es online!

Definiert eine unendliche Liste:

  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
quelle

4

Gelee , 15 Bytes

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

Dies ist ein vollständiges Programm, das bei n die ersten n Elemente der Sequenz ausgibt.

Probieren Sie es online!

Wie es funktioniert

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
quelle

3

C (gcc) 73 67 64 Bytes

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;}

Probieren Sie es online!

Definiert eine Funktion f, die 0-indiziert ist nund die nth-Zahl in der Sequenz erzeugt.

Wir können die Sequenz wie folgt analysieren:

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

Zuerst behandeln wir den Mittelteil:

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

Beachten Sie, dass die Argumente auf der linken Seite (4, 6, 9, 13, ...) einem Muster folgen: Zuerst zwei, dann drei, dann vier usw. hinzufügen. Wir beginnen bei t=4und addieren d(was bei 2 beginnt) jede Iteration der Schleife, wobei wir inkrementieren d.

Der Körper der Schleife ist interessanter. Denken Sie daran, dass wir 4 bis 5, 6 bis 8, 9 bis 12 usw. abbilden möchten. das ist nur das Hinzufügen , d-1wenn xist t. Diese Logik kommt jedoch vor dem letzten Fall, f(n) = n - 1sodass wir wissen, dass wir am Ende 1 subtrahieren werden. Deshalb können wir einfach dif x == t( x-t||(x+=d)) hinzufügen . Wir werden jedoch auch unmittelbar danach brechen aus der Schleife müssen - also fügen wir , dass auf ddie absurd aussehenden zu bekommen d+=x+=d, die immer das machen d<xBedingung scheitern.

Dies umfasst alles außer den ersten vier Werten. Wenn wir sie in Binärform betrachten, erhalten wir:

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

Also wollen wir das letzte bisschen umdrehen, wenn 2 <= x < 4. Dies geschieht mit x^x/2. x/2ergibt das zweitniedrigstwertige Bit, also wird durch XOR-Verknüpfung mit der ursprünglichen Nummer das letzte Bit umgedreht, wenn die Nummer 2 oder 3 ist.

Türknauf
quelle

3

Jelly , 13 10 Bytes

-3 Dank an Dennis (speichere mit der 0-Indizierung 2 aus dem kumulativen Summenaufbau und einer abschließenden Dekrementierung)

Ḷ»2Äi+_>2$

Ein monadischen Link auf eine ganze Zahl ist , Akzeptieren 0 -indexed n , die eine ganze Zahl zurückgibt, a (n)

Probieren Sie es online! Oder sehen Sie sich eine Testsuite an

Jonathan Allan
quelle

Nett! Ich hatte ḶÄ+3i+’aber keine Ahnung, wie ich mit den Randfällen umgehen soll.

Dennis

Ich habe auch Ḷ»ạ¥3für Ḋ3,2;- fühlt sich an wie es knappere für dieses Bit sein sollte.

Jonathan Allan

Ḷ»2Äi+_>2$Spart 3 Bytes mit 0-basierter Indizierung.

Dennis

Oh geiles Golf! Ich steckte in einem Land mit einem Index fest.

Jonathan Allan

2

Perl 5 mit `-pl`70 Bytes

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

Probieren Sie es online!

Dom Hastings
quelle

2

MATL , 22 Bytes

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

Gibt die ersten nTerme der Sequenz aus.

Probieren Sie es online!

Erläuterung

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
quelle

Ich mag den Smilie am Ende, jetzt möchte ich, dass alle meine MATL-Programme mit einem Lächeln enden. :)

Sundar - Reinstate Monica

@sundar Ja, ich bin froh, dass es eine relativ verbreitete Redewendung in MATL :-D

Luis Mendo ist.

2

Haskell , 51 Bytes

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

Probieren Sie es online!

Etwas länger als Lynns Haskell-Antwort , aber der andere Ansatz könnte trotzdem interessant sein.

Laikoni
quelle

1

Ruby , 73 Bytes

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

Probieren Sie es online!

Rekursive Funktion, die die ersten x-Nummern der Liste zurückgibt.

crashoz
quelle

1

QBasic, 58 Bytes

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

Ausgänge auf unbestimmte Zeit. Möglicherweise möchten Sie eine SLEEP 1innerhalb der Schleife hinzufügen oder es LOOP WHILE b<100oder so etwas machen, um die Ergebnisse zu sehen.

Dies implementiert im Grunde nur die Spezifikation. Beachten Sie, dass die Nummern, für die wir zurückgehen, immer die Nummern zwischen der zuletzt angesprungenen Nummer und der zuvor angesprungenen Nummer sind. Also speichern wir diese Grenzen als aund bund verwenden eine FORSchleife, um alle Zahlen zwischen ihnen auszudrucken.

DLosc
quelle

1

05AB1E , 14 Bytes

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

Probieren Sie es online!

Emigna
quelle

1

R , 70 Bytes

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

Probieren Sie es online!

1-indiziert
-4 Bytes mit FKonstante dank @JAD-Vorschlag
-5 Bytes Umkehrung der Liste dank @ Giuseppe Vorschlag
-2 Bytes zum Entfernen unnötiger Klammern in der for-Schleife dank @JAD-Vorschlag
-2 Bytes mit setdiffanstelle vonx[x %in% y]

Vorherige Version (79 Bytes)

digEmAll
quelle

2

79 Bytes

JAD

@JAD: Ich habe immer vergessen, F / T zu verwenden ... Ich kann nichts dafür, ich bin zu geneigt, "unsicheren Code" zu vermeiden: D

digEmAll

1

Wenn Sie die Liste in umgekehrter Reihenfolge erstellen, 5 byteswird eine Reihe von Warnungen gespeichert und ausgelöst!

Giuseppe

Es ist nicht einmal unsicher, wenn F/Tbei der Funktionsdefinition nicht neu definiert werden. Es ändert nicht (IIRC) den globalen Wert fürF/T

JAD

1

72 Bytes

JAD

1

Python 2 , 123 Bytes

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

Probieren Sie es online!

Bei Eingabe von x werden die ersten x Terme der Sequenz ausgegeben.

Ich lerne Python und diese Herausforderungen machen die Dinge interessanter.

Edit: etwas Whitespace rasieren

Medium Cog
quelle

Willkommen bei PPCG! Sie können in loszuwerden einigen mehr Räume bekommen 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

Gelee , 16 Bytes

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

Probieren Sie es online!

Ein Byte länger als die existierende Jelly-Antwort, aber dies könnte möglicherweise ein wenig golfen werden. RÄṬŻk²Ḋ$könnte vielleicht kürzer sein.

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

Länger aber anders.

dylnan
quelle

0

Ruby , 63 Bytes

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

Probieren Sie es online!

0-indiziert. Kann wohl runtergolfen werden.

Setzen Sie Monica iamnotmaynard wieder ein
quelle

0

Perl 6 , 52 Bytes

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

Probieren Sie es online!

Dies ist ein Generatorausdruck, der den ...Operator verwendet. Es sucht nach Lücken in der vorherigen Reihenfolge @_über ((^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

Das ?ist notwendig für den Anfangswert, der kein .key. Wenn keine Lücken gefunden werden, wird n (hier in der $Variablen) zum letzten Wert in der Liste addiert , plus eins für off by 0 error.

Phil H
quelle

0

Python 3 , 104 Bytes

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

Probieren Sie es online!

Bei Eingabe von x werden die ersten x "Folgen" ausgegeben

frosqh
quelle