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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < November 9 ! width="25%" align="center"|<< Oct | November | Dec >> ! width="20%" align="right" |Current desk > |}

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

Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, Template:Sfrac, ...

the subsequence with denominator $q$ ends at position ${\sum }_{i=2}^q\phi (i)$ Template:OEIS, where $\phi$ denotes Euler's totient function. Given the factorization of a number $i$, the value of $\phi (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)

Template:Ping 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)