Z całej matematyki zawsze będzie kilka twierdzeń, które wykraczają poza wszelki zdrowy rozsądek. Jednym z nich jest fakt, że istnieją różne rozmiary nieskończoności. Innym interesującym faktem jest pomysł, że wiele nieskończoności, które wydają się być różnej wielkości, są w rzeczywistości tego samego rozmiaru. Istnieje tyle samo liczb parzystych, co liczb całkowitych, tak jak liczb wymiernych.

Ogólna koncepcja tego pytania polega na skonfrontowaniu się z dziwną rzeczywistością nieskończoności. W tym wyzwaniu Twój program wyświetli listę, która:

• W dowolnym momencie zawsze masz całą liczbę wpisów
• Ostatecznie zawierają (jeśli pozostawione na wystarczająco długo) dowolny konkretny (niezerowy) numer wymierny dokładnie raz na całej liście
• Zawierają nieograniczoną liczbę pustych miejsc (wpisy na liście, które są niepotrzebnie ustawione na 0)
• Posiadaj odsetek pustych miejsc, który zbliża się do limitu 100%
• Dla każdej dodatniej liczby całkowitej N należy mieć nieskończoną liczbę miejsc z N kolejnymi pustymi miejscami

Wyzwanie

Twoim wyzwaniem jest napisanie możliwie najkrótszego programu, który wyświetli specjalną listę z następującymi zasadami:

1. Wszystkie wpisy z indeksem, który nie jest liczbą kwadratową, należy ustawić na zero. Tak więc pierwszy wpis będzie niezerowy, drugi i trzeci będzie zerowy, czwarty będzie niezerowy itp.
2. Wszystkie liczby wymierne będą miały postać niewłaściwego ułamka (takiego jak 4/5 lub 144/13), który został uproszczony. Wyjątkiem są zera, które będą po prostu 0.
3. Wszystkie (dodatnie i ujemne) liczby wymierne powinny ostatecznie pojawić się na liście, jeśli program działa wystarczająco długo i przy wystarczającej ilości pamięci. Dla każdej konkretnej liczby wymiernej wymagany czas może być dowolnie duży, ale zawsze skończony.
4. Jeśli działa przez nieskończony czas, żadna niezerowa liczba wymierna nigdy nie powinna pojawić się dwukrotnie.

Zasada 3 dopuszcza pewną zmienność, ponieważ istnieje nieskończona liczba różnych możliwych legalnych wyników.

Wyjście będzie strumieniem linii. Każda linia będzie miała ogólną formę, w 5: 2/3której pierwszy numer jest numerem wejściowym, a następnie numerem wymiernym. Zauważ, że 1: 0zawsze będzie to pierwszy wiersz wyniku.

Przykładowy fragment wyniku:

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

Zasady, przepisy i uwagi

To jest kod golfowy. Obowiązują standardowe zasady gry w golfa. Ponadto, ze względu na dopuszczalną zmienność w danych wyjściowych, musisz przynajmniej pokazać, dlaczego uważasz, że twoja lista będzie zawierała wszystkie możliwe liczby wymierne dokładnie raz, a twoje rozwiązanie jest poprawne.

EDYCJA: Ponieważ liczby pierwsze odwracają uwagę od wyzwania, zmieniam je na liczby kwadratowe. Osiąga to ten sam cel, a także skraca rozwiązania.

Haskell, 184 znaki

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

Odbywa się to po raz pierwszy w przejściu drzewa Calkin-Wilf , dając jednokrotnie wszystkie dodatnie liczby wymierne w zmniejszonej formie. Następnie przełącza się między dodatnim i ujemnym, aby objąć wszystkie niezerowe liczby wymierne i pola zerowe między kwadratowymi wpisami.

Wynik (z wyjątkiem linii zerowych dla zwięzłości):

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

Sage, 103 113 128

Sage z łatwością wymienia racjonalne uzasadnienia! Formatowanie zgodne z wymaganiami programu, jak zwykle, wszystko psuje.

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]

Szałwia wylicza QQwedług ich wysokości : maksymalna wartość bezwzględna licznika i mianownika po redukcji GCD.

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

Wykorzystuje rekurencję podaną w Recounting the Rationals autorstwa Calkin & Wilf.

Haskell, 55 bajtów

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

wyjścia

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

1% 1 jest korzeniem drzewa Calkin-Wilf; iterat dodaje oba elementy podrzędne każdego węzła; złączenie zwija poziomy w jedną listę.

120 znaków, jeśli dodasz odpowiedni import, 0 i negatywy:

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

wyjścia

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

wyprowadzanie pustych miejsc? to jest w kiepskim guście :( miałeś mnie na „liście wszystkich pozytywnych uzasadnień”

PHP 105 bajtów

Uwaga: Ten kod musi być zapisany jako iso-8859-1 (ansi), aby działał poprawnie. Interpretatory online, które domyślnie kodują wszystkie dane wejściowe do utf8 (takie jak ideone), generują nieprawidłowe dane wyjściowe.

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

Korzystanie z wyliczenia Georga Cantora (nieznacznie zmodyfikowane dla wartości +/-).

Jeśli masz problemy z uruchomieniem powyższego kodu (prawdopodobnie z powodu nadmiernej ilości komunikatów NOTICE), użyj tego (107 bajtów):

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

Oktawa, 168 bajtów

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

Rozwiązanie nie jest bardzo wyrafinowane, jest to po prostu przekątna „dywanu” liczb wymiernych, odrzucająca wszystkie ułamki, które można uprościć. Po dodatniej liczbie a/b, jej przeciwieństwo -a/bjest zawsze drukowane, zanim przejdzie kolejna z sekwencji.

Ponieważ wszystkie pozytywne proste ułamki zwykłe zostaną wydrukowane, a ułamki przeciwne do tych zostaną wydrukowane i nigdy nie jest możliwe, aby dwie różne proste ułamki miały tę samą wartość, każda niezerowa liczba wymierna zostanie wydrukowana dokładnie raz.

Degolfed:

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