A214803 -id:A214803 - cp's OEIS frontend

A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k), cf. A000010.

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

Offset: 0

N. J. A. Sloane

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 = zeta(2)^2 = A098198 ~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
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
This function, the partial sums of phi = A000010, is sometimes denoted by (uppercase) Phi. - M. F. Hasler, Apr 18 2015
From Roger Ford, Jan 16 2016: (Start)
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.
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
                 /\
        /\      //\\
       //\\-/\-///\\\-  n=6 p=3 g=3   Each preceding arch configuration
            /\   /\                   is formed by attaching the arch
        /\-//\\-//\\-   n=5 p=3 g=3   end in the first position and the
           /\                         arch end in the last position.
          //\\
         ///\\\-/\-     n=4 p=2 g=2
           /\
          //\\-/\-      n=3 p=2 g=2
           /\-/\-       n=2 p=2 g=2
            /\-         n=1 p=1 g=1. (End)
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
2013 IMO Problem 6 shows that a(n) is the number of ways to arrange the numbers 0, 1, ..., n on a circle such that for any numbers 0 <= a < b < c < d <= n, the chord joining a and d does not intersect with the chord intersecting b and c, with rotation counted as same. - Yifan Xie, Aug 26 2025

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

A. Beiler, Recreations in the Theory of Numbers, Dover Publications, 1966, Chap. XVI.
Steven 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.
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. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.

Al Zimmermann, Table of n, a(n) for n = 0..50000 (Terms 0 to 1000 by T. D. Noe)
Dorin Andrica, Ovidiu Bagdasar, On some results concerning the polygonal polynomials, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
Art of Problem Solving, 2013 IMO Problem 6.
S. Bockting-Conrad, Y. Kashina, T. K. Petersen, and B. E. Tenner, Sós permutations, arXiv:2007.01132 [math.CO], 2020.
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, and Nithin Varma, Bipartite Graphs of Small Readability, arXiv:1805.04765 [cs.DM], 2018.
Steven R. Finch, Euler Totient Function Asymptotic Constants [Broken link]
Steven R. Finch, Euler Totient Function Asymptotic Constants [From the Wayback machine]
Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler phi function, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008, pp. 34-42.
J. Sandor, D. S. Mitrinovic, B. Crstici, Handbook of Number Theory I, Volume 1, Springer, 2005, p. 24.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
James J. Sylvester, On the number of fractions contained in any Farey series of which the limiting number is given, 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).
J. J. Sylvester, The collected mathematical papers of James Joseph Sylvester, vol. 2, vol. 3, vol. 4.
A. Walfisz, Weylsche Exponentialsummen in der neueren Zahlentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin 1963.
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.
R. G. Wilson, v, Letter to N. J. A. Sloane, Jan 24 1989

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

List([1..60],n->Sum([1..n],i->Phi(i))); # Muniru A Asiru, Jul 31 2018

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

[&+[EulerPhi(i): i in [1..n]]: n in [1..60]]; // Vincenzo Librandi, Aug 01 2018

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

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 *)

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

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

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

from functools import lru_cache
@lru_cache(maxsize=None)
def A002088(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A002088(k1)-1)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

[sum(euler_phi(k) for k in (1..n)) for n in (0..60)] # G. C. Greubel, Nov 25 2018

a(n) = (3*n^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
a(n) = A000217(n) - A063985(n) = A018805(n) - A015614(n). - Reinhard Zumkeller, Jan 21 2013
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
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
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
a(n) = A005728(n) - 1, for n >= 0. - Wolfdieter Lang, Nov 22 2016
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
a(n) = A015614(n)+1. - R. J. Mathar, Apr 26 2023
a(n) = A000217(n) - Sum{k=2..n} a(floor(n/k)). From summing over Id = 1 (Dirichlet convolution) phi. - Jason Xu, Jul 31 2024
a(n) = Sum_{k=1..n} k*A002321(floor(n/k)). - Ridouane Oudra, Jul 03 2025

Additional comments from Len Smiley

A165900 a(n) = n^2 - n - 1.

Original entry on oeis.org

-1, -1, 1, 5, 11, 19, 29, 41, 55, 71, 89, 109, 131, 155, 181, 209, 239, 271, 305, 341, 379, 419, 461, 505, 551, 599, 649, 701, 755, 811, 869, 929, 991, 1055, 1121, 1189, 1259, 1331, 1405, 1481, 1559, 1639, 1721, 1805, 1891, 1979, 2069, 2161, 2255

Offset: 0

Philippe Deléham, Sep 29 2009

Previous name was: Values of Fibonacci polynomial n^2 - n - 1.
Shifted version of the array denoted rB(0,2) in A132382, whose e.g.f. is exp(x)(1-x)^2. Taking the derivative gives the e.g.f. of this sequence. - Tom Copeland, Dec 02 2013
The Fibonacci numbers are generated by the series x/(1 - x - x^2). - T. D. Noe, Dec 04 2013
Absolute value of expression f(k)*f(k+1) - f(k-1)*f(k+2) where f(1)=1, f(2)=n. Sign is alternately +1 and -1. - Carmine Suriano, Jan 28 2014 [Can anybody clarify what is meant here? - Joerg Arndt, Nov 24 2014]
Carmine's formula is a special case related to 4 consecutive terms of a Fibonacci sequence. A generalization of this formula is |a(n)| = |f(k+i)*f(k+j) - f(k)*f(k+i+j)|/F(i)*F(j), where f denotes a Fibonacci sequence with the initial values 1 and n, and F denotes the original Fibonacci sequence A000045. The same results can be obtained with the simpler formula |a(n)| = |f(k+1)^2 - f(k)^2 - f(k+1)*f(k)|. Everything said so far is also valid for Fibonacci sequences f with the initial values f(1) = n - 2, f(2) = 2*n - 3. - Klaus Purath, Jun 27 2022
a(n) is the total number of dollars won when using the Martingale method (bet $1, if win then continue to bet $1, if lose then double next bet) for n trials of a wager with exactly one loss, n-1 wins. For the case with exactly one win, n-1 losses, see A070313. - Max Winnick, Jun 28 2022
Numbers m such that 4*m+5 is a square b^2, where b = 2*n -1, for m = a(n). - Klaus Purath, Jul 23 2022

			G.f. = -1 - x + x^2 + 5*x^3 + 11*x^4 + 19*x^5 + 29*x^6 + 41*x^7 + ... - _Michael Somos_, Mar 23 2023

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Joseph J. Heed and Lucille Kelly, An interesting sequence of Fibonacci sequence generators, Fibonacci Quarterly, 13 (1975), pp. 29-30.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

A028387 and A110331 are very similar sequences.
Cf. A000045, A005843, A015614, A070313, A132382, A152015, A188652, A214803.
Other quadratics: A002061, A002378, A005563, A008865, A014206, A014209, A028552, A034856.

a165900 n = n * (n - 1) - 1  -- Reinhard Zumkeller, Jul 29 2012

Table[n^2 - n - 1, {n, 0, 50}] (* Ron Knott, Oct 27 2010 *)
LinearRecurrence[{3,-3,1},{-1,-1,1},60] (* Harvey P. Dale, Jul 05 2021 *)

a(n)=n^2-n-1 \\ Charles R Greathouse IV, Jan 12 2012

a(n+2) = (n+1)*a(n+1) - (n+2)*a(n).
G.f.: (x^2+2*x-1)/(1-x)^3.
E.g.f.: exp(x)*(x^2-1).
a(n) = - A188652(2*n) for n > 0. - Reinhard Zumkeller, Apr 13 2011
a(n) = A214803(A015614(n+1)) for n > 0. - Reinhard Zumkeller, Jul 29 2012
a(n+1) = a(n) + A005843(n) = A002378(n) - 1. - Ivan N. Ianakiev, Feb 18 2013
a(n+2) = A028387(n). - Michael B. Porter, Sep 26 2018
From Klaus Purath, Aug 25 2022: (Start)
a(2*n) = n*(a(n+1) - a(n-1)) -1.
a(2*n+1)  = (2*n+1)*(a(n+1) - a(n)) - 1.
a(n+2) = a(n) + 4*n + 2.
a(n) = A014206(n-1) - 3 = A002061(n-1) - 2.
a(n) = A028552(n-2) + 1 = A014209(n-2) + 2 = 2* A034856(n-2) + 3.
a(n) = A008865(n-1) + n = A005563(n-1) - n.
a(n) = A014209(n-3) + 2*n = A028387(n-1) - 2*n.
a(n) = A152015(n)/n, n != 0.
(a(n+k) - a(n-k))/(2*k) = 2*n-1, for any k.
(End)
For n > 1, 1/a(n) = Sum_{k>=1} F(k)/n^(k+1), where F(n) = A000045(n). - Diego Rattaggi, Nov 01 2022
a(n) = a(1-n) for all n in Z. - Michael Somos, Mar 23 2023
For n > 1, 1/a(n) = Sum_{k>=1} F(2k)/((n+1)^(k+1)), where F(2n) = A001906(n). - Diego Rattaggi, Jan 20 2025
From Amiram Eldar, May 11 2025: (Start)
Sum_{n>=1} 1/a(n) = tan(sqrt(5)*Pi/2)*Pi/sqrt(5).
Product_{n>=3} 1 - 1/a(n) = -sec(sqrt(5)*Pi/2)*Pi/6.
Product_{n>=2} 1 + 1/a(n) = -sec(sqrt(5)*Pi/2)*Pi. (End)

a(22) corrected by Reinhard Zumkeller, Apr 13 2011

Better name from Joerg Arndt, Oct 26 2024

A015614 a(n) = -1 + Sum_{i=1..n} phi(i).

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 17, 21, 27, 31, 41, 45, 57, 63, 71, 79, 95, 101, 119, 127, 139, 149, 171, 179, 199, 211, 229, 241, 269, 277, 307, 323, 343, 359, 383, 395, 431, 449, 473, 489, 529, 541, 583, 603, 627, 649, 695, 711, 753, 773, 805, 829, 881, 899, 939, 963

Offset: 1

Olivier Gérard

nonn

Number of elements in the set {(x,y): 1 <= x < y <= n, 1=gcd(x,y)}. - Michael Somos, Jun 13 1999
Number of fractions in (Haros)-Farey series of order n.
The asymptotic limit for the sequence is a(n) ~ 3*n^2/Pi^2. - Martin Renner, Dec 12 2011
2*a(n) is the number of proper fractions reduced to lowest terms with numerator and denominator less than or equal to n in absolute value. - Stefano Spezia, Aug 09 2019

			x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 11*x^6 + 17*x^7 + 21*x^8 +27*x^9 + ...

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966, pp. 170-171.

Stanislav Sykora, Table of n, a(n) for n = 1..10000
James J. Sylvester, On the number of fractions contained in any Farey series of which the limiting number is given, in: London, Edinburgh and Dublin Philosophical Magazine (5th series) 15 (1883), p. 251.

Cf. A000010, A002088, A018805, A185670.

Column k=2 of triangle A186974.

List([1..60],n->Sum([1..n],i->Phi(i)))-1; # Muniru A Asiru, Jul 31 2018

a015614 = (subtract 1) . a002088  -- Reinhard Zumkeller, Jul 29 2012

[-1+&+[EulerPhi(i): i in [1..n]]:n in [1..56]]; // Marius A. Burtea, Aug 09 2019

with(numtheory): a:=n->add(phi(i),i=1..n): seq(a(n)-1,n=1..60); # Muniru A Asiru, Jul 31 2018

Table[Sum[EulerPhi[m],{m,1,n}]-1,{n,1,56}] (* Geoffrey Critzer, May 16 2014 *)
Table[Length[FareySequence[n]]-2,{n,60}] (* Harvey P. Dale, Jan 30 2025 *)

{a(n) = if( n<1, 0, sum(k=1,n,eulerphi(k), -1))} /* Michael Somos, Sep 06 2013 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A015614(n): # based on second formula in A018805
    if n == 0:
        return -1
    c, j = 2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A015614(k1)+1)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

a(n) = -1 + A002088(n).
a(n) = (A018805(n) - 1)/2. - Reinhard Zumkeller, Apr 08 2006
For n > 1: A214803(a(n)) = A165900(n-1). - Reinhard Zumkeller, Jul 29 2012
a(n) = A018805(n) - A002088(n). - Reinhard Zumkeller, Jan 21 2013
G.f.: (1/(1 - x)) * (-x + Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020
a(n) = A000217(n-1) - A185670(n). - Hossein Mahmoodi, Jan 20 2022

More terms from Reinhard Zumkeller, Apr 08 2006

cp's OEIS Frontend

A002088 Sum of totient function: a(n) = Sum_{k=1..n} phi(k), cf. A000010.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Sage

Formula

Extensions

A165900 a(n) = n^2 - n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A015614 a(n) = -1 + Sum_{i=1..n} phi(i).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions