Output a list of all rational numbers

Question

Out of all of mathematics, there will always be a few theorems that go beyond all common sense. One of these is the fact that there are different sizes of infinity. Another interesting fact is the idea that many infinities which seem to be of different size are actually of the same size. There are just as many even numbers as integers, as there are rational numbers.

The general concept of this question is to confront the bizarre reality of infinity. In this challenge, your program will output a list which will:

• At any specific moment of time, always have a whole number of entries
• Eventually contain (if left to run long enough) any specific (non-zero) rational number precisely once on the entire list
• Contain an unbounded number of empty slots (entries on the list that are needlessly set to 0)
• Have a proportion of empty slots that approaches a limit of 100%
• For every positive integer N, have an infinite number of places with N consecutive empty slots

The Challenge

Your challenge is to write that shortest possible program that will output a special list with the following rules:

1. All entries with an index that is not a square number should be set to zero. So, the first entry will be nonzero, the second and third will be zero, the fourth will nonzero, etc.
2. All rational numbers will be in the form of an improper fraction (such as 4/5 or 144/13) that has been simplified. The exception is zeroes, which will be simply 0.
3. All (positive and negative) rational numbers should eventually appear on the list if your program runs for long enough and with enough memory. For any particular rational number, the time required may be an arbitrarily large, but always finite, amount of time.
4. If run for an infinite amount of time, no non-zero rational number should ever appear twice.

Rule 3 does allow for some variation, as in there is an infinite number of different possible legal outputs.

Output will be a stream of lines. Each line will be of the general form of 5: 2/3 where the first number is the entry number, then followed by the rational number. Note that 1: 0 will always be the first line of output.

Example snippet of output:

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

Rules, Regulations, and Notes

This is code golf. Standard code golf rules apply. Also, due to the variation allowed in the output, you need to at least show why you believe that your list will contain all possible rational numbers exactly once, and that your solution is correct.

EDIT: Since the primes numbers did distract from the challenge, I am changing it to square numbers. This accomplishes the same purpose, and also shortens the solutions.

Answer 1

Haskell, 184 characters

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

This does a breadth-first traversal of the Calkin-Wilf Tree, yielding all positive rational numbers in reduced form exactly once. It then alternates between positive and negative to cover all the non-zero rational numbers and pads with zeroes between the square entries.

Output (excluding zero lines for brevity):

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

Answer 2

Sage, 103 113 128

Sage can list the rationals with ease! Formatting to fit the program requirements, as always, ruins everything.

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 enumerates QQ according to their height: the max absolute value of the numerator & denominator after GCD reduction.

Answer 3

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

This uses the recursion given in Recounting the Rationals by Calkin & Wilf.

Answer 4

Haskell, 55 bytes

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

outputs

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

1%1 is the root of the Calkin-Wilf tree; the iterate adds both children of each node; the join collapses the levels into a single list.

120 chars if you add proper imports, 0, and negatives:

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

outputs

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

outputting empty slots? that's in poor taste:( you had me at "list of all positive rationals"

Answer 5

PHP 105 bytes

Note: This code must be saved as iso-8859-1 (ansi) in order to run correctly. Online interpretters which encode all input to utf8 by default (such as ideone) will generate the wrong output.

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

Using Georg Cantor's enumeration (slightly modified for +/- values).

If you're having problems getting the above code to run (likely due to an excessive amount of NOTICE messages), use this instead (107 bytes):

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

Answer 6

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

The solution is not very sophisticated, it is just a simple diagonal traversal of the "carpet" of rational numbers, discarding all fractions that can be simplified. After a positive number a/b, it's opposite -a/b is always printed before the next one from sequence goes.

Since all positive simple fractions will be printed and the opposite signed fractions to those will be printed, and it's never possible to two different simple fractions to have the same value, each non-zero rational number will be printed exactly once.

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