|
%I #70 Dec 13 2021 17:18:37
%S 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,
%T 11,11,11,11,11,11,11,11,11,11,12,12,12,12,13,13,13,13,13,13,13,13,13,
%U 13,13,13,14,14,14,14,14,14,15,15,15,15,15,15,15,15,16,16,16,16,16,16
%N Denominators in canonical bijection from positive integers to positive rationals <= 1.
%C n occurs phi(n) times (cf. A000010).
%C Least k such that phi(1) + phi(2) + phi(3) + ... + phi(k) >= n. - _Benoit Cloitre_, Sep 17 2002
%C 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.]
%C 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
%D 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.
%D H. Lauwerier, Fractals, Princeton Univ. Press, p. 23.
%H David Wasserman, <a href="/A038567/b038567.txt">Table of n, a(n) for n = 0..100000</a>
%H Paul Yiu, <a href="http://math.fau.edu/Yiu/RecreationalMathematics2003.pdf">Recreational Mathematics</a>, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Ra#rational">Index entries for sequences related to enumerating the rationals</a>
%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%F From _Henry Bottomley_, Dec 18 2000: (Start)
%F 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]
%F n = a(A015614(n)) = a(A002088(n)) - 1 = a(A002088(n-1)). (End)
%F a(n) = A002024(A169581(n)). - _Reinhard Zumkeller_, Dec 02 2009
%F a(A002088(n)) = n for n > 1. - _Reinhard Zumkeller_, Jul 29 2012
%F a(n) = A071912(2*n+1). - _Reinhard Zumkeller_, Dec 16 2013
%e 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.
%p 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)
%t 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 *)
%t Flatten[Table[Table[n,{EulerPhi[n]}],{n,20}]] (* _Harvey P. Dale_, Mar 12 2013 *)
%o (PARI) a(n)=if(n<0,0,s=1; while(sum(i=1,s,eulerphi(i))<n,s++); s)
%o (Haskell)
%o import Data.List (genericTake)
%o a038567 n = a038567_list !! n
%o a038567_list = concatMap (\x -> genericTake (a000010 x) $ repeat x) [1..]
%o -- _Reinhard Zumkeller_, Dec 16 2013, Jul 29 2012
%o (Python)
%o from sympy import totient
%o def a(n):
%o s=1
%o while sum(totient(i) for i in range(1, s + 1))<n: s+=1
%o return s # _Indranil Ghosh_, May 23 2017
%Y Cf. A020652, A020653, A038566 - A038569, A182972, A182973 - A182976.
%Y A054427 gives mapping to Stern-Brocot tree.
%Y Cf. A037162.
%K nonn,frac,core,easy,nice
%O 0,2
%A _N. J. A. Sloane_
%E More terms from _Erich Friedman_
|
