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

Author

N. J. A. Sloane

Keywords

• nonn
• frac
• core
• easy
• nice

Comments

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

Examples

			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.
		

References

• 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.

Links

• 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.

Crossrefs

Cf. A020652, A020653, A038566 - A038569, A093602, A182972, A182973 - A182976.

A054427 gives mapping to Stern-Brocot tree.

Cf. A037162.

Programs

Haskell

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

Maple

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)

Mathematica

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 *)

PARI

a(n)=if(n<0,0,s=1; while(sum(i=1,s,eulerphi(i))
				

Python

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

Python

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

Formula

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

Extensions

More terms from Erich Friedman