A038568 -id:A038568 - cp's OEIS frontend

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.

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,", "))

A173509 Partial sums of A038568.

Original entry on oeis.org

1, 2, 4, 5, 8, 10, 13, 14, 18, 21, 25, 26, 31, 33, 38, 41, 46, 50, 55, 56, 62, 67, 73, 74, 81, 83, 90, 93, 100, 104, 111, 116, 123, 129, 136, 137, 145, 148, 156, 161, 169, 176, 184, 185, 194, 196, 205, 209, 218, 223, 232, 239, 248, 256, 265, 266, 276, 279, 289, 296

Offset: 0

Jonathan Vos Post, Feb 20 2010

Partial sums of numerators in canonical bijection from positive integers to positive rationals. The companion sequence for denominators is A173467, summing A038569. The subsequence of squares in this partial sum begins: 1, 4, 25, 81, 100, 137, 169, 196, 256, 289, 576. The subsequence of primes in this partial sum begins: 2, 5, 13, x, 41, 67, 73, 83, 223, 239, 337, 353, 379, 401, 419, 449, 479, 491, 503, 563.

			a(93) = 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.

Cf. A038568, A038569, A173467.

a(n) = SUM[i=0..n] A038568(i).

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

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

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

A206330 Numbers that match polynomials irreducible over the integers.

Original entry on oeis.org

3, 4, 5, 6, 9, 10, 17, 18, 19, 20, 21, 22, 29, 30, 33, 34, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 53, 54, 55, 56, 57, 58, 59, 60, 69, 70, 73, 74, 77, 78, 81, 82, 83, 84, 87, 88, 97, 98, 101, 102, 105, 106, 109, 110, 113, 114, 117, 118, 119, 120, 123

Offset: 1

Clark Kimberling, Feb 06 2012

nonn

Each n>1 matches a polynomial having integer coefficients
determined by the prime factorization of n.  Let c be a
positive integer, and write
c=p(1)^e(1) * p(2)^e(2) * ... * p(k)^e(k), and
define p(n,x) = e(1) + e(2)x + e(3)x^2 + ... + e(k)x^k.
If c/d is a rational number with GCD(c,d)=1, define
Q(c/d,x)=p(c,x)-p(d,x).  Let c(n)/d(n) be the n-th
positive rational number given by the canonical
bijection; i.e., c(n)=A038568(n)/A038569(n).
Define P(0,x)=1 and P(n,x)=Q(c(n)/d(n),x).  Polynomials
having nonnegative integer coefficients are matched to
the nonnegative integers as follows:
...
n .... P[n,x] .. irreducible
0 .... 0 ....... no
1 ... -1 ....... no
2 .... 1 ....... no
3 ... -x ....... yes
4 .... x ....... yes
5 ... 1-x ...... yes
6 .. -1+x ...... yes
7 .. -2 ........ no
8 ... 2 ........ no
9 .. -2+x ...... yes
10 .. 2-x ...... yes

			In the table under Comments, read "yes" for n=3,4,5,6,9,10.

Cf. A206284 (polynomials over the positive integers),

A206331 (complement of A206330).

b[n_] := Table[x^k, {k, 0, n}];
f[n_] := f[n] = FactorInteger[n]; z = 1000;
t[n_, m_, k_] := If[PrimeQ[f[n][[m, 1]]] && f[n][[m, 1]]
 == Prime[k], f[n][[m, 2]], 0];
u = Table[Apply[Plus,
    Table[Table[t[n, m, k], {k, 1, PrimePi[n]}], {m, 1,
      Length[f[n]]}]], {n, 1, z}];
c[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]];
d[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]];
P[n_, x_] :=
 u[[c[n]]].b[-1 + Length[u[[c[n]]]]] -
  u[[d[n]]].b[-1 + Length[u[[d[n]]]]]
TableForm[Table[{n, P[n, x], Factor[P[n, x]]},
   {n, 1, z/4}]];
v = {}; Do[n++;
 If[IrreduciblePolynomialQ[P[n, x]], AppendTo[v, n]], {n, z/2}]
v                            (* A206330 *)
Complement[Range[0,200], v]  (* A206331 *)

A317988 Farey fraction tree, reading each fraction's numerator first, then its denominator.

Original entry on oeis.org

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

Offset: 1

Robert G. Wilson v, Oct 03 2018

nonn

0 < a(2n-1)/a(2n) < 1 for n > 2.

This appears to be A038568 preceded by 0,1,1. - Peter Kagey, Jan 09 2022

			Farey fraction tree begins:
  0/1                                             1/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
  ...

Cf. A038566, A038567, A038568.

Table[ If[ GCD[n, d] == 1, {n, d}, {}], {d, 0, 12}, {n, 0, d}] // Flatten

0,1 followed by the interleaving of A038566 & A038567.

cp's OEIS Frontend

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

A173509 Partial sums of A038568.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell