De todas las matemáticas, siempre habrá algunos teoremas que van más allá del sentido común. Uno de estos es el hecho de que hay diferentes tamaños de infinito. Otro hecho interesante es la idea de que muchos infinitos que parecen ser de diferente tamaño son en realidad del mismo tamaño. Hay tantos números pares como enteros, ya que hay números racionales.

El concepto general de esta pregunta es confrontar la extraña realidad del infinito. En este desafío, su programa generará una lista que:

• En cualquier momento específico, siempre tenga un número entero de entradas
• Eventualmente contenga (si se deja que se ejecute lo suficiente) cualquier número racional específico (que no sea cero) precisamente una vez en toda la lista
• Contiene un número ilimitado de ranuras vacías (entradas en la lista que se establecen innecesariamente en 0)
• Tener una proporción de espacios vacíos que se acerque a un límite del 100%
• Por cada entero positivo N, tenga un número infinito de lugares con N ranuras vacías consecutivas

El reto

Su desafío es escribir el programa más corto posible que generará una lista especial con las siguientes reglas:

1. Todas las entradas con un índice que no sea un número cuadrado deben establecerse en cero. Entonces, la primera entrada será distinta de cero, la segunda y la tercera serán cero, la cuarta será distinta de cero, etc.
2. Todos los números racionales tendrán la forma de una fracción impropia (como 4/5 o 144/13) que se ha simplificado. La excepción son los ceros, que serán simplemente 0.
3. Todos los números racionales (positivos y negativos) deberían aparecer eventualmente en la lista si su programa se ejecuta durante el tiempo suficiente y con suficiente memoria. Para cualquier número racional particular, el tiempo requerido puede ser una cantidad arbitrariamente grande, pero siempre finita.
4. Si se ejecuta durante una cantidad de tiempo infinita, ningún número racional distinto de cero debería aparecer dos veces.

La regla 3 permite alguna variación, ya que hay un número infinito de diferentes resultados legales posibles.

La salida será un flujo de líneas. Cada línea tendrá la forma general de 5: 2/3donde el primer número es el número de entrada, seguido del número racional. Tenga en cuenta que 1: 0siempre será la primera línea de salida.

Fragmento de ejemplo de salida:

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

Reglas, Regulaciones y Notas

Este es el código de golf. Se aplican las reglas estándar del código de golf. Además, debido a la variación permitida en la salida, debe mostrar al menos por qué cree que su lista contendrá todos los números racionales posibles exactamente una vez, y que su solución es correcta.

EDITAR: Dado que los números primos distrajeron del desafío, lo estoy cambiando a números cuadrados. Esto cumple el mismo propósito y también acorta las soluciones.

Haskell, 184 caracteres

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

Esto atraviesa por primera vez el árbol Calkin-Wilf , produciendo todos los números racionales positivos en forma reducida exactamente una vez. Luego alterna entre positivo y negativo para cubrir todos los números racionales distintos de cero y los pads con ceros entre las entradas cuadradas.

Salida (excluyendo líneas cero por brevedad):

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 puede enumerar los racionales con facilidad! Formatear para ajustarse a los requisitos del programa, como siempre, arruina todo.

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]

Sage enumera QQsegún su altura : el valor absoluto máximo del numerador y denominador después de la reducción de 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

Esto utiliza la recursividad dada en Recuento de los racionales por Calkin y Wilf.

Haskell, 55 bytes

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

salidas

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

1% 1 es la raíz del árbol Calkin-Wilf; la iteración agrega ambos hijos de cada nodo; la unión contrae los niveles en una sola lista.

120 caracteres si agrega importaciones adecuadas, 0 y negativos:

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

salidas

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

salida de ranuras vacías? eso es de mal gusto :( me tenías en "lista de todos los racionales positivos"

PHP 105 bytes

Nota: Este código debe guardarse como iso-8859-1 (ansi) para que se ejecute correctamente. Los intérpretes en línea que codifican todas las entradas a utf8 de forma predeterminada (como ideone) generarán una salida incorrecta.

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

Usando la enumeración de Georg Cantor (ligeramente modificado para valores +/-).

Si tiene problemas para ejecutar el código anterior (probablemente debido a una cantidad excesiva de mensajes de AVISO), use esto en su lugar (107 bytes):

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

Octava, 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

La solución no es muy sofisticada, es solo un simple recorrido diagonal de la "alfombra" de números racionales, descartando todas las fracciones que se pueden simplificar. Después de un número positivo a/b, su opuesto -a/bsiempre se imprime antes de que pase el siguiente de la secuencia.

Dado que se imprimirán todas las fracciones simples positivas y se imprimirán las fracciones con signo opuestas a esas, y nunca es posible que dos fracciones simples diferentes tengan el mismo valor, cada número racional distinto de cero se imprimirá exactamente una vez.

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