Definition

Nennen wir eine (unendliche) Ganzzahlsequenz universal, wenn sie jede endliche Ganzzahlsequenz als zusammenhängende Teilsequenz enthält.

Mit anderen Worten, die ganzzahlige Folge (a ₁ , a ₂ ,…) ist genau dann universell, wenn für jede endliche ganzzahlige Folge (b ₁ ,…, b _n ) ein Offset k vorliegt, so dass (a _{k + 1)} ,…, A _{k + n} ) = (b ₁ ,…, b _n ) .

Beispielsweise ist die Folge positiver Primzahlen nicht universell, unter anderem aus folgenden Gründen.

• Es enthält keine negativen Ganzzahlen, 1 oder zusammengesetzten Zahlen.

• Obwohl es 3 enthält , enthält es nicht die zusammenhängende Untersequenz (3, 3, 3) .

• Obwohl es 2 und 5 enthält, enthält es nicht die zusammenhängende Teilfolge (2, 5) .

• Obwohl es die zusammenhängende Teilfolge (7, 11, 13) enthält, enthält es die zusammenhängende Teilfolge (13, 11, 7) nicht .

Aufgabe

Wählen Sie eine beliebige universelle Ganzzahlsequenz (eine ₁ , eine ₂ , ...) und implementieren Sie sie in einer Programmiersprache Ihrer Wahl. Beachten Sie dabei die folgenden Regeln.

• Sie können ein vollständiges Programm oder eine Funktion einreichen.

• Sie haben drei Möglichkeiten für I / O:

  1. Nehmen Sie keine Eingabe vor und drucken oder senden Sie die gesamte Sequenz zurück.

  2. Nehmen Sie einen Index n als Eingabe und drucken oder geben Sie ein _{n zurück} .

  3. Nehmen Sie einen Index n als Eingabe und geben Sie ihn aus oder geben Sie ihn zurück (a ₁ ,…, a _n ) .

• Für die E / A-Optionen 2 und 3 können Sie bei Bedarf eine 0- basierte Indizierung verwenden.

• Ihre Übermittlung muss deterministisch sein: Wenn Sie mehrere Male mit derselben Eingabe ausgeführt werden, muss dieselbe Ausgabe erstellt werden.

Bitte beweisen Sie außerdem, dass die von Ihnen gewählte Reihenfolge universell ist, es sei denn, dies ist sofort offensichtlich. Ihr Beweis kann möglicherweise nicht von unbewiesenen Vermutungen abhängen.

Es gelten die Standardregeln für Code-Golf . Möge der kürzeste Code in Bytes gewinnen!

Schale , 5 Bytes

Dies druckt eine unendliche Liste

ΣṖ…ݱ

Probieren Sie es online! oder finden Sie den ersten Index Ihrer Sequenz . (Verbraucht für die meisten Sequenzen viel Speicher)

Erläuterung:

   ݱ   Infinite list [1,-1,2,-2,3,-3,4,-4,5,-5...]
  …     Rangify       [1,0,-1,0,1,2,1,0,-1,-2,...]
 Ṗ      Powerset
Σ       Concatenate

In Husk Ṗverhält es sich gut für unendliche Listen. Sie können das Verhalten hier sehen

Python 2 , 49 46 43 Bytes

def f(n):d=len(`n`);return n/d**(n%d)%d-d/2

f(n)gibt nur ein _{n zurück} . Hierbei wird die kleinste Stelle der nBasis verwendet d, um eine der höheren Stellen zu extrahieren.

Probieren Sie es online! Dieses Skript (mit freundlicher Genehmigung von Dennis) verwendet eine beliebige endliche Sequenz und gibt an, nwo diese Sequenz beginnt.

Erläuterung

n/d**(n%d)%d-d/2
     (n%d)         least significant digit of n
n/d**(   )%d       get n%d-th digit of n
            -d/2   offset to get negative values

Zum Beispiel für nin dem Bereich 3141592650zu 3141592659, d=10und die letzten Ziffer nwählt eine von den anderen Stellen. Dann addieren wir -d/2, um negative Werte zu erhalten.

n%d:       0  1  2  3  4  5  6  7  8  9
f(n)+d/2:  0  5  6  2  9  5  1  4  1  3
f(n):     -5  0  1 -3  4  0 -4 -1 -4 -2

Standalone-Alternative, auch 43 Bytes:

n=input();d=len(`n`);print n/d**(n%d)%d-d/2

Brachylog 2, 11 Bytes

≜~×-₂ᵐ~ȧᵐ≜∋

Probieren Sie es online!

Ich habe auch einen Algorithmus mit additiven Partitionen in einer Liste ausprobiert, der jedoch nicht kürzer war. Dies ist ein Generator, der einen unendlichen Strom von ganzen Zahlen als Ausgabe erzeugt. Der TIO-Link hat eine Kopfzeile, um die ersten zehntausend davon zu drucken.

Erläuterung

Das Programm beginnt damit, dass alle möglichen ganzen Zahlen nacheinander ausprobiert werden ( ≜alle verbleibenden Möglichkeiten werden standardmäßig für ganze Zahlen ausprobiert ). Das sind 0, 1, -1, 2, -2 usw. (obwohl die negativen ganzen Zahlen nicht das Ende des Programms erreichen). Dies ist der einzige "unendliche" Schritt des Programms; alle anderen sind endlich.

~×generiert dann alle möglichen Faktorisierungen der ganzen Zahl, behandelt verschiedene Ordnungen als unterschiedlich und verwendet nur Werte ab 2 (es gibt also nur endlich viele); Beachten Sie, dass zusammengesetzte Zahlen in der Faktorisierung zulässig sind, nicht nur Primzahlen. Dies bedeutet, dass alle möglichen Folgen von ganzen Zahlen ≥ 2 zu einem bestimmten Zeitpunkt bei der Ausführung der Funktion durch diesen Schritt erzeugt werden (da eine solche Folge notwendigerweise ein Produkt hat und dieses Produkt zu einem bestimmten Zeitpunkt durch die Initiale erzeugt wird ≜).

Wir müssen dann die Menge dieser Sequenzen auf die Menge aller ganzzahligen Sequenzen abbilden, was in zwei Schritten erfolgt: Subtrahieren von 2 ( -₂) von jedem Element ( ᵐ), wobei wir die Menge aller nichtnegativen ganzzahligen Sequenzen erhalten, und dann Plus oder Minus nehmen ( ~ȧdh "ein Wert, dessen absoluter Wert" ist) jedes Element (ᵐ). Der letztgenannte Schritt ist offensichtlich nicht deterministisch, weshalb Brachylog ihn als Generator behandelt und alle möglichen Listen generiert, deren Elemente plus oder minus dem entsprechenden Element der Eingabeliste sind. Dies bedeutet, dass wir jetzt einen Generator für alle möglichen Ganzzahlsequenzen haben, und er generiert sie in einer Reihenfolge, die bedeutet, dass sie alle generiert werden (insbesondere die Reihenfolge, die Sie erhalten, wenn Sie den absoluten Wert jedes Elements nehmen, addieren Sie 2 zu jedem Element, und ordnen Sie dann nach dem Produkt der resultierenden Elemente).

Leider will die Frage eine einzelne Sequenz, keine Sequenz von Sequenzen, also brauchen wir zwei weitere Befehle. Erstens ≜fordert Brachylog auf , die Sequenz von Sequenzen explizit streng zu generieren (im Gegensatz zur Erstellung einer Datenstruktur, die das Konzept einer mit dieser Methode generierten Sequenz beschreibt und die Sequenzen erst dann tatsächlich generiert, wenn dies erforderlich ist); Beides beschleunigt in diesem Fall das Programm und stellt sicher, dass die Ausgabe in der angeforderten Reihenfolge erfolgt. Bewirkt schließlich, ∋dass der Generator die Elemente der einzelnen Sequenzen einzeln ausgibt (wobei zur nächsten Sequenz übergegangen wird, sobald alle Elemente der vorherigen Sequenz ausgegeben wurden).

Das Endergebnis: Jede mögliche Ganzzahlsequenz wird einzeln generiert und ausgegeben und alle zusammen zu einer einzigen universellen Sequenz verkettet.

Pyth - 11 Bytes

nDas kartesische Produkt der Macht [-n, n]für alle n.

.V1js^}_bbb

Probieren Sie es online hier (endlich).

Python 2 , 100 bis 99 Bytes

• Dank ovs ein Byte gespart ; Iterieren über eine itertoolseingebaute bis unbegrenzte Schleife.

from itertools import*
for n in count():
 for P in permutations(range(-n,n)*n):
	for p in P:print p

Probieren Sie es online!

nGibt unbegrenzt alle Permutationen des -fach wiederholten Ganzzahlbereichs [-n; n)für alle nichtnegativen Ganzzahlen aus n. Mit dieser geänderten Version
können Sie nach dem ersten Offset kfür eine beliebige Untersequenz suchen .

Perl 6 , 91 Bytes

loop (my$i=1;;$i++){my@n=(-$i..$i);my@m=@n;loop (my$k=1;$k <$i;$k++){@m=@m X@n;};print @m;}

Probieren Sie es online!

Hierbei wird eine ähnliche Methode verwendet wie bei einigen anderen Antworten. Es verwendet kartesische Produkte, um die Elemente zu drucken (-1,0,1), dann alle geordneten Paare der Elemente in (-2,-1,0,1,2), dann alle geordneten Drillinge der Elemente in (-3,-2,-1,0,1,2,3)usw.

Ich bin neu in Perl, also könnte man vielleicht mehr Golf spielen.

Mehr lesbare Version:

loop (my $i = 1; ; $i++) {
  my @n = (-$i..$i);
  my @m = @n;
  loop (my $k=1; $k <$i; $k++) {
    @m = @m X @n;
  }
  print @m;
}