19
\$\begingroup\$

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\}\$.

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

10 Answers 10

Reset to default
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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 ^
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I was thinking of exactly this when I wrote this comment, but you beat me to it. \$\endgroup\$
    – Bubbler
    Oct 24, 2022 at 22:48
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$
    – Bubbler
    Oct 24, 2022 at 23:15
  • \$\begingroup\$ @Bubbler Thanks for the assist! \$\endgroup\$
    – Jordan
    Oct 24, 2022 at 23:30
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)\$.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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)}")
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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