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

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

9 Answers 9

5
\$\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
\$\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 ^
\$\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!

\$\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 at 22:48
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$
    – Bubbler
    Oct 24 at 23:15
  • \$\begingroup\$ @Bubbler Thanks for the assist! \$\endgroup\$
    – Jordan
    Oct 24 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.

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

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 37 bytes

NθF²⊞υιF↔θ⊞υ⁻Σ…⮌υ²⊗﹪§υ±²↨υ⁰‹θ⁰⪫⮌…⮌υ²/

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.

Nθ

Input n.

F²⊞υι

Start with 0/1.

F↔θ

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:

Nθ≔¹η≔⁰ζF↔θ«≔⁻⁺ζη⊗﹪ζηε≔ηζ≔εη»‹θ⁰Iζ/Iη

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

≔¹η≔⁰ζ

Start with 0/1.

F↔θ«

Repeat |n| times.

≔⁻⁺ζη⊗﹪ζηε

Calculate the next term of the sequence.

≔ηζ≔εη

Shuffle the terms into the desired variables.

»‹θ⁰

Output a - if the input was negative.

Iζ/Iη

Output the current two terms, separated by /.

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

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