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