A020653 -id:A020653 - 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);

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

A111992 Numerators of row sums of array of rationals A038566(n)/A020653(n), n>=2.

Original entry on oeis.org

1, 5, 10, 77, 26, 223, 988, 3909, 748, 55991, 5084, 785633, 124658, 207061, 1096792, 29889983, 1893246, 197698279, 85352744, 154834887, 47589202, 325333835, 1188897016, 7612795845, 5775510652, 183259245573, 33778670612

Offset: 2

Wolfdieter Lang, Sep 12 2005

Denominators are given by A069220.

See the W. Lang link under A038566 for the rationals and more.

			Rationals a(n)/A038566(n): [1, 5/2, 10/3, 77/12, 26/5, 223/20,
988/105, 3909/280, 748/63, 55991/2520,...]

a(n)=numerator(sum(r(n, k), k=1..phi(n))), with phi(n)=A000010(n) (Euler's totient function) and r(n, k):=A038566(n,k)/A020653(n,k), n>=2, if A020653 is read as an irregular triangle.

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

A020652 Numerators in canonical bijection from positive integers to positive rationals.

Original entry on oeis.org

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, 1, 5

Offset: 1

David W. Wilson

a(A002088(n)) = 1 for n > 1. - Reinhard Zumkeller, Jul 29 2012
When read as an irregular table with each 1 entry starting a new row, then the n-th row consists of the set of multiplicative units of Z_{n+1}. These rows form a group under multiplication mod n. - Tom Edgar, Aug 20 2013
The pair of sequences A020652/A020653 is defined by ordering the positive fractions p/q (reduced to lowest terms) by increasing p+q, then increasing p: 1/1; 1/2, 2/1; 1/3, 3/1; 1/4, 2/3, 3/2, 4/1; 1/5, 5/1; 2/5, 3/4, 4/3, 5/2; etc. For given p+q, there are A000010(p+q) fractions, listed starting at index A002088(p+q-1). - M. F. Hasler, Mar 06 2020

			Arrange positive fractions < 1 by increasing denominator then by increasing numerator: 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6 ... (this is A020652/A038567). - _William Rex Marshall_, Dec 16 2010

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.
Richard Courant and Herbert Robbins. What Is Mathematics?, Oxford, 1941, pp. 79-80.
H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

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

Essentially the same as A038566, which is the main entry for this sequence.
Cf. A020653, A038567-A038569, A182972-A182976.
A054424 gives mapping to Stern-Brocot tree.
Cf. A037161.

a020652 n = a020652_list !! (n-1)
a020652_list = map fst [(u,v) | v <- [1..], u <- [1..v-1], gcd u v == 1]
-- Reinhard Zumkeller, Jul 29 2012

with (numtheory): A020652 := 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 (j-1): end: # Ulrich Schimke (ulrschimke(AT)aol.com), Nov 06 2001

Reap[Do[If[GCD[num, den] == 1, Sow[num]], {den, 1, 20}, {num, 1, den-1}] ][[2, 1]] (* Jean-François Alcover, Oct 22 2012 *)

a(n)=my(s,j=1,k=1);while(sCharles R Greathouse IV, Feb 07 2013

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

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

See A020652/A020653 for an alternative version where the fractions p/q are listed by increasing p+q, then p. - M. F. Hasler, Nov 25 2021

			First arrange the positive fractions p/q <= 1 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).
Now follow each but the first term by its reciprocal:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, ... (this is A038568/A038569).

H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

Cf. A038566, A038567, A038568.

See A020652, A020653 for an alternative version.

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

a[n_] := Module[{s = 1, k = 2, j = 1}, While[s <= n, s = s + 2*EulerPhi[k]; k = k+1]; s = s - 2*EulerPhi[k-1]; While[s <= n, If[GCD[j, k-1] == 1, s = s+2]; j = j+1]; If[s > n+1, k-1, j-1]]; Table[a[n], {n, 0, 99}](* Jean-François Alcover, Nov 10 2011, after Maple *)

a(n) = { my (e); for (q=1, oo, if (n+1<2*e=eulerphi(q), for (p=1, oo, if (gcd(p,q)==1, if (n+1<2, return ([q,p][n+2]), n-=2))), n-=2*e)) } \\ Rémy Sigrist, Feb 25 2021

from sympy import totient, gcd
def a(n):
    s=1
    k=2
    while s<=n:
        s+=2*totient(k)
        k+=1
    s-=2*totient(k - 1)
    j=1
    while s<=n:
        if gcd(j, k - 1)==1: s+=2
        j+=1
    if s>n + 1: return k - 1
    return j - 1 # Indranil Ghosh, May 23 2017, translated from Mathematica

More terms from Erich Friedman

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

A071974 Numerator of rational number i/j such that Sagher map sends i/j to n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 1, 5, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 4, 7, 5, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 8, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 5, 2, 1, 1, 1, 4, 9, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 7, 3, 10, 1, 1, 1, 1

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 is multiplicative.

			The Sagher map sends the following fractions to 1, 2, 3, 4, ...: 1/1, 1/2, 1/3, 2/1, 1/5, 1/6, 1/7, 1/4, 3/1, ...

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
David M. Bradley, Counting the Positive Rationals: A Brief Survey, arXiv:math/0509025 [math.HO], 2005.
Gerald Freilich, A denumerability formula for the rationals, Amer. Math. Monthly, Nov 1965, pp. 1013-1014.
Kevin McCrimmon, Enumeration of the positive rationals, Amer. Math. Monthly, Nov 1960, p. 868.
Vaclav Kotesovec, Graph - the asymptotic ratio (10000 terms)
Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.
Index entries for sequences related to enumerating the rationals

Cf. A071975. Differs from A056622 at a(32).
Cf. A000290, A027748, A077591, A124010, A350388.
For other bijective mappings from integers to positive rationals see A002487, A020652/A020653, A038568/A038569, A229994/A077610, A295515.
Cf. A307868.

a071974 n = product $ zipWith (^) (a027748_row n) $
   map (\e -> (1 - e `mod` 2) * e `div` 2) $ a124010_row n
-- Reinhard Zumkeller, Jun 15 2012

f[{p_, a_}] := If[EvenQ[a], p^(a/2), 1]; a[n_] := Times@@(f/@FactorInteger[n])
Table[Sqrt@ SelectFirst[Reverse@ Divisors@ n, And[IntegerQ@ Sqrt@ #, CoprimeQ[#, n/#]] &], {n, 104}] (* Michael De Vlieger, Dec 06 2018 *)

a(n)=local(v=factor(n)~); prod(k=1,length(v),if(v[2,k]%2,1,v[1,k]^(v[2,k]/2)))

from math import prod
from sympy import factorint
def A071974(n): return prod(p**(e>>1) for p, e in factorint(n).items() if e&1^1) # Chai Wah Wu, Jul 27 2024

If n=Product p_i^e_i, then a_n=Product p_i^f(e_i), where f(n)=n/2 if n is even and f(n)=0 if n is odd. - Reiner Martin, Jul 08 2002
a(n^2) = n, A071975(n^2) = 1, cf. A000290; a(2*(2*n-1)^2) = 2*n+1, A071975(2*(2*n-1)^2) = 2, cf. A077591. - Reinhard Zumkeller, Jul 10 2011
From Amiram Eldar, Nov 02 2023, Jul 26 2024: (Start)
a(n) = sqrt(A350388(n)) (square root of largest unitary divisor of n that is a square).
Dirichlet g.f.: zeta(2*s) * zeta(2*s-1) * Product_{p prime} (1 + 1/p^s - 1/p^(2*s) - 1/p^(3*s-1)). (End)
From Vaclav Kotesovec, May 05 2025: (Start)
Let f(s) = Product_{p prime} (1 -  (p^s + p)/((p^s + 1)*p^(2*s))).
Dirichlet g.f.: zeta(s) * zeta(2*s-1) * f(s).
Sum_{k=1..n} a(k) ~ f(1) * n * (log(n) + 3*gamma - 1 + f'(1)/f(1)) / 2, where
f(1) = A307868 = Product_{p prime} (1 - 2/(p*(1+p))) = 0.4716806136129978680752356330804820874259263820069868836357372554177321...
f'(1) = f(1) * Sum_{p prime} (5*p+3)*log(p) / ((p+1)*(p^2+p-2)) = f(1) * 2.1244279471327068377850377690765768532203174482128717024402373817115555...
and gamma is the Euler-Mascheroni constant A001620. (End)

More terms from Reiner Martin, Jul 08 2002

Additional references supplied by Kevin Ryde added by N. J. A. Sloane, May 31 2012

A038568 Numerators in canonical bijection from positive integers to positive rationals.

Original entry on oeis.org

1, 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, 1, 10, 3, 10, 7, 10, 9, 10, 1, 11, 2, 11, 3, 11, 4, 11, 5, 11, 6, 11, 7, 11, 8, 11, 9, 11, 10, 11, 1, 12, 5, 12, 7, 12, 11, 12, 1, 13, 2

Offset: 0

N. J. A. Sloane

Even-indexed terms are positive integers in order, with m occurring phi(m) times. Preceding odd-indexed terms (except for missing initial 0) are the corresponding numbers <= m and relatively prime to m, in increasing order. The denominators are just this sequence shifted left. Thus each positive rational occurs exactly once as a ratio a(n)/a(n+1). - Franklin T. Adams-Watters, Dec 06 2006

			First 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);
now follow each term (except the first) with its reciprocal:
1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, ... (this is A038568/A038569).

H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

Cf. A020652, A020653, A038566, A038567, A038569.

using Nemo
function A038568List(len)
    a, A = QQ(0), []
    for n in 1:len
        a = next_minimal(a)
        push!(A, numerator(a))
    end
A end
A038568List(84) |> println # Peter Luschny, Mar 13 2018

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

a[n_] := Module[{sum = 1, k = 2}, While[sum < n, sum = sum + 2*EulerPhi[k]; k = k+1]; sum = sum - 2*EulerPhi[k-1]; j = 1; While[sum < n, If[GCD[j, k-1] == 1, sum = sum+2]; j = j+1; ]; If[sum > n, Return[j-1]]; Return[k-1] ]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 21 2012, translated from Maple *)

a(n) = { my (e); for (q=1, oo, if (n+1<2*e=eulerphi(q), for (p=1, oo, if (gcd(p,q)==1, if (n+1<2, return ([p,q][n+2]), n-=2))), n-=2*e)) } \\ Rémy Sigrist, Feb 25 2021

from sympy import totient, gcd
def a(n):
    s=1
    k=2
    while sn: return j - 1
    return k - 1 # Indranil Ghosh, May 23 2017, translated from Mathematica

More terms from Erich Friedman

A048705 The rule numbers for 1-D CA composed of Rules "90" and "150" so that each direction occurs only once.

Original entry on oeis.org

90, 150, 1721342310, 140117185019831836588493434554119984790, 113427455640312821160607117168492587690

Offset: 1

Antti Karttunen, Mar 09 1999

nonn

The "numerator" (0, 1 and the rest from A020652) is the multiplicity of the "Rule 150" component and the "denominator" (1, 0 and the rest from A020653) is the multiplicity of the "Rule 90" component.
The resulting numbers define one-dimensional linear cellular automata with radius being the sum of the number of the "90" and "150" components.
In hexadecimal the sequence is 5A, 96, 66999966, 69699696969669699696696969699696, 5555555555555555AAAAAAAAAAAAAAAA, ...

Index entries for sequences related to cellular automata

A048706 gives the corresponding "XOR-conjugate" rules.

Cf. A038183, A038184, A048709 (for specific examples). See also A048708, A048720.

# The definitions of bit_i and floor_log_2 are given in A048700
rule90 := proc(seed,n) option remember: local sl, i: if (0 = n) then (seed) else sl := floor_log_2(seed+1); add(((bit_i(rule90(seed,n-1),i)+bit_i(rule90(seed,n-1),i-2)) mod 2)*(2^i), i=0..(2*n)+sl) fi: end:
rule150 := proc(seed,n) option remember: local sl, i: if (0 = n) then (seed) else sl := floor_log_2(seed+1);
add(((bit_i(rule150(seed,n-1),i)+bit_i(rule150(seed,n-1),i-1)+bit_i(rule150(seed,n-1),i-2)) mod 2)*(2^i), i=0..((2*n)+sl)) fi: end:
# Rule 90 and Rule 150 are commutative in respect to each other:
rule90x150combination := proc(n) local p,q,i; p := extended_A020652[ n ]; # the Rule 150 component [ 0,1,op(A020652) ]
q := extended_A020653[ n ]; # the Rule 90 component [ 1,0,op(A020653) ]
RETURN(sum('bit_i(rule150(rule90(i,q),p),(2*(p+q))) * (2^i)','i'=0..(2^((2*(p+q))+1))-1));
end:

a(n) = rule90x150combination(n) # See the Maple procedures below.

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

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

A111992 Numerators of row sums of array of rationals A038566(n)/A020653(n), n>=2.

Views

Author

Keywords

Comments

Examples

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A020652 Numerators in canonical bijection from positive integers to positive rationals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI