20
\$\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\$ Commented Oct 24, 2022 at 19:17
  • \$\begingroup\$ May I use a float to represent a rational number? \$\endgroup\$ Commented Oct 25, 2022 at 0:10
  • \$\begingroup\$ @Bubbler I'm going to say no. \$\endgroup\$ Commented 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\$ Commented Oct 24, 2022 at 22:48
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$ Commented Oct 24, 2022 at 23:15
  • \$\begingroup\$ @Bubbler Thanks for the assist! \$\endgroup\$ Commented 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\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.