%I A002088 M1008 N0376
%S A002088 0,1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,102,120,128,140,150,
%T A002088 172,180,200,212,230,242,270,278,308,324,344,360,384,396,432,450,474,
%U A002088 490,530,542,584,604,628,650,696,712,754,774,806,830,882,900,940,964
%N A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k) (cf. A000010).
%C A002088 Number of elements in the set {(x,y): 1<=x<=y<=n, 1=gcd(x,y)}.
%C A002088 Sum_{k=1..n} phi(k) gives the number of distinct arithmetic progressions 
               which contain 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 E. (labos(AT)ana.sote.hu), May 
               02 2001
%C A002088 The quotient A024916[n]/a[n] = SummatorySigma/SummatoryTotient as n increases 
               seems to approach Pi^4/36 or zeta(2)^2 [~2.705808084277845]. - Labos 
               E. (labos(AT)ana.sote.hu), Sep 20 2004. Corrected by Peter Pein, 
               Apr 28 2009.
%C A002088 Also the number of rationals p/q in (0,1] with denominators q<=n. - Franz 
               Vrabec (franz.vrabec(AT)aon.at), Jan 29 2005
%C A002088 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 
               (FrankTAW(AT)Netscape.net), Oct 19 2006
%C A002088 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
%D A002088 A. Beiler, Recreations in the Theory of Numbers, Dover, 1966, Chap. XVI.
%D A002088 S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
%D A002088 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, 
               Reading, MA, 1990, p. 138.
%D A002088 M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 
               1972, p. 6.
%D A002088 D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 
               105, National Research Council, Washington, DC, 1941, pp. 7-10.
%D A002088 Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler 'phi' 
               function, The College Mathematics Journal, vol. 39 (#1), pp. 34-42.
%D A002088 D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section I.21.
%D A002088 I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 
               2nd ed., Wiley, NY, 1966, p. 94, Problem 11.
%D A002088 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A002088 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002088 J. J. Sylvester, On the number of fractions contained in any Farey Series 
               of which the Limiting Number is given, London, Edinburgh and Dublin 
               Philosophical Magazine (Fifth Series), vol. 15 (1883), p. 251 = Collected 
               Mathematical Papers, Vols. 1-4, Cambridge Univ. Press, 1904-1912, 
               Vol. 4, p. 103.
%D A002088 A. Walfisz, Weylsche Exponentialsummen in der Neuene Zahlentheorie, VEB 
               Deutsher Verlag, Berlin, 1963
%H A002088 T. D. Noe, <a href="b002088.txt">Table of n, a(n) for n = 0..1000</a>
%H A002088 S. R. Finch, <a href="http://algo.inria.fr/bsolve/constant/totient/totient.html">
               Euler Totient Function Asymptotic Constants</a>
%H A002088 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 A002088 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               TotientFunction.html">Link to a section of The World of Mathematics.</
               a>
%H A002088 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               BeattySequence.html">Beatty Sequence.</a>
%H A002088 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               TotientSummatoryFunction.html">Totient Summatory Function.</a>
%F A002088 a(n) = (3n^2)/(pi^2) + O( n log n).
%F A002088 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 (benoit7848c(AT)orange.fr), 
               Feb 02 2003
%F A002088 a(n)=(1/2)*sum(k>=1, mu(k)*floor(n/k)*floor(1+n/k)) - Benoit Cloitre 
               (benoit7848c(AT)orange.fr), Apr 11 2003
%F A002088 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 E. (labos(AT)ana.sote.hu), Sep 21 2004
%F A002088 A024916(n)/a(n) = zeta(2)^2 + O(log(n)/n). This follows from asymptotic 
               formulas for the sequences. - Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), 
               Oct 19 2006
%F A002088 Row sums of triangle A134542 - Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Oct 31 2007
%p A002088 with(numtheory): A002088 := n->add(phi(i),i=1..n);
%t A002088 Table[Plus @@ EulerPhi[Range[n]], {n, 0, 57}] - Alonso Delarte (alonso.delarte(AT)gmail.com), 
               May 30 2006
%Y A002088 Cf. A000010, A015614, A005728, A067282.
%Y A002088 Cf. A134542.
%Y A002088 Sequence in context: A162578 A152919 A092249 this_sequence A019332 A002491 
               A045958
%Y A002088 Adjacent sequences: A002085 A002086 A002087 this_sequence A002089 A002090 
               A002091
%K A002088 nonn,easy,nice
%O A002088 0,3
%A A002088 N. J. A. Sloane (njas(AT)research.att.com).
%E A002088 Additional comments from Leonard Smiley (smiley(AT)math.uaa.alaska.edu).