A038568 Numerators in canonical bijection from positive integers to positive rationals.

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

Offset

0,3

Comments

Even-indexed terms are positive integers in order, with m occurring phi(m) times. Preceding odd-indexed terms (except for missing initial 0) are the corresponding numbers <= m and relatively prime to m, in increasing order. The denominators are just this sequence shifted left. Thus each positive rational occurs exactly once as a ratio a(n)/a(n+1). - Franklin T. Adams-Watters, Dec 06 2006

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

Example

First 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);
now follow each term (except the first) with 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).

Maple

with (numtheory): A038568 := 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 (j-1) fi: RETURN (k-1): end: # Ulrich Schimke (ulrschimke(AT)aol.com)

Mathematica

a[n_] := Module[{sum = 1, k = 2}, While[sum < n, sum = sum + 2*EulerPhi[k]; k = k+1]; sum = sum - 2*EulerPhi[k-1]; j = 1; While[sum < n, If[GCD[j, k-1] == 1, sum = sum+2]; j = j+1; ]; If[sum > n, Return[j-1]]; Return[k-1] ]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 21 2012, translated from Maple *)

Prog

(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: return j - 1
    return k - 1 # Indranil Ghosh, May 23 2017, translated from Mathematica
(Julia)
using Nemo
function A038568List(len)
    a, A = QQ(0), []
    for n in 1:len
        a = next_minimal(a)
        push!(A, numerator(a))
    end
A end
A038568List(84) |> println # Peter Luschny, Mar 13 2018
(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 ([p, q][n+2]), n-=2))), n-=2*e)) } \\ Rémy Sigrist, Feb 25 2021

Crossrefs

Cf. A020652, A020653, A038566, A038567, A038569.

Sequence in context: A215467 A284266 A317988 * A071912 A070940 A020651

Adjacent sequences: A038565 A038566 A038567 * A038569 A038570 A038571

Keyword

nonn,frac,core,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Erich Friedman

Status

approved