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

Mathematics desk
< November 9 << Oct | November | Dec >> 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

edit

Is there a mapping to the relatively prime rationals?

edit

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)[reply]

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   ends at position   (sequence A002088 in the OEIS), where   denotes Euler's totient function. Given the factorization of a number  , the value of   is easily computed.  --Lambiam 09:33, 10 November 2021 (UTC)[reply]
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)[reply]
@Bubba73: You might also be interested in the Calkin–Wilf tree. --JBL (talk) 00:46, 11 November 2021 (UTC)[reply]
Yes! (Well, half of it.) Bubba73 You talkin' to me? 06:26, 11 November 2021 (UTC)[reply]
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)[reply]
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)[reply]

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)[reply]

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