Die Reihenfolge ist zu meta

25

Wir beginnen mit einer leeren 1-indizierten Sequenz:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,...

Im n- ten Schritt füllen wir alle a (n) -Leerzeichen mit den ganzen Zahlen größer als 1 aus, beginnend mit dem ersten verbleibenden Leerzeichen, wobei a (n) der n- te Eintrag in der Sequenz ist.

Nach dem ersten Schritt:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,...

Beachten Sie, dass a (1) 2 sein muss, da die erste ganze Zahl größer als 1 2 ist.

Im zweiten Schritt füllen wir alle a (2) Lücken aus. Es ist offensichtlich, dass a (2) 2 sein muss.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,...

Im dritten Schritt füllen wir alle a (3) Lücken aus. Aus der Folge ist a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,...

Im vierten Schritt füllen wir alle a (4) Lücken aus. Aus der Folge ist a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,...

Schließlich:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,...

Aufgabe

Bei n wird das n- te Element der Sequenz zurückgegeben.

Die ersten 10.000.000 Begriffe der Sequenz finden Sie hier .

Das ist Code-Golf . Kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken .

code-golf sequence Undichte Nonne
quelle
@ LuisMendo Danke, ich habe es hinzugefügt.
Undichte Nonne
Nur neugierig, was hat mr.One falsch gemacht, von der Sequenz ausgeschlossen zu werden?
Dead Possum
@DeadPossum Nun, wenn Sie alle Lücken ausfüllen, sind Sie in einem Schritt fertig.
Undichte Nonne
2
@DeadPossum Wenn a (n) 1 ist, füllt der n-te Schritt jedes verbleibende Leerzeichen aus und beendet die Generierung.
Undichte Nonne
1
@QBrute Ich habe eine Liste der ersten 10.000.000 Links in der Frage bereitgestellt. Zeichne sie einfach.
Undichte Nonne

Antworten:

20

Haskell , 80 67 Bytes

g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m

Probieren Sie es online!

Haskell ist die perfekte Sprache, um eine unendliche Liste in sich selbst zu definieren.

Anders Kaseorg
quelle
1
Angesichts der Tatsache, dass der TIO-Link wie erwartet funktioniert, sollte meine Frage stattdessen lauten: Können Sie eine Erklärung hinzufügen, wie dies funktioniert?
Julian Wolf
2
@JulianWolf Es hört sich so an, als ob Sie mit letPattern Guards nicht vertraut sind. pattern1 | let pattern2 = expr2 = expr1bedeutet dasselbe wie pattern1 = let pattern2 = expr2 in expr1(aus demselben Grund [expr1 | let pattern2 = expr2]bedeutet das dasselbe wie [let pattern2 = expr2 in expr1]).
Anders Kaseorg
1
Ich muss mich an letPattern Guards erinnern (vor allem daran, dass sie Funktionen ausführen können)! Außerdem m=2:2:2`drop`g mist ein Byte kürzer.
Ørjan Johansen
1
(!!)$0:mist zwei Bytes kürzer.
Ørjan Johansen
1
Eigentlich kann man das 2:2:Zeug mit etwas mehr Faulheit ganz fallen lassen: g ~(a:b)|...und m=g m.
Ørjan Johansen
10

C, 123 Bytes

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

Probieren Sie es online!

Komplettlösung

f(n){int*p=calloc(n,4),

Ordnen Sie ein Array mit n Ganzzahlen zu, um die ersten n Elemente der Sequenz zu speichern . Diese Hardcodes sizeof(int)wie 4, die eine sichere Annahme in den meisten Fällen und sicherlich ein Ich bin bereit , im Rahmen des Code Golf zu machen. :)

i=0,j,k;

Dies sind alles Zähler: ifür den Index des Schritts, auf dem wir uns befinden, jum die Sequenz zu durchlaufen und knach leeren Stellen zu suchen und um zu zählen, wie viele leere Stellen gesehen wurden.

for(*p=p[1]=2;i<n;++i)

Bevor wir unsere Hauptschleife starten, schleichen wir uns in einer Initialisierung der ersten beiden Elemente der Sequenz an 2. ( p[0]= *(p + 0)= *p.) Das wirft zwar die Zählung ab k, aber ...

for(j=0,k=i/2?0:2-i;j<n;++j)

... führen wir auch eine hinterhältige Initialisierung von durch k, bei der überprüft wird, ob der Wert ikleiner als ist, 2und der Startwert von korrigiert wird, kwenn dies der Fall ist. Hier beginnt auch die innere Schleife, die bei jedem Schritt die gesamte bisherige Sequenz durchläuft.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

Diese Zeile könnte eine Erklärung gebrauchen. Wir können dies erweitern auf:

if (!(p[j] || ((k++) % p[i]))) {
    p[j] = k / p[i] + 2;
}

durch Kurzschließen und dann durch De Morgans Gesetze und die Tatsache, dass 0in C falsch ist:

if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
}

Dies bedeutet im Wesentlichen: "Wenn dieser Bereich leer ist, erhöhen Sie ihn k. Wenn er kzuvor ein Vielfaches der Schrittgröße war, führen Sie die folgende Anweisung aus." Daher führen wir die Anweisung für jedes Element der Schrittgröße aus , und genau so wird die Sequenz beschrieben. Die Aussage selbst ist einfach; alles wird es generieren 2, 3, 4, ....

n=p[n-1];}

Unter Verwendung des tricky-return-without-a-return, mit dem gearbeitet wird gcc, "geben" wir das letzte Element der ersten n Terme in der Sequenz zurück, das zufällig der n- te Term ist.

Türknauf
quelle
3

Pyth, 29 Bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1

Probieren Sie es online aus

Wie es funktioniert

Anstatt mit Listen herumzuspielen, wird eine einfache rekursive Formel verwendet.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input())))
Anders Kaseorg
quelle
3

Haskell , 67 Bytes

0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j<i]
f=(%1).pred

Probieren Sie es online!

Eine rekursive arithmetische Lösung, die im Grunde die gleiche Methode ergab wie Anders Kaseorgs Pyth-Antwort .

Dieser Code ist mit Warzen bedeckt - hässliche Teile, die aussehen, als könnten sie weggolfen werden, aber ich habe nicht gesehen, wie.

Die Funktion i%jmöchte wirklich einen Wächter verwenden, um zu prüfen, ob mod i(f j)>0einer der beiden entsprechenden Ausdrücke vorliegt, und um sie auszuwerten. Aber beide Ausdrücke verwenden div i(f j). Wenn Sie das in einer Wache binden, wird es nicht auf beide Seiten zutreffen. Soweit ich weiß, kann eine Wache nicht dazu gebracht werden, sich über andere Wachen zu "verteilen". letund wheresind zu lang. Der Code lastwählt also einen von zwei Ausdrücken aus, während der Guard die Variable bindet. Pfui.

Idealerweise würden wir verwenden, divModweil sowohl das divals modauch verwendet werden, aber es (d,m)<-divMod ...ist ein langer Ausdruck. Wir überprüfen stattdessen, ob der Mod ungleich Null ist, indem wir prüfen, ob der divWert mal dem Divisor unter dem ursprünglichen Wert liegt.

Der 0%j=2Fall wäre nicht nötig, wenn Haskell kurzgeschlossen würde div 0, was nicht der Fall ist. Das .predkonvertiert den 1-indizierten Eingang in einen Null-indizierten, sonst würde es -1überall Korrekturen geben.

xnor
quelle
Wenn Sie %1-indiziert schalten , benötigen Sie eine 5-Byte-Korrektur, die nur bindet. Allerdings können Sie dann inline fin %ohne Kosten, und dann fwird anonym , so dass Sie insgesamt zwei Bytes speichern.
Ørjan Johansen
@ ØrjanJohansen Was meinst du hier mit Inline? Ich verstehe nicht, wie ich die Referenzen ändern kann, fohne Bytes zu verlieren.
Xnor
divModscheint ein Byte billiger zu sein, weil es das Verzweigen mit erlaubt !!(0^m). Bisher habe ich:1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);(%1)
Ørjan Johansen
Wie Sie sehen, setzt das Inlining die 1-Neuindizierung voraus, wodurch das entfernt wird .pred.
Ørjan Johansen
2

JavaScript (ES6), 98 93 91 Byte

Eine rekursive Funktion, die stoppt, sobald das Ergebnis verfügbar ist.

f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Alternative Version, 90 Byte

Vorgeschlagen von Shaggy für -1 Byte

Dieser muss mit gerufen werden f(n)(). Obwohl der entsprechende Beitrag in Meta derzeit eine positive Bewertung ergibt, ist diese Syntax offenbar umstritten.

n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Demo

Code-Snippet anzeigen

Arnauld
quelle
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k?c:++v:(i=1,v=2),i=0,k=a[p]||2))sollte für 92 Bytes funktionieren. Nennen Sie es mit f(n)().
Shaggy
@ Shaggy Danke! Als alternative Version hinzugefügt.
Arnauld
1

Java 8, 124 Bytes

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];}

Lambda-Ausdruck.

Erstellt ein ganzzahliges Array und füllt es kontinuierlich auf, bis der n-te Wert gefüllt wird.

Das Vordeklarieren von Variablen oben, um so viele Deklarationen wie möglich zu vermeiden, intkostet 4 Byte Speicherplatz, während das Hinzufügen von ,n2 Byte erforderlich ist.

Bei der j'ten Iteration der Berechnung ist die Anzahl der zu überspringenden' Leerzeichen gleich a[j](oder 2, wenn leer). Es stellt sich heraus, dass, wenn die erste Lücke, die wir ausfüllen müssen, an der Position ist k, k * a[j]wir den 'Schritt' ( s) erhalten.

Xanderhall
quelle