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

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

Author

N. J. A. Sloane

Keywords

• nonn
• frac
• core
• nice

Comments

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

Examples

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

References

• H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.

Links

• David Wasserman, Table of n, a(n) for n = 0..100000
• Index entries for "core" sequences
• Index entries for sequences related to enumerating the rationals

Crossrefs

Cf. A038566, A038567, A038568.

See A020652, A020653 for an alternative version.

Programs

Maple

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)

Mathematica

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

PARI

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

Python

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

Extensions

More terms from Erich Friedman

Definition clarified by N. J. A. Sloane, Nov 25 2021