cp's OEIS Frontend

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

%I A038566 #88 Jul 20 2025 13:13:06
%S A038566 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,
%T A038566 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,
%U A038566 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
%N A038566 Numerators in canonical bijection from positive integers to positive rationals <= 1: arrange fractions by increasing denominator then by increasing numerator.
%C A038566 For denominators see A038567.
%C A038566 Row n has length A000010(n).
%C A038566 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.
%C A038566 Also triangle in which n-th row gives phi(n) numbers between 1 and n that are relatively prime to n.
%C A038566 A038610(n) = least common multiple of n-th row. - _Reinhard Zumkeller_, Sep 21 2013
%C A038566 Row n has sum A023896(n). - _Jamie Morken_, Dec 17 2019
%C A038566 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
%D A038566 Richard Courant and Herbert Robbins. What Is Mathematics?, Oxford, 1941, pp. 79-80.
%D A038566 H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.
%D A038566 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 163.
%H A038566 David Wasserman, <a href="/A038566/b038566.txt">Table of n, a(n) for n = 1..100001</a>
%H A038566 Wolfdieter Lang, <a href="/A038566/a038566.pdf">Rows of rationals, n=2..25.</a>
%H A038566 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A038566 <a href="/index/Ra#rational">Index entries for sequences related to enumerating the rationals</a>
%H A038566 <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%F A038566 The n-th "clump" consists of the phi(n) integers <= n and prime to n.
%F A038566 a(n) = A002260(A169581(n)). - _Reinhard Zumkeller_, Dec 02 2009
%F A038566 a(n+1) = A020652(n) for n > 1. - _Georg Fischer_, Oct 27 2020
%e A038566 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.
%e A038566 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]
%e A038566 The beginning of the triangle in which n-th row gives numbers between 1 and n that are relatively prime to n:
%e A038566 n\k 1 2 3  4  5  6  7  8 9 10 11 12 13 14 15 16 17 18
%e A038566 1:  1
%e A038566 2:  1
%e A038566 3:  1 2
%e A038566 4:  1 3
%e A038566 5:  1 2 3  4
%e A038566 6:  1 5
%e A038566 7:  1 2 3  4  5  6
%e A038566 8:  1 3 5  7
%e A038566 9:  1 2 4  5  7  8
%e A038566 10: 1 3 7  9
%e A038566 11: 1 2 3  4  5  6  7  8 9 10
%e A038566 12: 1 5 7 11
%e A038566 13: 1 2 3  4  5  6  7  8 9 10 11 12
%e A038566 14: 1 3 5  9 11 13
%e A038566 15: 1 2 4  7  8 11 13 14
%e A038566 16: 1 3 5  7  9 11 13 15
%e A038566 17: 1 2 3  4  5  6  7  8 9 10 11 12 13 14 15 16
%e A038566 18: 1 5 7 11 13 17
%e A038566 19: 1 2 3  4  5  6  7  8 9 10 11 12 13 14 15 16 17 18
%e A038566 20: 1 3 7  9 11 13 17 19
%e A038566 ... Reformatted. - _Wolfdieter Lang_, Jan 18 2017
%e A038566 ------------------------------------------------------
%p A038566 s := proc(n) local i,j,k,ans; i := 0; ans := [ ]; for j while i<n do for k to j do if gcd(j,k) = 1 then ans := [ op(ans),k ]; i := i+1 fi od od; RETURN(ans); end; s(100);
%t A038566 Flatten[Table[Flatten[Position[GCD[Table[Mod[j, w], {j, 1, w-1}], w], 1]], {w, 1, 100}], 2]
%t A038566 row[n_]:=Select[Range[n],GCD[n,#]==1 &]; Array[row,17]//Flatten (* _Stefano Spezia_, Jul 20 2025 *)
%o A038566 (Haskell)
%o A038566 a038566 n k = a038566_tabf !! (n-1) !! (k-1)
%o A038566 a038566_row n = a038566_tabf !! (n-1)
%o A038566 a038566_tabf=
%o A038566    zipWith (\v ws -> filter ((== 1) . (gcd v)) ws) [1..] a002260_tabl
%o A038566 a038566_list = concat a038566_tabf
%o A038566 -- _Reinhard Zumkeller_, Sep 21 2013, Feb 23 2012
%o A038566 (PARI) first(n)=my(v=List(),i,j);while(i<n,for(k=1,j,if(gcd(j,k)==1, listput(v,k);i++));j++);Vec(v) \\ _Charles R Greathouse IV_, Feb 07 2013
%o A038566 (PARI) row(n) = select(x->gcd(n, x)==1, [1..n]); \\ _Michel Marcus_, May 05 2020
%o A038566 (SageMath)
%o A038566 def aRow(n):
%o A038566     if n == 1: return 1
%o A038566     return [k for k in ZZ(n).coprime_integers(n+1)]
%o A038566 print(flatten([aRow(n) for n in range(1, 18)])) # _Peter Luschny_, Aug 17 2020
%Y A038566 Cf. A020652, A020653, A038566, A038567, A038568, A038569, A000010 (row lengths), A002088, A060837, A071970, A002260.
%Y A038566 A054424 gives mapping to Stern-Brocot tree.
%Y A038566 Row sums give rationals A111992(n)/A069220(n), n>=1.
%Y A038566 A112484 (primes, rows n >=3).
%K A038566 nonn,frac,core,nice,tabf
%O A038566 1,4
%A A038566 _N. J. A. Sloane_
%E A038566 More terms from _Erich Friedman_
%E A038566 Offset corrected by _Max Alekseyev_, Apr 26 2010