login
A020652
Numerators in canonical bijection from positive integers to positive rationals.
33
1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 7, 1, 2, 4, 5, 7, 8, 1, 3, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 5, 7, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 3, 5, 9, 11, 13, 1, 2, 4, 7, 8, 11, 13, 14, 1, 3, 5, 7, 9, 11, 13, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1, 5
OFFSET
1,3
COMMENTS
a(A002088(n)) = 1 for n > 1. - Reinhard Zumkeller, Jul 29 2012
When read as an irregular table with each 1 entry starting a new row, then the n-th row consists of the set of multiplicative units of Z_{n+1}. These rows form a group under multiplication mod n. - Tom Edgar, Aug 20 2013
The pair of sequences A020652/A020653 is defined by ordering the positive fractions p/q (reduced to lowest terms) by increasing p+q, then increasing p: 1/1; 1/2, 2/1; 1/3, 3/1; 1/4, 2/3, 3/2, 4/1; 1/5, 5/1; 2/5, 3/4, 4/3, 5/2; etc. For given p+q, there are A000010(p+q) fractions, listed starting at index A002088(p+q-1). - M. F. Hasler, Mar 06 2020
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.
Richard Courant and Herbert Robbins. What Is Mathematics?, Oxford, 1941, pp. 79-80.
H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.
EXAMPLE
Arrange positive fractions < 1 by increasing denominator then by increasing numerator: 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6 ... (this is A020652/A038567). - William Rex Marshall, Dec 16 2010
MAPLE
with (numtheory): A020652 := proc (n) local sum, j, k; sum := 0: k := 2: while (sum < n) do: sum := sum + phi(k): k := k + 1: od: sum := sum - phi(k-1): j := 1; while sum < n do: if gcd(j, k-1) = 1 then sum := sum + 1: fi: j := j+1: od: RETURN (j-1): end: # Ulrich Schimke (ulrschimke(AT)aol.com), Nov 06 2001
MATHEMATICA
Reap[Do[If[GCD[num, den] == 1, Sow[num]], {den, 1, 20}, {num, 1, den-1}] ][[2, 1]] (* Jean-François Alcover, Oct 22 2012 *)
PROG
(Haskell)
a020652 n = a020652_list !! (n-1)
a020652_list = map fst [(u, v) | v <- [1..], u <- [1..v-1], gcd u v == 1]
-- Reinhard Zumkeller, Jul 29 2012
(PARI) a(n)=my(s, j=1, k=1); while(s<n, s+=eulerphi(k++); ); s-=eulerphi(k); while(s<n, if(gcd(j, k)==1, s++); j++); j-1 \\ Charles R Greathouse IV, Feb 07 2013
(Python)
from sympy import totient, gcd
def a(n):
s=0
k=2
while s<n:
s+=totient(k)
k+=1
s-=totient(k - 1)
j=1
while s<n:
if gcd(j, k - 1)==1:
s+=1
j+=1
return j - 1
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, May 23 2017, after Ulrich Schimke's MAPLE code
CROSSREFS
Essentially the same as A038566, which is the main entry for this sequence.
A054424 gives mapping to Stern-Brocot tree.
Cf. A037161.
Sequence in context: A280700 A356149 A038566 * A293248 A096107 A329585
KEYWORD
nonn,frac,core,nice,tabf
STATUS
approved