|
%I M1008 N0376 #200 Apr 26 2023 08:07:10
%S 0,1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,102,120,128,140,150,
%T 172,180,200,212,230,242,270,278,308,324,344,360,384,396,432,450,474,
%U 490,530,542,584,604,628,650,696,712,754,774,806,830,882,900,940,964
%N Sum of totient function: a(n) = Sum_{k=1..n} phi(k), cf. A000010.
%C Number of elements in the set {(x,y): 1 <= x <= y <= n, 1=gcd(x,y)}. - _Michael Somos_, Jun 13 1999
%C Sum_{k=1..n} phi(k) gives the number of distinct arithmetic progressions which contain an infinite number of primes and whose difference does not exceed n. E.g., {1k+1}, {2k+1}, {3k+1, 3k+2}, {4k+1, 4k+3}, {5k+1, ..5k+4} means 10 sequences. - _Labos Elemer_, May 02 2001
%C The quotient A024916(n)/a(n) = SummatorySigma/SummatoryTotient as n increases seems to approach Pi^4/36 = zeta(2)^2 = A098198 ~2.705808084277845. - _Labos Elemer_, Sep 20 2004 (corrected by Peter Pein, Apr 28 2009)
%C Also the number of rationals p/q in (0,1] with denominators q<=n. - _Franz Vrabec_, Jan 29 2005
%C a(n) is the number of initial segments of Beatty sequences for real numbers > 1, cut off when the next term in the sequence would be >= n. For example, the sequence 1,2 is included for n=3 and n=4, but not for n >= 5 because the next term of the Beatty sequence must be 3 or 4. Problem suggested by _David W. Wilson_. - _Franklin T. Adams-Watters_, Oct 19 2006
%C Number of complex numbers satisfying any one of {x^1=1, x^2=1, x^3=1, x^4=1, x^5=1, ..., x^n=1}. - Paul Smith (math.idiot(AT)gmail.com), Mar 19 2007
%C a(n+2) equals the number of Sturmian words of length n which are 'special', prefix of two Sturmian words of length n+1. - _Fred Lunnon_, Sep 05 2010
%C For n > 1: A020652(a(n)) = 1 and A038567(a(n)) = n; for n > 0: A214803(a(n)) = 1. - _Reinhard Zumkeller_, Jul 29 2012
%C Also number of elements in the set {(x,y): 1 <= x + y <= n, x >= 0, y > 0, with x and y relatively prime integers}. Thus, the number of reduced rational numbers x/y with x nonnegative, y positive, and x + y <= n. (For n >= 1, 0 <= x/y <= n - 1, clearly including each integer in this interval.) - _Rick L. Shepherd_, Apr 08 2014
%C This function, the partial sums of phi = A000010, is sometimes denoted by (uppercase) Phi. - _M. F. Hasler_, Apr 18 2015
%C From _Roger Ford_, Jan 16 2016: (Start)
%C For n >= 1: a(n) is the number of perfect arched semi-meander solutions with n arches. To be perfect the number of arch groupings must equal the number of arches with a length of 1 in the current generation and every preceding generation.
%C Example: p is the number of arches with length 1 (/\), g is the number of arch groups (-), n is number of arches in the top half of a semi-meander solution
%C /\
%C /\ //\\
%C //\\-/\-///\\\- n=6 p=3 g=3 Each preceding arch configuration
%C /\ /\ is formed by attaching the arch
%C /\-//\\-//\\- n=5 p=3 g=3 end in the first position and the
%C /\ arch end in the last position.
%C //\\
%C ///\\\-/\- n=4 p=2 g=2
%C /\
%C //\\-/\- n=3 p=2 g=2
%C /\-/\- n=2 p=2 g=2
%C /\- n=1 p=1 g=1. (End)
%C a(n) is the number of distinct lists of binary words of length n that are balanced (Sturmian). - _Dan Rockwell_, Will Wodrich, Aaliyah Fiala, and Bob Burton, May 30 2019
%D A. Beiler, Recreations in the Theory of Numbers, Dover Publications, 1966, Chap. XVI.
%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
%D Sarah Bockting-Conrad, Yevgenia Kashina, T. Kyle Petersen, Bridget Eileen Tenner, Sós Permutations, arXiv:2007.01132
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 138.
%D M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972, p. 6.
%D D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
%D D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section I.21.
%D I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 94, Problem 11.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.
%H Al Zimmermann, <a href="/A002088/b002088.txt">Table of n, a(n) for n = 0..50000</a> (Terms 0 to 1000 by T. D. Noe)
%H Dorin Andrica, Ovidiu Bagdasar, <a href="http://hdl.handle.net/10545/623501">On some results concerning the polygonal polynomials</a>, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
%H Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma, <a href="https://arxiv.org/abs/1805.04765">Bipartite Graphs of Small Readability</a>, arXiv:1805.04765 [cs.DM], 2018.
%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/totient/totient.html">Euler Totient Function Asymptotic Constants</a> [Broken link]
%H Steven R. Finch, <a href="http://web.archive.org/web/20010603070928/http://www.mathsoft.com/asolve/constant/totient/totient.html">Euler Totient Function Asymptotic Constants</a> [From the Wayback machine]
%H Paul Loomis, Michael Plytage and John Polhill, <a href="http://www.jstor.org/stable/27646564">Summing up the Euler phi function</a>, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008, pp. 34-42.
%H J. Sandor, D. S. Mitrinovic, B. Crstici, <a href="https://doi.org/10.1007/1-4020-3658-2">Handbook of Number Theory I</a>, Volume 1, Springer, 2005, p. 24.
%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%H James J. Sylvester, <a href="https://doi.org/10.1080/14786448308627346">On the number of fractions contained in any Farey series of which the limiting number is given</a>, in: London, Edinburgh and Dublin Philosophical Magazine (5th series) 15 (1883), p. 251 = Collected Mathematical Papers, Vols. 1-4, Cambridge Univ. Press, 1904-1912, Vol. 4, p. 103 (see below).
%H J. J. Sylvester, The collected mathematical papers of James Joseph Sylvester, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=AAS8085.0002.001">vol. 2</a>, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=AAS8085.0003.001">vol. 3</a>, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?sid=b88432273f115fb346725f1a42422e19;c=umhistmath;idno=AAS8085.0004.001">vol. 4</a>.
%H A. Walfisz, <a href="https://doi.org/10.1002/zamm.19640441217">Weylsche Exponentialsummen in der neueren Zahlentheorie</a>, VEB Deutscher Verlag der Wissenschaften, Berlin 1963.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotientFunction.html">Totient Function</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BeattySequence.html">Beatty Sequence.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotientSummatoryFunction.html">Totient Summatory Function.</a>
%H R. G. Wilson, v, <a href="/A002088/a002088.pdf">Letter to N. J. A. Sloane, Jan 24 1989</a>
%F a(n) = (3*n^2)/(Pi^2) + O(n log n).
%F More precisely, a(n) = (3/Pi^2)*n^2 + O(n*(log(n))^(2/3)*(log(log(n)))^(4/3)), (A. Walfisz 1963). - _Benoit Cloitre_, Feb 02 2003
%F a(n) = (1/2)*Sum_{k>=1} mu(k)*floor(n/k)*floor(1+n/k). - _Benoit Cloitre_, Apr 11 2003
%F a(n) = A000217(n) - A063985(n) = A018805(n) - A015614(n). - _Reinhard Zumkeller_, Jan 21 2013
%F A slightly simpler version of Cloitre's formula is a(n) = 1/2 + Sum_{k=1..oo} floor(n/k)^2*mu(k)/2. - _Bill Gosper_, Jul 25 2020
%F The quotient A024916(n)/a(n) = SummatorySigma/SummatoryTotient as n increases seems to approach (Pi^4)/36 = Zeta(2)^2 = 2.705808084277845. See also A067282. - _Labos Elemer_, Sep 21 2004
%F A024916(n)/a(n) = zeta(2)^2 + O(log(n)/n). This follows from asymptotic formulas for the sequences. - _Franklin T. Adams-Watters_, Oct 19 2006
%F Row sums of triangle A134542. - _Gary W. Adamson_, Oct 31 2007
%F G.f.: (Sum_{n>=1} mu(n)*x^n/(1-x^n)^2)/(1-x), where mu(n) = A008683(n). - _Mamuka Jibladze_, Apr 06 2015
%F a(n) = A005728(n) - 1, for n >= 0. - _Wolfdieter Lang_, Nov 22 2016
%F a(n) = (Sum_{k=1..floor(sqrt(n))} k*(k+1) * (M(floor(n/k)) - M(floor(n/(k+1)))) + Sum_{k=1..floor(n/(1+floor(sqrt(n))))} mu(k) * floor(n/k) * floor(1+n/k))/2, where M(k) is the Mertens function (A002321) and mu(k) is the Moebius function (A008683). - _Daniel Suteu_, Nov 23 2018
%F a(n) = A015614(n)+1. - _R. J. Mathar_, Apr 26 2023
%e G.f. = x + 2*x^2 + 4*x^3 + 6*x^4 + 10*x^5 + 12*x^6 + 18*x^7 + 22*x^8 + 28*x^9 + ...
%p with(numtheory): A002088:=n->add(phi(i),i=1..n): seq(A002088(n), n=0..70);
%t Table[Plus @@ EulerPhi[Range[n]], {n, 0, 57}] (* _Alonso del Arte_, May 30 2006 *)
%t Accumulate[EulerPhi[Range[0,60]]] (* _Harvey P. Dale_, Aug 27 2011 *)
%o (PARI) a(n)=sum(k=1,n,eulerphi(k)) \\ _Charles R Greathouse IV_, Jun 16 2011
%o (PARI) a(n)=my(s=1); forsquarefree(k=1,n,s+=(n\k[1])^2*moebius(k)); s/2 \\ _Charles R Greathouse IV_, Oct 15 2021
%o (PARI) first(n)=my(v=vector(n),s); forfactored(k=1,n, v[k[1]]=s+=eulerphi(k)); v \\ _Charles R Greathouse IV_, Oct 15 2021
%o (Haskell)
%o a002088 n = a002088_list !! n
%o a002088_list = scanl (+) 0 a000010_list -- _Reinhard Zumkeller_, Jul 29 2012
%o (GAP) List([1..60],n->Sum([1..n],i->Phi(i))); # _Muniru A Asiru_, Jul 31 2018
%o (Magma) [&+[EulerPhi(i): i in [1..n]]: n in [1..60]]; // _Vincenzo Librandi_, Aug 01 2018
%o (Sage) [sum(euler_phi(k) for k in (1..n)) for n in (0..60)] # _G. C. Greubel_, Nov 25 2018
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A002088(n): # based on second formula in A018805
%o if n == 0:
%o return 0
%o c, j = 0, 2
%o k1 = n//j
%o while k1 > 1:
%o j2 = n//k1 + 1
%o c += (j2-j)*(2*A002088(k1)-1)
%o j, k1 = j2, n//j2
%o return (n*(n-1)-c+j)//2 # _Chai Wah Wu_, Mar 24 2021
%Y Cf. A000010, A015614, A005728, A067282, A001088, A134542.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E Additional comments from _Len Smiley_
|
