A020652 -id:A020652 - cp's OEIS frontend

A054424 Permutation of natural numbers: maps the canonical list of fractions (A020652/A020653) to whole Stern-Brocot (Farey) tree (top = 1/1 and both sides < 1 and > 1, but excluding the "fractions" 0/1 and 1/0).

1, 2, 3, 4, 7, 8, 5, 6, 15, 16, 31, 32, 9, 11, 12, 14, 63, 64, 10, 13, 127, 128, 17, 23, 24, 30, 255, 256, 19, 28, 511, 512, 33, 18, 20, 47, 48, 27, 29, 62, 1023, 1024, 22, 25, 2047, 2048, 65, 35, 39, 21, 95, 96, 26, 56, 60, 126, 4095, 4096, 34, 40, 55, 61, 8191, 8192

Offset: 1

Antti Karttunen

nonn

			Whole Stern-Brocot tree: 1/1 1/2 2/1 1/3 2/3 3/2 3/1 1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1 1/5 2/7
Canonical fractions: 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

Cf. A047679, A007305, A007306, A054427, A057114. In table form: A054425. Inverse permutation: A054426.

cfrac2binexp := proc(c) local i,e,n; n := 0; for i from 1 to nops(c) do e := c[i]; if(i = nops(c)) then e := e-1; fi; n := ((2^e)*n) + ((i mod 2)*((2^e)-1)); od; RETURN(n); end;
frac2position_in_whole_SB_tree := proc(r) local k,msb; if(1 = r) then RETURN(1); else if(r > 1) then k := cfrac2binexp(convert(r,confrac)); else k := ReflectBinTreePermutation(cfrac2binexp(convert(1/r,confrac))); fi; msb := floor_log_2(k); if(r > 1) then RETURN(k + (2^(msb+1))); else RETURN(k + (2^(msb+1)) - (2^msb)); fi; fi; end;
canonical_fractions_to_whole_SternBrocot_permutation := proc(u) local a,n,i; a := []; for n from 2 to u do for i from 1 to n-1 do if (1 = igcd(n,i)) then a := [op(a),frac2position_in_whole_SB_tree(i/(n-i))]; fi; od; od; RETURN(a); end; # ReflectBinTreePermutation and floor_log_2 given in A054429

canonical_fractions_to_whole_SternBrocot_permutation(30);

A182976 Denominators of fractions with the same position in A020652/A038567 and A182972/A182973.

Original entry on oeis.org

2, 3, 5, 23, 73, 143, 163, 235, 477, 1238, 4175, 4641, 7820, 11217, 25915, 37643, 95299, 576088, 1203677

Offset: 1

William Rex Marshall, Dec 16 2010

The positions of the matching fractions are given in A182974.
The numerators of the matching fractions are given in A182975.
The initial (zeroth) term of A038567 is ignored.

			The matching fractions are 1/2, 1/3, 2/5, 9/23, 30/73, 59/143 ... (this is A182975/A182976).

S. Cook, Problem 511: An Enumeration Problem, Journal of Recreational Mathematics, Vol. 9:2 (1976-77), 137. Solution by the Problem Editor, JRM, Vol. 10:2 (1977-78), 122-123.

Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.

Cf. A020652, A038567, A182972-A182975.

A182974 Numbers n for which A020652(n)/A038567(n) = A182972(n)/A182973(n).

Original entry on oeis.org

1, 2, 7, 158, 1617, 6211, 8058, 16765, 69093, 465988, 5297983, 6546724, 18588348, 38244610, 204136352, 430712111, 2760559191, 100878516991, 440393924631

Offset: 1

William Rex Marshall, Dec 16 2010

Numerators of the matching fractions are given in A182975.
Denominators of the matching fractions are given in A182976.
The initial (zeroth) term of A038567 is ignored.

			a(1)=1, a(2)=2 and a(3)=7 because the 1st, 2nd and 7th fractions match in the following two sequences:
1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5 ... (A020652/A038567)
1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5, 3/4 ... (A182972/A182973)

S. Cook, Problem 511: An Enumeration Problem, Journal of Recreational Mathematics, Vol. 9:2 (1976-77), 137. Solution by the Problem Editor, JRM, Vol. 10:2 (1977-78), 122-123.

Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.

Cf. A020652, A038567, A182972, A182973, A182975, A182976.

A182975 Numerators of fractions with the same position in A020652/A038567 and A182972/A182973.

Original entry on oeis.org

1, 1, 2, 9, 30, 59, 67, 97, 197, 513, 1729, 1922, 3239, 4646, 10734, 15592, 39474, 238623, 498579

Offset: 1

William Rex Marshall, Dec 16 2010

The positions of the matching fractions are given in A182974.
The denominators of the matching fractions are given in A182976.
The initial (zeroth) term of A038567 is ignored.

			The matching fractions are 1/2, 1/3, 2/5, 9/23, 30/73, 59/143 ... (this is A182975/A182976).

S. Cook, Problem 511: An Enumeration Problem, Journal of Recreational Mathematics, Vol. 9:2 (1976-77), 137. Solution by the Problem Editor, JRM, Vol. 10:2 (1977-78), 122-123.

Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.

Cf. A020652, A038567, A182972-A182974, A182976.

A060837 List the positive rationals in the canonical order A020652(n)/A020653(n) and apply the Sagher map to turn them into integers.

Original entry on oeis.org

1, 2, 4, 3, 9, 8, 12, 18, 16, 5, 25, 6, 20, 72, 48, 50, 36, 7, 45, 75, 49, 32, 28, 80, 200, 98, 64, 27, 63, 147, 81, 10, 108, 288, 112, 150, 180, 392, 192, 162, 100, 11, 175, 245, 121, 24, 44, 90, 432, 800, 252, 294, 320, 648, 300, 242, 144, 13, 99, 675, 405, 363, 169, 14

Offset: 1

N. J. A. Sloane, Jun 19 2002

The Sagher map sends Product p_i^e_i / Product q_i^f_i (p_i and q_i being distinct primes) to Product p_i^(2e_i) * Product q_i^(2f_i-1). This map is multiplicative.

			The first few rationals and their images are 1/1 -> 1, 1/2 -> 2, 2/1 -> 4, 1/3 -> 3, 3/1 -> 9, 1/4 -> 8, ...

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Y. Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Cf. A038566, A071970.

a060837 n = (a020652 n ^ 2) *
   product (zipWith (^) (a027748_row m)
                        (map ((subtract 1) . (* 2)) (a124010_row m)))
   where m = a020653 n
-- Reinhard Zumkeller, Feb 16 2014

a(n) = A020652(n)^2 * product(A027748(m,k)^(2*A124010(m,k)-1): m=a020653(n), k=1..A000005(m)). - Reinhard Zumkeller, Feb 16 2014

More terms from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jan 12 2003
Corrected by Charles R Greathouse IV, Sep 02 2009
Definition slightly changed by Reinhard Zumkeller, Feb 16 2014

A341864 Least increasing sequence of primes a(n) == A020652(n) (mod A038567(n)).

Original entry on oeis.org

3, 7, 11, 13, 19, 31, 37, 43, 59, 61, 71, 113, 149, 157, 179, 229, 251, 257, 283, 293, 311, 379, 389, 409, 419, 421, 431, 461, 463, 467, 479, 617, 673, 751, 829, 863, 919, 953, 1009, 1021, 1033, 1069, 1097, 1123, 1151, 1171, 1237, 1277, 1291, 1409, 1423, 1489, 1607, 1621, 1973, 1987, 2027, 2087

Offset: 1

J. M. Bergot and Robert Israel, Feb 22 2021

nonn

A020652/A038567 is an enumeration of the fractions < 1 (in lowest terms) arranged by increasing denominator and then increasing numerator.

a(n) is the least prime > a(n-1) congruent to A020652(n) (mod A038567(n)).

			a(5) = 19 == A020652(5) = 3 (mod A038567(5) = 4) and is the least prime > a(4) = 13 with this property.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A020652, A038567.

N:= 100: # for a(1)..a(N)
A:=Vector(N): A[1]:= 3: n:= 1:
for d from 3 while n < N do
  for m from 1 to d-1 while n < N do
    if igcd(m,d)=1 then
      n:= n+1;
      for k from ceil((A[n-1]+1 - m)/d) do
        q:= d*k+m;
        if isprime(q) then A[n]:= q; break fi
      od
    fi
od od:
convert(A,list);

A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k), cf. A000010.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 12, 18, 22, 28, 32, 42, 46, 58, 64, 72, 80, 96, 102, 120, 128, 140, 150, 172, 180, 200, 212, 230, 242, 270, 278, 308, 324, 344, 360, 384, 396, 432, 450, 474, 490, 530, 542, 584, 604, 628, 650, 696, 712, 754, 774, 806, 830, 882, 900, 940, 964

Offset: 0

N. J. A. Sloane

Number of elements in the set {(x,y): 1 <= x <= y <= n, 1=gcd(x,y)}. - Michael Somos, Jun 13 1999
Sum_{k=1..n} phi(k) gives the number of distinct arithmetic progressions which contain an infinite number of primes and whose difference does not exceed n. E.g., {1k+1}, {2k+1}, {3k+1, 3k+2}, {4k+1, 4k+3}, {5k+1, ..5k+4} means 10 sequences. - Labos Elemer, May 02 2001
The quotient A024916(n)/a(n) = SummatorySigma/SummatoryTotient as n increases seems to approach Pi^4/36 = zeta(2)^2 = A098198 ~2.705808084277845. - Labos Elemer, Sep 20 2004 (corrected by Peter Pein, Apr 28 2009)
Also the number of rationals p/q in (0,1] with denominators q<=n. - Franz Vrabec, Jan 29 2005
a(n) is the number of initial segments of Beatty sequences for real numbers > 1, cut off when the next term in the sequence would be >= n. For example, the sequence 1,2 is included for n=3 and n=4, but not for n >= 5 because the next term of the Beatty sequence must be 3 or 4. Problem suggested by David W. Wilson. - Franklin T. Adams-Watters, Oct 19 2006
Number of complex numbers satisfying any one of {x^1=1, x^2=1, x^3=1, x^4=1, x^5=1, ..., x^n=1}. - Paul Smith (math.idiot(AT)gmail.com), Mar 19 2007
a(n+2) equals the number of Sturmian words of length n which are 'special', prefix of two Sturmian words of length n+1. - Fred Lunnon, Sep 05 2010
For n > 1: A020652(a(n)) = 1 and A038567(a(n)) = n; for n > 0: A214803(a(n)) = 1. - Reinhard Zumkeller, Jul 29 2012
Also number of elements in the set {(x,y): 1 <= x + y <= n, x >= 0, y > 0, with x and y relatively prime integers}. Thus, the number of reduced rational numbers x/y with x nonnegative, y positive, and x + y <= n. (For n >= 1, 0 <= x/y <= n - 1, clearly including each integer in this interval.) - Rick L. Shepherd, Apr 08 2014
This function, the partial sums of phi = A000010, is sometimes denoted by (uppercase) Phi. - M. F. Hasler, Apr 18 2015
From Roger Ford, Jan 16 2016: (Start)
For n >= 1: a(n) is the number of perfect arched semi-meander solutions with n arches. To be perfect the number of arch groupings must equal the number of arches with a length of 1 in the current generation and every preceding generation.
Example:  p is the number of arches with length 1 (/\),  g is the number of arch groups (-),  n is number of arches in the top half of a semi-meander solution
                 /\
        /\      //\\
       //\\-/\-///\\\-  n=6 p=3 g=3   Each preceding arch configuration
            /\   /\                   is formed by attaching the arch
        /\-//\\-//\\-   n=5 p=3 g=3   end in the first position and the
           /\                         arch end in the last position.
          //\\
         ///\\\-/\-     n=4 p=2 g=2
           /\
          //\\-/\-      n=3 p=2 g=2
           /\-/\-       n=2 p=2 g=2
            /\-         n=1 p=1 g=1. (End)
a(n) is the number of distinct lists of binary words of length n that are balanced (Sturmian). - Dan Rockwell, Will Wodrich, Aaliyah Fiala, and Bob Burton, May 30 2019
2013 IMO Problem 6 shows that a(n) is the number of ways to arrange the numbers 0, 1, ..., n on a circle such that for any numbers 0 <= a < b < c < d <= n, the chord joining a and d does not intersect with the chord intersecting b and c, with rotation counted as same. - Yifan Xie, Aug 26 2025

			G.f. = x + 2*x^2 + 4*x^3 + 6*x^4 + 10*x^5 + 12*x^6 + 18*x^7 + 22*x^8 + 28*x^9 + ...

A. Beiler, Recreations in the Theory of Numbers, Dover Publications, 1966, Chap. XVI.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 138.
M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972, p. 6.
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section I.21.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 94, Problem 11.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.

Al Zimmermann, Table of n, a(n) for n = 0..50000 (Terms 0 to 1000 by T. D. Noe)
Dorin Andrica, Ovidiu Bagdasar, On some results concerning the polygonal polynomials, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
Art of Problem Solving, 2013 IMO Problem 6.
S. Bockting-Conrad, Y. Kashina, T. K. Petersen, and B. E. Tenner, Sós permutations, arXiv:2007.01132 [math.CO], 2020.
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, and Nithin Varma, Bipartite Graphs of Small Readability, arXiv:1805.04765 [cs.DM], 2018.
Steven R. Finch, Euler Totient Function Asymptotic Constants [Broken link]
Steven R. Finch, Euler Totient Function Asymptotic Constants [From the Wayback machine]
Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler phi function, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008, pp. 34-42.
J. Sandor, D. S. Mitrinovic, B. Crstici, Handbook of Number Theory I, Volume 1, Springer, 2005, p. 24.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
James J. Sylvester, On the number of fractions contained in any Farey series of which the limiting number is given, in: London, Edinburgh and Dublin Philosophical Magazine (5th series) 15 (1883), p. 251 = Collected Mathematical Papers, Vols. 1-4, Cambridge Univ. Press, 1904-1912, Vol. 4, p. 103 (see below).
J. J. Sylvester, The collected mathematical papers of James Joseph Sylvester, vol. 2, vol. 3, vol. 4.
A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin 1963.
Eric Weisstein's World of Mathematics, Totient Function
Eric Weisstein's World of Mathematics, Beatty Sequence.
Eric Weisstein's World of Mathematics, Totient Summatory Function.
R. G. Wilson, v, Letter to N. J. A. Sloane, Jan 24 1989

Cf. A000010, A015614, A005728, A067282, A001088, A134542, A002321.

List([1..60],n->Sum([1..n],i->Phi(i))); # Muniru A Asiru, Jul 31 2018

a002088 n = a002088_list !! n
a002088_list = scanl (+) 0 a000010_list -- Reinhard Zumkeller, Jul 29 2012

[&+[EulerPhi(i): i in [1..n]]: n in [1..60]]; // Vincenzo Librandi, Aug 01 2018

with(numtheory): A002088:=n->add(phi(i),i=1..n): seq(A002088(n), n=0..70);

Table[Plus @@ EulerPhi[Range[n]], {n, 0, 57}] (* Alonso del Arte, May 30 2006 *)
Accumulate[EulerPhi[Range[0,60]]] (* Harvey P. Dale, Aug 27 2011 *)

a(n)=sum(k=1,n,eulerphi(k)) \\ Charles R Greathouse IV, Jun 16 2011

a(n)=my(s=1); forsquarefree(k=1,n,s+=(n\k[1])^2*moebius(k)); s/2 \\ Charles R Greathouse IV, Oct 15 2021

first(n)=my(v=vector(n),s); forfactored(k=1,n, v[k[1]]=s+=eulerphi(k)); v \\ Charles R Greathouse IV, Oct 15 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A002088(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A002088(k1)-1)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

[sum(euler_phi(k) for k in (1..n)) for n in (0..60)] # G. C. Greubel, Nov 25 2018

a(n) = (3*n^2)/(Pi^2) + O(n log n).
More precisely, a(n) = (3/Pi^2)*n^2 + O(n*(log(n))^(2/3)*(log(log(n)))^(4/3)), (A. Walfisz 1963). - Benoit Cloitre, Feb 02 2003
a(n) = (1/2)*Sum_{k>=1} mu(k)*floor(n/k)*floor(1+n/k). - Benoit Cloitre, Apr 11 2003
a(n) = A000217(n) - A063985(n) = A018805(n) - A015614(n). - Reinhard Zumkeller, Jan 21 2013
A slightly simpler version of Cloitre's formula is a(n) = 1/2 + Sum_{k=1..oo} floor(n/k)^2*mu(k)/2. - Bill Gosper, Jul 25 2020
The quotient A024916(n)/a(n) = SummatorySigma/SummatoryTotient as n increases seems to approach (Pi^4)/36 = Zeta(2)^2 = 2.705808084277845. See also A067282. - Labos Elemer, Sep 21 2004
A024916(n)/a(n) = zeta(2)^2 + O(log(n)/n). This follows from asymptotic formulas for the sequences. - Franklin T. Adams-Watters, Oct 19 2006
Row sums of triangle A134542. - Gary W. Adamson, Oct 31 2007
G.f.: (Sum_{n>=1} mu(n)*x^n/(1-x^n)^2)/(1-x), where mu(n) = A008683(n). - Mamuka Jibladze, Apr 06 2015
a(n) = A005728(n) - 1, for n >= 0. - Wolfdieter Lang, Nov 22 2016
a(n) = (Sum_{k=1..floor(sqrt(n))} k*(k+1) * (M(floor(n/k)) - M(floor(n/(k+1)))) + Sum_{k=1..floor(n/(1+floor(sqrt(n))))} mu(k) * floor(n/k) * floor(1+n/k))/2, where M(k) is the Mertens function (A002321) and mu(k) is the Moebius function (A008683). - Daniel Suteu, Nov 23 2018
a(n) = A015614(n)+1. - R. J. Mathar, Apr 26 2023
a(n) = A000217(n) - Sum{k=2..n} a(floor(n/k)). From summing over Id = 1 (Dirichlet convolution) phi. - Jason Xu, Jul 31 2024
a(n) = Sum_{k=1..n} k*A002321(floor(n/k)). - Ridouane Oudra, Jul 03 2025

Additional comments from Len Smiley

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

Original entry on oeis.org

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

N. J. A. Sloane

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

			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
------------------------------------------------------

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.

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

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).

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

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

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 *)

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

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

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

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

More terms from Erich Friedman

Offset corrected by Max Alekseyev, Apr 26 2010

A038567 Denominators in canonical bijection from positive integers to positive rationals <= 1.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

n occurs phi(n) times (cf. A000010).
Least k such that phi(1) + phi(2) + phi(3) + ... + phi(k) >= n. - Benoit Cloitre, Sep 17 2002
Sum of numerator and denominator of fractions arranged by Cantor's ordering (1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1, 6/1, ...) with equivalent fractions removed. - Ron R. King, Mar 07 2009 [This applies to a(1, 2, ...) without initial term a(0) = 1 which could correspond to 0/1. - Editor's Note.]
Care has to be taken in considering the offset which may be 0 or 1 in related sequences (see crossrefs), e.g., A038568 & A038569 also have offset 0, in A038566 offset has been changed to 1. - M. F. Hasler, Oct 18 2021

			Arrange fractions by increasing denominator then by increasing numerator: 1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, ...: this is A038566/A038567.

S. Cook, Problem 511: An Enumeration Problem, Journal of Recreational Mathematics, Vol. 9:2 (1976-77), 137. Solution by the Problem Editor, JRM, Vol. 10:2 (1977-78), 122-123.
Hans Lauwerier, Fractals, Princeton University Press, 1991, p. 23.

David Wasserman, Table of n, a(n) for n = 0..100000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633. [Wayback Machine link]
Index entries for "core" sequences.
Index entries for sequences related to enumerating the rationals.
Index entries for sequences related to Stern's sequences.

Cf. A020652, A020653, A038566 - A038569, A093602, A182972, A182973 - A182976.
A054427 gives mapping to Stern-Brocot tree.
Cf. A037162.

import Data.List (genericTake)
a038567 n = a038567_list !! n
a038567_list = concatMap (\x -> genericTake (a000010 x) $ repeat x) [1..]
-- Reinhard Zumkeller, Dec 16 2013, Jul 29 2012

with (numtheory): A038567 := proc (n) local sum, k; sum := 1: k := 2: while (sum < n) do: sum := sum + phi(k): k := k + 1: od: RETURN (k-1): end: # Ulrich Schimke (ulrschimke(AT)aol.com)

a[n_] := (k = 0; While[ Total[ EulerPhi[ Range[k]]] <= n, k++]; k); Table[ a[n], {n, 0, 77}] (* Jean-François Alcover, Dec 08 2011, after Pari *)
Flatten[Table[Table[n,{EulerPhi[n]}],{n,20}]] (* Harvey P. Dale, Mar 12 2013 *)

a(n)=if(n<0,0,s=1; while(sum(i=1,s,eulerphi(i))

from sympy import totient
def a(n):
    s=1
    while sum(totient(i) for i in range(1, s + 1))Indranil Ghosh, May 23 2017

from functools import lru_cache
@lru_cache(maxsize=None)
def A002088(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*((A002088(k1)<<1)-1)
        j, k1 = j2, n//j2
    return n*(n-1)-c+j>>1
def A038567(n):
    kmin, kmax = 0, 1
    while A002088(kmax) <= n:
        kmax <<= 1
    kmin = kmax>>1
    while True:
        kmid = kmax+kmin>>1
        if A002088(kmid) > n:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Jun 10 2025

From Henry Bottomley, Dec 18 2000: (Start)
a(n) = A020652(n) + A020653(n) for all n > 0, e.g., a(1) = 2 = 1 + 1 = A020652(1) + A020653(1). [Corrected and edited by M. F. Hasler, Dec 10 2021]
n = a(A015614(n)) = a(A002088(n)) - 1 = a(A002088(n-1)). (End)
a(n) = A002024(A169581(n)). - Reinhard Zumkeller, Dec 02 2009
a(A002088(n)) = n for n > 1. - Reinhard Zumkeller, Jul 29 2012
a(n) = A071912(2*n+1). - Reinhard Zumkeller, Dec 16 2013
a(n) ~ c * sqrt(n), where c = Pi/sqrt(3) = 1.813799... (A093602). - Amiram Eldar, Dec 27 2024

More terms from Erich Friedman

A020653 Denominators in a certain bijection from positive integers to positive rationals.

Original entry on oeis.org

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

Offset: 1

David W. Wilson

This bijection lists the fractions p/q (in lowest terms) by increasing p+q, then by increasing p (see the example). The variant A038569 corresponds to the bijection where each fraction p/q with p < q is followed by its reciprocal q/p. - M. F. Hasler, Oct 25 2021

			From _M. F. Hasler_, Nov 25 2021: (Start)
This sequence gives the denominators of the positive fractions p/q (in lowest terms) when they are listed by increasing p+q, then by increasing p:
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; ...
(End)

Richard Courant and Herbert Robbins. What Is Mathematics?, Oxford, 1941, pp. 79-80.
H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

Cf. A020652, A038566, A038569.

a020653 n = a020653_list !! (n-1)
a020653_list = concat $ map reverse $ tail a038566_tabf
-- Reinhard Zumkeller, Oct 30 2012

with (numtheory): A020653 := proc (n) local sum, j, k; sum := 0: k := 2: while (sum < n) do: sum := sum + phi(k): k := k + 1: od: sum := sum - phi(k-1): j := 1; while sum < n do: if gcd(j,k-1) = 1 then sum := sum + 1: fi: j := j+1: od: RETURN (k-j): end: # Ulrich Schimke (ulrschimke(AT)aol.com), Nov 06 2001

a[n_] := Module[{s=0, k=2}, While [s < n, s = s + EulerPhi[k]; k = k+1]; s = s - EulerPhi[k-1]; j=1; While[s < n , If[GCD[j, k-1] == 1 , s = s+1]; j = j+1]; k-j]; Table[a[n], {n, 1, 96}] (* Jean-François Alcover, Dec 06 2012, after Ulrich Schimke's Maple program *)
Flatten[Map[Denominator[#/Reverse[#]]&,Table[Flatten[Position[GCD[Map[Mod[#,n]&,Range[n-1]],n],1]],{n,100}]]] (* Peter J. C. Moses, Apr 17 2013 *)

a(n) = my(s=0, k=1, j=1); while(sRuud H.G. van Tol, May 14 2024

from sympy import totient, gcd
def a(n):
    s=0
    k=2
    while sIndranil Ghosh, May 23 2017, translated from Ulrich Schimke's MAPLE code

Definition clarified by N. J. A. Sloane, Nov 25 2021

cp's OEIS Frontend

A054424 Permutation of natural numbers: maps the canonical list of fractions (A020652/A020653) to whole Stern-Brocot (Farey) tree (top = 1/1 and both sides < 1 and > 1, but excluding the "fractions" 0/1 and 1/0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A182976 Denominators of fractions with the same position in A020652/A038567 and A182972/A182973.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A182974 Numbers n for which A020652(n)/A038567(n) = A182972(n)/A182973(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A182975 Numerators of fractions with the same position in A020652/A038567 and A182972/A182973.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A060837 List the positive rationals in the canonical order A020652(n)/A020653(n) and apply the Sagher map to turn them into integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Formula

Extensions

A341864 Least increasing sequence of primes a(n) == A020652(n) (mod A038567(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k), cf. A000010.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Sage