Aus der ganzen Mathematik wird es immer ein paar Sätze geben, die über den gesunden Menschenverstand hinausgehen. Eine davon ist die Tatsache, dass es verschiedene Größen von Unendlichkeit gibt. Eine weitere interessante Tatsache ist die Idee, dass viele Unendlichkeiten, die unterschiedlich groß zu sein scheinen, tatsächlich gleich groß sind. Es gibt genauso viele gerade Zahlen wie ganze Zahlen, wie es rationale Zahlen gibt.

Das allgemeine Konzept dieser Frage ist die Konfrontation mit der bizarren Realität der Unendlichkeit. In dieser Challenge gibt Ihr Programm eine Liste aus, die:

• Haben Sie zu einem bestimmten Zeitpunkt immer eine ganze Anzahl von Einträgen
• Enthalten Sie eventuell (wenn Sie lange genug warten müssen) eine bestimmte (nicht null) rationale Zahl genau einmal in der gesamten Liste
• Enthält eine unbegrenzte Anzahl leerer Slots (Einträge in der Liste, die unnötigerweise auf 0 gesetzt sind)
• Einen Anteil an leeren Slots haben, der sich einem Limit von 100% nähert
• Haben Sie für jede positive ganze Zahl N eine unendliche Anzahl von Stellen mit N aufeinanderfolgenden leeren Slots

Die Herausforderung

Ihre Herausforderung besteht darin, das kürzestmögliche Programm zu schreiben, das eine spezielle Liste mit den folgenden Regeln ausgibt:

1. Alle Einträge mit einem Index, der keine quadratische Zahl ist, sollten auf Null gesetzt werden. Der erste Eintrag ist also ungleich Null, der zweite und dritte ungleich Null, der vierte ungleich Null usw.
2. Alle rationalen Zahlen haben die Form eines falschen Bruches (wie 4/5 oder 144/13), der vereinfacht wurde. Die Ausnahme sind Nullen, was einfach sein wird 0.
3. Alle (positiven und negativen) rationalen Zahlen sollten irgendwann in der Liste erscheinen, wenn Ihr Programm lange genug und mit genügend Speicher läuft. Für eine bestimmte rationale Zahl kann die benötigte Zeit eine willkürlich große, aber immer begrenzte Zeitdauer sein.
4. Wenn für eine unendliche Zeitspanne ausgeführt, sollte keine rationale Zahl ungleich Null jemals zweimal auftreten.

Regel 3 lässt gewisse Abweichungen zu, da es unendlich viele verschiedene mögliche rechtliche Ergebnisse gibt.

Die Ausgabe erfolgt in Form eines Zeilenstroms. Jede Zeile hat die allgemeine Form, 5: 2/3wobei die erste Nummer die Eintragsnummer ist, gefolgt von der rationalen Nummer. Beachten Sie, dass dies 1: 0immer die erste Ausgabezeile ist.

Beispielausschnitt der Ausgabe:

1: 1/1
2: 0
3: 0
4: 2/1
5: 0
6: 0
7: 0
8: 0
9: -2/1
10: 0
etc...

Regeln, Vorschriften und Hinweise

Das ist Code Golf. Es gelten die Standard-Code-Golfregeln. Aufgrund der Abweichungen, die in der Ausgabe zulässig sind, müssen Sie zumindest nachweisen, warum Sie glauben, dass Ihre Liste alle möglichen rationalen Zahlen genau einmal enthält und Ihre Lösung korrekt ist.

EDIT: Da die Primzahlen von der Herausforderung abgelenkt haben, ändere ich sie in quadratische Zahlen. Dies erfüllt den gleichen Zweck und verkürzt auch die Lösungen.

Haskell, 184 Zeichen

main=putStr.unlines$zip[1..](s>>=g)>>=h
s=(1,1):(s>>=f)
f(a,b)=[(a,a+b),(a+b,b)]
g x@(a,b)=[x,(-a,b)]
h(i,(a,b))=(i^2)%(u a++'/':u b):map(%"0")[i^2+1..i*(i+2)]
i%s=u i++": "++s
u=show

Dies durchläuft den Calkin-Wilf-Baum in seiner ersten Breite und liefert alle positiven rationalen Zahlen in reduzierter Form genau einmal. Es wird dann zwischen positiv und negativ gewechselt, um alle rationalen Zahlen ungleich Null und Pads mit Nullen zwischen den Quadrateingaben abzudecken.

Ausgabe (aus Gründen der Kürze ohne Nullzeilen):

1: 1/1
4: -1/1
9: 1/2
16: -1/2
25: 2/1
36: -2/1
49: 1/3
64: -1/3
81: 3/2
100: -3/2
...

Salbei, 103 113 128

Sage kann die Rationals mit Leichtigkeit auflisten! Eine Formatierung, die den Programmanforderungen entspricht, ruiniert wie immer alles.

for i,q in enumerate(QQ):
 for j in[(i-1)^2+1..i*i]:print'%d:'%j,[0,'%d/%d'%(q.numer(),q.denom())][j==i*i]

Salbei zählt QQnach ihrer Höhe auf : der maximale Absolutwert des Zählers und Nenners nach GCD-Reduktion.

Python, 162

f=lambda n:f(n/2)if n%2 else f(n/2)+f(n/2-1)if n else 1
n=i=1
while 1:
 print'%d:'%i,
 if i-n*n:s=0
 else: n+=1;s='%d/%d'%((-1)**n*f(n/2-1),f(n/2))
 print s
 i+=1

Dies verwendet die Rekursion aus Recounting the Rationals von Calkin & Wilf.

Haskell, 55 Bytes

mapM_ print$join$iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1]

Ausgänge

1 % 1
2 % 1
1 % 2
3 % 1
2 % 3
3 % 2
1 % 3
4 % 1
...

1% 1 ist die Wurzel des Calkin-Wilf-Baumes; Die Iteration fügt beide Kinder jedes Knotens hinzu. Durch den Join werden die Ebenen in einer einzigen Liste zusammengefasst.

120 Zeichen, wenn Sie ordnungsgemäße Importe, 0 und Negative hinzufügen:

import Data.Ratio
import Control.Monad
main=mapM_ print$0:(join(iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1])>>=(\x->[-x,x]))

Ausgänge

0 % 1
(-1) % 1
1 % 1
(-2) % 1
2 % 1
(-1) % 2
1 % 2
(-3) % 1
3 % 1
(-2) % 3
2 % 3
(-3) % 2
3 % 2
(-1) % 3
1 % 3
(-4) % 1
4 % 1
...

leere Slots ausgeben? das ist geschmacklos :( du hattest mich auf "liste aller positiven rationals"

PHP 105 Bytes

Hinweis: Dieser Code muss als iso-8859-1 (ansi) gespeichert werden, damit er korrekt ausgeführt werden kann. Online-Interpreter, die standardmäßig alle Eingaben in utf8 codieren (z. B. ideone), erzeugen die falsche Ausgabe.

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.~Ð.++$µ:"-$x":0,~õ;

Verwendung der Aufzählung von Georg Cantor (leicht modifiziert für +/- Werte).

Wenn Sie Probleme haben, den obigen Code zum Ausführen zu bringen (wahrscheinlich aufgrund einer zu großen Anzahl von NOTICE-Nachrichten), verwenden Sie stattdessen Folgendes (107 Byte):

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.'/'.++$µ:"-$x":0,'
';

Oktave, 168 Bytes

a=b=p=1;do for i=(p-1)^2+1:p^2-1 printf("%d: 0\n",i)end
printf("%d: %d/%d\n",p^2,a,b)
a=-a;if a>0do if b==1 b=a+1;a=1;else a++;b--;end until 1==gcd(a,b)end
p++;until 0

Die Lösung ist nicht sehr ausgefeilt, es ist nur eine einfache diagonale Durchquerung des "Teppichs" rationaler Zahlen, wobei alle Brüche verworfen werden, die vereinfacht werden können. Nach einer positiven Nummera/b-a/b wird immer das Gegenteil gedruckt, bevor die nächste aus der Sequenz ausgegeben wird.

Da alle positiven einfachen Brüche gedruckt werden und die entgegengesetzten vorzeichenbehafteten Brüche gedruckt werden und es niemals möglich ist, zwei verschiedene einfache Brüche mit demselben Wert zu versehen, wird jede rationale Zahl ungleich Null genau einmal gedruckt.

Entgolfet:

a=b=p=1
do
    for i=(p-1)^2+1:p^2-1
        printf("%d: 0\n",i)         # p=2,3,4: 1..3,5..8,10..15
    end
    printf("%d: %d/%d\n", p^2,a,b); # p=2,3,4: 4,9,16
    a=-a;
    if a>0                          # the rule is: after a/b, a>0 output -a/b
        do
            if b==1 b=a+1;a=1; else a++;b--; end
        until 1==gcd(a,b)
    end
    p++;
until 0