# Enumerate the rationals

The cardinality of the set $$\\mathbb Q\$$ of rational numbers is known to be exactly the same as that of the set $$\\mathbb Z\$$ of integers. This means that it is possible to construct a bijection between these sets—a mapping such that each integer corresponds to exactly one rational number, and vice versa.

Provide such a bijection from $$\\mathbb Z\$$ to $$\\mathbb Q\$$. You may choose to use as the domain any contiguous subset of the integers instead of the whole of $$\\mathbb Z\$$. For example, you could instead choose a domain of $$\\{\cdots,5,6,7\}\$$ (integers $$\\le 7\$$) or $$\\{0,1,2,\cdots\}\$$ (like a 0-indexed infinite list), but not $$\\{1,2,3,5,8,\cdots\}\$$.

• Related: 1 2 3
– att
Oct 24, 2022 at 19:17
• May I use a float to represent a rational number? Oct 25, 2022 at 0:10
• @Bubbler I'm going to say no.
– att
Oct 25, 2022 at 8:10

# Vyxal, 12 bytes

⌊d-‹Ė)1Ḟ:NY‹


Try it Online!

A completely different tactic, using an alternating form of the Calkin-Wilf sequence inspired by Jordan's answer. Append an i if outputting an infinite sequence is not allowed.

       Ḟ    # Generate a sequence...
1     # Starting with 1
-----)      # Each value is the previous value n, put into the following...
⌊           # floor(n)
d          # 2 * floor(n)
-         # n - 2 * floor(n)
‹        # n - 2 * floor(n) - 1
Ė       # 1 / (n - 2 * floor(n) - 1)
Y  # Interleave with
:N   # The sequence negated
‹ # Decrement every term to add a 0


# J, 21 16 bytes

**|1&(1%+-2*|)-~


Attempt This Online!

Uses the Calkin-Wilf generator. The domain is full $$\\mathbb{Z}\$$. f(n) = CalkinWilf(n) and f(-n) = -f(n) for n>=0. The input must be given as a bigint.

**|1&(1%+-2*|)-~    input: n, bigint
|                 abs(n)
&(       )-~    repeat ^ times, starting from bigint zero:
1& 1%+-2*|       1/((1 + x) - 2 * frac(x))
**                  multiply sign(n) to ^


# Ruby, 67 50 bytes

-17 bytes thanks to Bubbler

This is the Calkin-Wilf sequence but mapped to the negative rationals for negative inputs, plus $$\f(0) = 0\$$.

F=->n{n<1?0:(m=F[n-1]
n%2>0?1r/(1-2*m.ceil+m):-m)}


Attempt This Online!

## Ruby, 40 bytes

This is the Calkin-Wilf sequence for positive inputs/outputs only.

F=->n{n<2?1:1r/(2*(m=F[n-1]).floor+1-m)}


Attempt This Online!

• I was thinking of exactly this when I wrote this comment, but you beat me to it. Oct 24, 2022 at 22:48
• 50 bytes Oct 24, 2022 at 23:15
• @Bubbler Thanks for the assist! Oct 24, 2022 at 23:30

# R, 71 66 bytes

f=\(x,n=abs(x))if(n,c(sum(m<-f(n-1))-2*m[2]%%m[1],x/n*m[1]),1:0)


Attempt This Online!

Outputs rational numbers represented as vectors of (denominator, numerator).

# R, 67 bytes

\(x,y=rle(intToBits(2*abs(x)+1))$l)sign(x)*head(c(y[1]-1,y[-1]),-1)  Attempt This Online! Outputs rational numbers represented as continued fractions. Works by calculating element i of the Calkin–Wilf sequence using the run-length encoding of the binary representation of i. # Vyxal, 19 bytes ›"ƛȧ‹*[½₍⌊⌈Uvx∑;÷ȧ"  Try it Online! A mess. Uses the Stern-Brocot sequence and works in theory... Given an integer, outputs a pair of integers. ›" # [n, n+1] ƛ ; # Map to... [ # If .... ȧ‹ # |a| - 1 * # * a ½ # Then take a/2 ₍⌊⌈ # [floor(a/2), ceil(a/2) U # Uniquify (if even, just n/2) vx # Recurse on each ∑ # Sum ÷ȧ" # Take the absolute value of the second.  # Python 3.8 (pre-release), 69 67 bytes -2 bytes from Arnauld f=lambda i,m=1,n=1:i>3and f(i//2,m+i%2*n,n+~i%2*m)or(-~i*2%3*m-m,n)  Try it online! Maps $$\\{1,2,\ldots,\}\$$. Represents fractions as pairs of integers; $$\0\$$ represented as $$\(0,1)\$$. # PARI/GP, 44 bytes f(n)=if(n<0,-f(-n),n,(1+f(n\2)^q=n%2*2-1)^q)  Attempt This Online! Using the Calkin-Wilf sequence like other answers. ## PARI/GP, 47 bytes n->t=0;[t=(1+t^q--)^q|q<-2*binary(n)];t*sign(n)  Attempt This Online! Starting from $$\t=0\$$. For each binary digit of the input $$\n\$$, take $$\t=t+1\$$ if the digit is $$\1\$$, and $$\t=\frac{t}{t+1}\$$ if the digit is $$\0\$$. Finally multiply the result with $$\\operatorname{sign}(n)\$$. ## PARI/GP, 47 bytes n->for(i=!t=0,abs(n),t=1/(1-t+t\1*2));t*sign(n)  Attempt This Online! # Charcoal, 37 bytes ＮθＦ²⊞υιＦ↔θ⊞υ⁻Σ…⮌υ²⊗﹪§υ±²↨υ⁰‹θ⁰⪫⮌…⮌υ²/  Try it online! Link is to verbose version of code. Explanation: Port of my JavaScript answer to Output the nth rational number according to the Stern-Brocot sequence. Ｎθ  Input n. Ｆ²⊞υι  Start with 0/1. Ｆ↔θ  Repeat |n| times. ⊞υ⁻Σ…⮌υ²⊗﹪§υ±²↨υ⁰  Calculate the next term of the sequence. ‹θ⁰  Output a - if the input was negative. ⪫⮌…⮌υ²/  Output the last two terms of the sequence, joined with /. Alternative implementation, also 37 bytes: Ｎθ≔¹η≔⁰ζＦ↔θ«≔⁻⁺ζη⊗﹪ζηε≔ηζ≔εη»‹θ⁰Ｉζ/Ｉη  Try it online! Link is to verbose version of code. Explanation: Ｎθ  Input n. ≔¹η≔⁰ζ  Start with 0/1. Ｆ↔θ«  Repeat |n| times. ≔⁻⁺ζη⊗﹪ζηε  Calculate the next term of the sequence. ≔ηζ≔εη  Shuffle the terms into the desired variables. »‹θ⁰  Output a - if the input was negative. Ｉζ/Ｉη  Output the current two terms, separated by /. # Retina 0.8.2, 61 bytes \d+$*#/1
+#(?=1*/(1+))(\1*)(1*)/\3(1+)
$1/$2$4 ^/ 0/ 1+$.&


Try it online! Link includes test cases. Explanation: Another port of my JavaScript answer to Output the nth rational number according to the Stern-Brocot sequence.

\d+
$*#/1  Convert the absolute value of n to unary using #s, then append /1 representing 0/1 in unary. +#(?=1*/(1+))(\1*)(1*)/\3(1+)  Match and consume one # each time, so that the replacement happens n times; look ahead and capture b as $1 so that a-a%b and a%b can be calculated as $2 and $3, and therefore also b-a%b as $4. $1/$2$4


Replace a with b and b with a-a%b+b-a%b i.e. a+b-a%b*2.

^/
0/


Special case 0/, since 0 in unary is the empty string.

1+
\$.&


Convert to decimal.

# Python, 207 bytes.

$$\ \text{207 bytes, it can be golfed much more.} \$$

Golfed version. Try it online!

from fractions import Fraction as F
def g(n):
if n < 1:
return 0
else:
m = g(n-1)
if n % 2 > 0:
return F(1, (1 - 2*int(m) + m))
else:
return -m


Ungolfed version. Try it online!

from fractions import Fraction

def F(n):
if n < 1:
return 0
else:
m = F(n-1)
if n % 2 > 0:
return Fraction(1, (1 - 2*int(m) + m))
else:
return -m

for i in range(101):
print(f"{i} => {F(i)}")