A071912 -id:A071912 - 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

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

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