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

A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jun 09 2013

The triangle of fractions A226314(i,j)/A054531(i,j) is an efficient way to enumerate the rationals [Fortnow].

Sum(A226314(n,k)/A054531(n,k): 1<=k<=n) = A226555(n)/A040001(n). - Reinhard Zumkeller, Jun 10 2013

			Triangle begins:
[1]
[1, 2]
[1, 2, 3]
[1, 3, 3, 4]
[1, 2, 3, 4, 5]
[1, 4, 5, 5, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 5, 3, 7, 5, 7, 7, 8]
[1, 2, 7, 4, 5, 8, 7, 8, 9]
[1, 6, 3, 7, 9, 8, 7, 9, 9, 10]
...
The resulting triangle of fractions begins:
1,
1/2, 2,
1/3, 2/3, 3,
1/4, 3/2, 3/4, 4,
1/5, 2/5, 3/5, 4/5, 5,
...

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
Lance Fortnow, Counting the Rationals Quickly, Computational Complexity Weblog, Monday, March 01, 2004.
Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Cf. A002262.

Cf. A037161, A037162, A066657, A066658.

a226314 n k = n - (n - k) `div` gcd n k
a226314_row n = a226314_tabl !! (n-1)
a226314_tabl = map f $ tail a002262_tabl where
   f us'@(_:us) = map (v -) $ zipWith div vs (map (gcd v) us)
     where (v:vs) = reverse us'
-- Reinhard Zumkeller, Jun 10 2013

f:=(i,j) -> j+(i-j)/gcd(i,j);
g:=n->[seq(f(i,n),i=1..n)];
for n from 1 to 20 do lprint(g(n)); od:

A037161 Well-order the rational numbers; take numerators.

Original entry on oeis.org

0, -1, 1, -2, -1, 1, 2, -3, -1, 1, 3, -4, -3, -2, -1, 1, 2, 3, 4, -5, -1, 1, 5, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, -7, -5, -3, -1, 1, 3, 5, 7, -8, -7, -5, -4, -2, -1, 1, 2, 4, 5, 7, 8, -9, -7, -3, -1, 1, 3, 7, 9, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1

Offset: 0

N. J. A. Sloane

W. Sierpiński, Cardinal and Ordinal Numbers, Warsaw 1965, 2nd ed., p. 40.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A037162.

Cf. A020652.

import Data.List (transpose)
import Data.Ratio ((%), numerator)
a037161 n = a037161_list !! n
a037161_list = 0 : map numerator
  (concat $ concat $ transpose [map (map negate) qss, map reverse qss])
  where qss = map q [1..]
        q x = map (uncurry (%)) $ filter ((== 1) . uncurry gcd) $
                  zip (reverse zs) zs where zs = [1..x]
-- Reinhard Zumkeller, Mar 08 2013

order[n_] := Join[-Reverse[ pos = Select[(r = Range[n])/Reverse[r], Numerator[#] + Denominator[#] == n + 1 & ] ], pos]; order[0] = 0; Numerator[ Flatten[ Table[ order[n], {n, 0, 10}]]] (* Jean-François Alcover, Jun 27 2012 *)

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

A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

A037161 Well-order the rational numbers; take numerators.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica