A182976 -id:A182976 - cp's OEIS frontend

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

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

A182972 Numerators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Original entry on oeis.org

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

Offset: 1

William Rex Marshall, Dec 16 2010

A023022(n) and A245677(n) give number and numerator of sum of fractions a(k)/A182973(k) such that a(k) + A182973(k) = n. - Reinhard Zumkeller, Jul 30 2014

			Positive fractions < 1 listed by increasing sum of numerator and denominator, and by increasing numerator for equal sums:
1/2
1/3
1/4 2/3
1/5
1/6 2/5 3/4
1/7 3/5
1/8 2/7 4/5
1/9 3/7
1/10 2/9 3/8 4/7 5/6
1/11 5/7
1/12 2/11 3/10 4/9 5/8 6/7
1/13 3/11 5/9
1/14 2/13 4/11 7/8
1/15 3/13 5/11 7/9
1/16 2/15 3/14 4/13 5/12 6/11 7/10 8/9
1/17 5/13 7/11
1/18 2/17 3/16 4/15 5/14 6/13 7/12 8/11 9/10
1/19 3/17 7/13 9/11
(this is 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.
R. K. Guy, Unsolved Problems in Number Theory (UPINT), Section D11.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.
Index entries for sequences related to enumerating the rationals

Cf. A182973 (denominators), A366191 (interleaved).
Cf. A020652, A038567, A182974, A182975, A182976.
Cf. A023022, A245677, A245678, A245718.
Essentially the same as A333856.

a182972 n = a182972_list !! (n-1)
a182972_list = map fst $ concatMap q [3..] where
   q x = [(num, den) | num <- [1 .. div x 2],
                       let den = x - num, gcd num den == 1]
-- Reinhard Zumkeller, Jul 29 2014

t1:=[];
for n from 2 to 40 do
t1:=[op(t1),1/(n-1)];
for i from 2 to floor((n-1)/2) do
   if gcd(i,n-i)=1 then t1:=[op(t1),i/(n-i)]; fi; od:
od:
t1;

t1={}; For[n=2, n <= 40, n++, AppendTo[t1, 1/(n-1)]; For[i=2, i <= Floor[(n-1)/2], i++, If[GCD[i, n-i] == 1, AppendTo[t1, i/(n-i)]]]]; t1 // Numerator // Rest (* Jean-François Alcover, Jan 20 2015, translated from Maple *)

program a182972;
var
  num,den,n: longint;
function gcd(i,j: longint):longint;
begin
  repeat
    if i>j then i:=i mod j else j:=j mod i;
  until (i=0) or (j=0);
  if i=0 then gcd:=j else gcd:=i;
end;
begin
  num:=1; den:=1; n:=0;
  repeat
    repeat
      inc(num); dec(den);
      if num>=den then
      begin
        inc(den,num); num:=1;
      end;
    until gcd(num,den)=1;
    inc(n); writeln(n,' ',num);
  until n=100000;
end.

from itertools import count, islice
from math import gcd
def A182972_gen(): # generator of terms
    return (i for n in count(2) for i in range(1,1+(n-1>>1)) if gcd(i,n-i)==1)
A182972_list = list(islice(A182972_gen(),10)) # Chai Wah Wu, Aug 28 2023

Corrected by William Rex Marshall, Aug 12 2013

A182973 Denominators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Original entry on oeis.org

2, 3, 4, 3, 5, 6, 5, 4, 7, 5, 8, 7, 5, 9, 7, 10, 9, 8, 7, 6, 11, 7, 12, 11, 10, 9, 8, 7, 13, 11, 9, 14, 13, 11, 8, 15, 13, 11, 9, 16, 15, 14, 13, 12, 11, 10, 9, 17, 13, 11, 18, 17, 16, 15, 14, 13, 12, 11, 10, 19, 17, 13, 11, 20, 19, 17, 16, 13, 11, 21, 19, 17, 15, 13, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12

Offset: 1

William Rex Marshall, Dec 16 2010

A023022(n) and A245678(n) give number and denominator of sum of fractions A182972(k)/a(k) such that A182972(k) + a(k) = n. - Reinhard Zumkeller, Jul 30 2014

			Positive fractions < 1 listed by increasing sum of numerator and denominator, and by increasing numerator for equal sums:
1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5, 3/4, 1/7, 3/5, 1/8, 2/7, 4/5, 1/9, 3/7, ...
(this is 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.
R. K. Guy, Unsolved Problems in Number Theory (UPINT), Section D11.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.
Index entries for sequences related to enumerating the rationals

Cf. A182972 (numerators), A366191 (interleaved).
Cf. A020652, A038567, A182974-A182976.
Cf. A023022, A245677, A245678, A245718.

a182973 n = a182973_list !! (n-1)
a182973_list = map snd $ concatMap q [3..] where
   q x = [(num, den) | num <- [1 .. div x 2],
                       let den = x - num, gcd num den == 1]
-- Reinhard Zumkeller, Jul 29 2014

A182973list[s_] := Table[If[CoprimeQ[num, s-num], s-num, Nothing], {num, Floor[s/2]}]; Flatten[Array[A182973list, 25, 3]] (* Paolo Xausa, Feb 27 2024 *)

program a182973;
var
  num,den,n: longint;
function gcd(i,j: longint):longint;
begin
  repeat
    if i>j then i:=i mod j else j:=j mod i;
  until (i=0) or (j=0);
  if i=0 then gcd:=j else gcd:=i;
end;
begin
  num:=1; den:=1; n:=0;
  repeat
    repeat
      inc(num); dec(den);
      if num>=den then
      begin
        inc(den,num); num:=1;
      end;
    until gcd(num,den)=1;
    inc(n); writeln(n,' ',den);
  until n=100000;
end.

from itertools import count, islice
from math import gcd
def A182973_gen(): # generator of terms
    return (n-i for n in count(2) for i in range(1,1+(n-1>>1)) if gcd(i,n-i)==1)
A182973_list = list(islice(A182973_gen(),10)) # Chai Wah Wu, Aug 28 2023

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.

cp's OEIS Frontend

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

A182972 Numerators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Pascal

Python

Extensions

A182973 Denominators of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Pascal

Python

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