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)
- 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)
- 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)
- 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)
- 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)
- Yes! (Well, half of it.) Bubba73 You talkin' to me? 06:26, 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)