A038566 Numerators in canonical bijection from positive integers to positive rationals <= 1: arrange fractions by increasing denominator then by increasing numerator.

1, 1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 7, 1, 2, 4, 5, 7, 8, 1, 3, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 5, 7, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 3, 5, 9, 11, 13, 1, 2, 4, 7, 8, 11, 13, 14, 1, 3, 5, 7, 9, 11, 13, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• frac
• core
• nice
• tabf

Comments

For denominators see A038567.

Row n has length A000010(n).

Also numerators in canonical bijection from positive integers to all positive rational numbers: arrange fractions in triangle in which in the n-th row the phi(n) numbers are the fractions i/j with gcd(i,j) = 1, i+j=n, i=1..n-1, j=n-1..1. n>=2. Denominators (A020653) are obtained by reversing each row.

Also triangle in which n-th row gives phi(n) numbers between 1 and n that are relatively prime to n.

A038610(n) = least common multiple of n-th row. - Reinhard Zumkeller, Sep 21 2013

Row n has sum A023896(n). - Jamie Morken, Dec 17 2019

This irregular triangle gives in row n the smallest positive reduced residue system modulo n, for n >= 1. If one takes 0 for n = 1 it becomes the smallest nonnegative residue system modulo n. - Wolfdieter Lang, Feb 29 2020

Examples

			The beginning of the list of positive rationals <= 1: 1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, .... This is A038566/A038567.
The beginning of the triangle giving all positive rationals: 1/1; 1/2, 2/1; 1/3, 3/1; 1/4, 2/3, 3/2, 4/1; 1/5, 5/1; 1/6, 2/5, 3/4, 4/3, 5/2, 6/1; .... This is A020652/A020653, with A020652(n) = A038566(n+1). [Corrected by _M. F. Hasler_, Mar 06 2020]
The beginning of the triangle in which n-th row gives numbers between 1 and n that are relatively prime to n:
n\k 1 2 3  4  5  6  7  8 9 10 11 12 13 14 15 16 17 18
1:  1
2:  1
3:  1 2
4:  1 3
5:  1 2 3  4
6:  1 5
7:  1 2 3  4  5  6
8:  1 3 5  7
9:  1 2 4  5  7  8
10: 1 3 7  9
11: 1 2 3  4  5  6  7  8 9 10
12: 1 5 7 11
13: 1 2 3  4  5  6  7  8 9 10 11 12
14: 1 3 5  9 11 13
15: 1 2 4  7  8 11 13 14
16: 1 3 5  7  9 11 13 15
17: 1 2 3  4  5  6  7  8 9 10 11 12 13 14 15 16
18: 1 5 7 11 13 17
19: 1 2 3  4  5  6  7  8 9 10 11 12 13 14 15 16 17 18
20: 1 3 7  9 11 13 17 19
... Reformatted. - _Wolfdieter Lang_, Jan 18 2017
------------------------------------------------------
		

References

• Richard Courant and Herbert Robbins. What Is Mathematics?, Oxford, 1941, pp. 79-80.
• H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.
• James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 163.

Links

• David Wasserman, Table of n, a(n) for n = 1..100001
• Wolfdieter Lang, Rows of rationals, n=2..25.
• Index entries for "core" sequences
• Index entries for sequences related to enumerating the rationals
• Index entries for sequences related to Stern's sequences

Crossrefs

Cf. A020652, A020653, A038566, A038567, A038568, A038569, A000010 (row lengths), A002088, A060837, A071970, A002260.

A054424 gives mapping to Stern-Brocot tree.

Row sums give rationals A111992(n)/A069220(n), n>=1.

A112484 (primes, rows n >=3).

Programs

Haskell

a038566 n k = a038566_tabf !! (n-1) !! (k-1)
a038566_row n = a038566_tabf !! (n-1)
a038566_tabf=
   zipWith (\v ws -> filter ((== 1) . (gcd v)) ws) [1..] a002260_tabl
a038566_list = concat a038566_tabf
-- Reinhard Zumkeller, Sep 21 2013, Feb 23 2012

Maple

s := proc(n) local i,j,k,ans; i := 0; ans := [ ]; for j while i
				

Mathematica

Flatten[Table[Flatten[Position[GCD[Table[Mod[j, w], {j, 1, w-1}], w], 1]], {w, 1, 100}], 2]
row[n_]:=Select[Range[n],GCD[n,#]==1 &]; Array[row,17]//Flatten (* Stefano Spezia, Jul 20 2025 *)

PARI

first(n)=my(v=List(),i,j);while(iCharles R Greathouse IV, Feb 07 2013

PARI

row(n) = select(x->gcd(n, x)==1, [1..n]); \\ Michel Marcus, May 05 2020

SageMath

def aRow(n):
    if n == 1: return 1
    return [k for k in ZZ(n).coprime_integers(n+1)]
print(flatten([aRow(n) for n in range(1, 18)])) # Peter Luschny, Aug 17 2020

Formula

The n-th "clump" consists of the phi(n) integers <= n and prime to n.

a(n) = A002260(A169581(n)). - Reinhard Zumkeller, Dec 02 2009

a(n+1) = A020652(n) for n > 1. - Georg Fischer, Oct 27 2020

Extensions

More terms from Erich Friedman

Offset corrected by Max Alekseyev, Apr 26 2010