login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k) (cf. A000010).
(Formerly M1008 N0376)
65
0, 1, 2, 4, 6, 10, 12, 18, 22, 28, 32, 42, 46, 58, 64, 72, 80, 96, 102, 120, 128, 140, 150, 172, 180, 200, 212, 230, 242, 270, 278, 308, 324, 344, 360, 384, 396, 432, 450, 474, 490, 530, 542, 584, 604, 628, 650, 696, 712, 754, 774, 806, 830, 882, 900, 940, 964 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of elements in the set {(x,y): 1<=x<=y<=n, 1=gcd(x,y)}. - Michael Somos, Jun 13 1999

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

The quotient A024916[n]/a[n] = SummatorySigma/SummatoryTotient as n increases seems to approach Pi^4/36 or zeta(2)^2 [~2.705808084277845]. - Labos Elemer, Sep 20 2004 (corrected by Peter Pein, Apr 28 2009)

Also the number of rationals p/q in (0,1] with denominators q<=n. - Franz Vrabec, Jan 29 2005

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

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

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

For n > 1: A020652(a(n)) = 1 and A038567(a(n)) = n; for n > 0: A214803(a(n)) = 1. - Reinhard Zumkeller, Jul 29 2012

a(n) = A000217(n) - A063985(n) = A018805(n) - A015614(n). - Reinhard Zumkeller, Jan 21 2013

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

REFERENCES

A. Beiler, Recreations in the Theory of Numbers, Dover, 1966, Chap. XVI.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 138.

M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972, p. 6.

D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.

Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler 'phi' function, The College Mathematics Journal, vol. 39 (#1), pp. 34-42.

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section I.21.

I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 94, Problem 11.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.

A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin 1963.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000

S. R. Finch, Euler Totient Function Asymptotic Constants

J. J. Sylvester, The collected mathematical papers of James Joseph Sylvester, vol. 2, vol. 3, vol. 4.

Eric Weisstein's World of Mathematics, Totient Function

Eric Weisstein's World of Mathematics, Beatty Sequence.

Eric Weisstein's World of Mathematics, Totient Summatory Function.

FORMULA

a(n) = (3n^2)/(pi^2) + O(n log n).

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

a(n) = (1/2)*sum{k>=1} mu(k)*floor(n/k)*floor(1+n/k). - Benoit Cloitre, Apr 11 2003

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

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

Row sums of triangle A134542. - Gary W. Adamson, Oct 31 2007

EXAMPLE

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 +...

MAPLE

with(numtheory): A002088 := n->add(phi(i), i=1..n);

MATHEMATICA

Table[Plus @@ EulerPhi[Range[n]], {n, 0, 57}] (* Alonso del Arte, May 30 2006 *)

Accumulate[EulerPhi[Range[0, 60]]] (* Harvey P. Dale, Aug 27 2011 *)

PROG

(PARI) a(n)=sum(k=1, n, eulerphi(k)) \\ Charles R Greathouse IV, Jun 16 2011

(Haskell)

a002088 n = a002088_list !! n

a002088_list = scanl (+) 0 a000010_list -- Reinhard Zumkeller, Jul 29 2012

CROSSREFS

Cf. A000010, A015614, A005728, A067282, A001088, A134542.

Sequence in context: A162578 A152919 A092249 * A019332 A002491 A045958

Adjacent sequences:  A002085 A002086 A002087 * A002089 A002090 A002091

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Leonard Smiley (smiley(AT)math.uaa.alaska.edu)

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 21 13:08 EDT 2014. Contains 248377 sequences.