Wikipedia:Reference desk/Archives/Mathematics/2021 November 10

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 10

Is there a mapping to the relatively prime rationals?

Given the set of rational numbers strictly between 0 and 1 where the numerator and denominator are relatively prime, is there an easy bijection with the positive integers? Bubba73 ^{You talkin' to me?} 05:36, 10 November 2021 (UTC)

This critically depends on your idea of what is easy. If you take the somewhat obvious enumeration

1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, 5/8, 7/8, 1/9, 2/9, 4/9, 5/9, 7/9, 8/9, ...

the subsequence with denominator $q$ ends at position $\textstyle {\sum _{i{=}2}^{q}\varphi (i)}$ (sequence A002088 in the OEIS), where $\varphi$ denotes Euler's totient function. Given the factorization of a number $i$, the value of $\varphi (i)$ is easily computed.  --Lambiam 09:33, 10 November 2021 (UTC)

Thanks, that is easy enough. I wasn't wanting something like the large Diophantane equation with 26 variables. This is practical. Bubba73 ^{You talkin' to me?} 17:02, 10 November 2021 (UTC)

@Bubba73: You might also be interested in the Calkin–Wilf tree. --JBL (talk) 00:46, 11 November 2021 (UTC)

Yes! (Well, half of it.) Bubba73 ^{You talkin' to me?} 06:26, 11 November 2021 (UTC)

Or the Farey tree, the left half of the Stern–Brocot tree. Both the C–W tree and the S–B tree are dealt with in a functional pearl "Enumerating the rationals",^[1] which can be downloaded here.  --Lambiam 08:47, 11 November 2021 (UTC)

I was looking at the left side of the Calkin-Wilf tree, just take the reciprocal of rationals > 1. That should work. Bubba73 ^{You talkin' to me?} 00:17, 13 November 2021 (UTC)

The Cantor pairing function was historically important, if you are just trying to see that the rationals are countable. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 04:41, 12 November 2021 (UTC)

Good idea, but that includes ones not in lowest terms. Bubba73 ^{You talkin' to me?} 00:23, 13 November 2021 (UTC)