A038569 -id:A038569 - cp's OEIS frontend

A173467 Partial sums of A038569.

1, 3, 4, 7, 8, 11, 13, 17, 18, 22, 25, 30, 31, 36, 38, 43, 46, 51, 55, 61, 62, 68, 73, 80, 81, 88, 90, 97, 100, 107, 111, 118, 123, 130, 136, 144, 145, 153, 156, 164, 169, 177, 184, 193, 194, 203, 205, 214, 218, 227, 232, 241, 248, 257, 265, 275, 276, 286, 289, 299

Offset: 0

Jonathan Vos Post, Feb 18 2010

nonn

Cf. A038569.

a(n) = Sum_{i=0..n} A038569(i).

a(37) corrected by Georg Fischer, Aug 29 2020

A340922 a(n) is the position of phi(A038568(n)^2)/phi(A038569(n)^2) in the enumeration of the rationals by A038568 and A038569, where phi is A000010.

Original entry on oeis.org

0, 1, 2, 19, 20, 3, 4, 35, 36, 9, 10, 239, 240, 55, 56, 57, 58, 13, 14, 83, 84, 16, 15, 1059, 1060, 255, 256, 23, 24, 259, 260, 265, 266, 25, 26, 615, 616, 145, 146, 39, 40, 272, 271, 1763, 1764, 423, 424, 427, 428, 435, 436, 51, 52, 443, 444, 947, 948, 241, 242

Offset: 0

Hugo Pfoertner, Feb 19 2021

nonn

			  n                   0   1   2   3    4   5    6    7    8   9    10
  j/k                 1  1/2  2  1/3   3  2/3  3/2  1/4   4  3/4  4/3
  phi(j^2)/phi(k^2)   1  1/2  2  1/6   6  1/3   3   1/8   8  3/4  4/3
  a(n)                0   1   2   19  20   3    4    35  36   9    10
.
  n                  11    12   13    14   15    16    17   18   19   20
  j/k                1/5    5  2/5   5/2  3/5    5/3  4/5  5/4  1/6    6
  phi(j^2)/phi(k^2)  1/20  20  1/10   10  3/10  10/3  2/5  5/2  1/12  12
  a(n)               239  240   55    56   57    58    13   14   83   84

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Hongjian Li, Pingzhi Yuan, and Hairong Bai, Positive Rational Numbers of the Form phi(n^2)/phi(m^2), The American Mathematical Monthly, 128:2 (2021), 174-176.
Rémy Sigrist, PARI program for A340922

Cf. A000010, A038568, A038569.

using Nemo
function A340922List(len)
    num(a) = euler_phi(numerator(a)^2)
    den(a) = euler_phi(denominator(a)^2)
    a, q, A, R = QQ(0), QQ(0), [], Int[]
    for n in 1:len
        q = next_minimal(q)
        x = num(q)//den(q)
        while true
            i = findfirst(isequal(x), A)
            if i == nothing
                a = next_minimal(a)
                push!(A, a)
            else
                push!(R, i - 1)
                break
            end
        end
    end
    R
end
A340922List(59) |> println # Peter Luschny, Feb 19 2021

\\ It is assumed that a38568 and a38569 are available as vectors,
\\ e.g. from the corresponding b-files.
\\ a38568=readvec("[path] a38568"); a38569=readvec("[path] a38569");
findinlist(n,d)={my(num=numerator(n/d),den=denominator(n/d));for(k=1,#a38568,if(num==a38568[k]&&den==a38569[k],return(k)));0};
for(k=1,60,my(m=a38568[k],n=a38569[k],num=eulerphi(m^2),den=eulerphi(n^2));print1(findinlist(num,den)-1,", "))

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

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

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

A206350 Position of 1/n in the canonical bijection from the positive integers to the positive rational numbers.

Original entry on oeis.org

1, 2, 4, 8, 12, 20, 24, 36, 44, 56, 64, 84, 92, 116, 128, 144, 160, 192, 204, 240, 256, 280, 300, 344, 360, 400, 424, 460, 484, 540, 556, 616, 648, 688, 720, 768, 792, 864, 900, 948, 980, 1060, 1084, 1168, 1208, 1256, 1300, 1392, 1424, 1508, 1548

Offset: 1

Clark Kimberling, Feb 06 2012

nonn

The canonical bijection from the positive integers to the positive rational numbers is given by A038568(n)/A038569(n).
Appears to be a variant of A049696. - R. J. Mathar, Feb 11 2012
Apparently numbers m such that A071912(m) = 1. - Bill McEachen, Aug 01 2023

			The canonical bijection starts with 1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, so that A206297 starts with 1,3,5,9,13 and this sequence starts with 1,2,4,8,12.

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A000010, A008683, A038568, A038569, A049696, A171503, A206296.

Cf. A071912.

[1] cat [2*(&+[EulerPhi(k): k in [1..n-1]]): n in [2..80]]; // G. C. Greubel, Mar 29 2023

1, op(2*ListTools:-PartialSums(map(numtheory:-phi, [$1..100]))); # Robert Israel, Apr 24 2015

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, j-1, k-1]];
t = Table[a[n], {n, 0, 3000}];   (* A038568 *)
ReplacePart[Flatten[Position[t, 1]], 1, 1] (* A206350 *)
(* Second program *)
a[n_]:= If[n==1, 1, 2*Sum[EulerPhi[k], {k, n-1}]];;
Table[a[n], {n, 80}] (* G. C. Greubel, Mar 29 2023 *)

def A206350(n): return 1 if (n==1) else 2*sum(euler_phi(k) for k in range(1,n))
[A206350(n) for n in range(1,80)] # G. C. Greubel, Mar 29 2023

a(1) = 1, a(n+1) = Sum_{k=1..n} mu(k) * floor(n/k) * floor(1 + n/k), where mu(k) is the Moebius function A008683. - Daniel Suteu, May 28 2018

a(n) = 2*Sum_{k=1..n-1} A000010(k), a(1) = 1. - Robert Israel, Apr 24 2015

A206297 Position of n in the canonical bijection from the positive integers to the positive rational numbers.

Original entry on oeis.org

1, 3, 5, 9, 13, 21, 25, 37, 45, 57, 65, 85, 93, 117, 129, 145, 161, 193, 205, 241, 257, 281, 301, 345, 361, 401, 425, 461, 485, 541, 557, 617, 649, 689, 721, 769, 793, 865, 901, 949, 981, 1061, 1085, 1169, 1209, 1257, 1301, 1393, 1425, 1509, 1549

Offset: 1

Clark Kimberling, Feb 06 2012

nonn

The canonical bijection from the positive integers to the positive rational numbers is given by A038568(n)/A038569(n).
Appears to be a variant of A049691. - R. J. Mathar, Feb 11 2012
It appears that a(n) = 2*A005728(n) - 1. - Chris Boyd, Mar 21 2015

			The canonical bijection starts with 1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, so that this sequence starts with 1,3,5,9,13 and A206350 starts with 1,2,4,8,12.

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A038568, A038569, A206350.

A049691 is an essentially identical sequence. See also A018805.

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, j - 1, k - 1]];
t = Table[a[n], {n, 0, 3000}];   (* A038568 *)
ReplacePart[1 + Flatten[Position[t, 1]], 1, 1]
(* A206297 *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A206297(n):
    if n == 1:
        return 1
    c, j = 1, 2
    k1 = (n-1)//j
    while k1 > 1:
        j2 = (n-1)//k1 + 1
        c += (j2-j)*(A206297(k1+1)-2)
        j, k1 = j2, (n-1)//j2
    return (n-2)*(n-1)-c+j+2 # Chai Wah Wu, Aug 04 2024

cp's OEIS Frontend

A173467 Partial sums of A038569.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A340922 a(n) is the position of phi(A038568(n)^2)/phi(A038569(n)^2) in the enumeration of the rationals by A038568 and A038569, where phi is A000010.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Julia

PARI

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

Python

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell