13
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ What is the point of rule 1? Do you just want people to mutually golf two separate programs to test primality and enumerate the rationals? \$\endgroup\$ – Peter Taylor May 12 '12 at 21:45
  • \$\begingroup\$ It shows how a very small portion of the integers still has the same cardinality as the full set of rational numbers, and it also allows the percentage of empty slots to approach (but never reach) 100%. \$\endgroup\$ – PhiNotPi May 12 '12 at 21:52
  • \$\begingroup\$ I'm assuming that the program also needs to run in a fixed amount of memory, i.e. it can't assume that the machine can always allocate more? Also, is it against the rules to use (say) a C int for the list index when you know that it has a finite range? (Even though the exact limit can vary with the implementation.) Is some form of bignum required? \$\endgroup\$ – breadbox May 12 '12 at 22:27
  • 1
    \$\begingroup\$ @PhiNotPi, there are far simpler ways of doing that, and it's a distraction from the more interesting part of the question. \$\endgroup\$ – Peter Taylor May 12 '12 at 22:48
  • 1
    \$\begingroup\$ Note that 1: 0 will always be the first line of output. – This contradicts your example and also does not make sense to me. \$\endgroup\$ – Wrzlprmft Apr 13 '15 at 13:15
6
\$\begingroup\$

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
...
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can eliminate the x.next() and use print only once, as follows, bringing the score down to 124: x=enumerate(QQ) for i,q in x: for j in[(i-1)^2+1..i*i]: print'%d: '%j,'%d/%d'%(q.numer(),q.denom())if j.is_square()else 0. This doesn't display properly in a comment, but I think you can see what I mean. \$\endgroup\$ – r.e.s. May 13 '12 at 21:55
  • \$\begingroup\$ BTW, I notice that after the first 4 positive elements, Sage's enumeration is not the same as in the other answers. The Calkin-Wilf formulas give a sequence in which the denominator of a rational is the numerator of the next rational; e.g. (..., 1/3, 3/2, 2/3, ...), compared to Sage's (..., 1/3, 3/1, 2/3,...). I can't seem to locate any documentation for Sage's enumeration, to see how it's computed. \$\endgroup\$ – r.e.s. May 13 '12 at 22:33
  • \$\begingroup\$ @r.e.s., thanks! I'd wanted to merge the print statements, but forgot to use the [x..y] notation. Great to see another Sage user here! \$\endgroup\$ – boothby May 13 '12 at 23:32
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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"

\$\endgroup\$
  • \$\begingroup\$ mapM_ print$fix((1%1:).(>>= \x->[x+1,1/(x+1)])) is 47 chars. from haskellwiki. works as is, without any imports, at haskell.org's "try it" REPL (well, without the mapM_ print part...) \$\endgroup\$ – Will Ness Oct 3 '16 at 11:25
1
\$\begingroup\$

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,'
';
\$\endgroup\$
  • 1
    \$\begingroup\$ I get run-time errors with this code (which seems to contain some strange characters; e.g., "$ö.~Ð."). \$\endgroup\$ – r.e.s. May 14 '12 at 13:46
  • \$\begingroup\$ Can you demonstrate that this solution works, say on ideone? I get errors as well: ideone.com/ru1fo \$\endgroup\$ – mellamokb May 14 '12 at 18:04
  • \$\begingroup\$ Ideone seems to error out when too many NOTICE messages are generated: both ~Ð (equal to '/') and ~õ (equal to "\n") will generate a NOTICE every iteration. Of course, if you have NOTICEs off, it's not a problem. A paste with both replaced (107 Bytes): ideone.com/lFUbl \$\endgroup\$ – primo May 14 '12 at 18:43
  • \$\begingroup\$ I've just noticed that Ideone's PHP interpretter generates the wrong output. If you run the code locally, you will see that it is correct. Or, you could test it with a valid PHP interpretter, such as Anarchy Golf's performance checker: golf.shinh.org/checker.html (save it to a file and upload) \$\endgroup\$ – primo May 14 '12 at 19:11
  • \$\begingroup\$ When I save your revised code to a file with ANSI encoding, it does run on the Anarchy Golf interpreter. However, there's now a different problem: it violates the requirement that "no non-zero rational number should ever appear twice" in the list. In fact, the code appears to list every rational infinitely many times; e.g. 1/1, 2/2, 3/3, ... are all the same rational, and likewise for 1/2, 2/4, 3/6, ..., etc. \$\endgroup\$ – r.e.s. May 15 '12 at 3:21
0
\$\begingroup\$

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.

Diagonal traversal of all positive rationals

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.