A018805 -id:A018805 - 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

A048691 a(n) = d(n^2), where d(k) = A000005(k) is the number of divisors of k.

Original entry on oeis.org

1, 3, 3, 5, 3, 9, 3, 7, 5, 9, 3, 15, 3, 9, 9, 9, 3, 15, 3, 15, 9, 9, 3, 21, 5, 9, 7, 15, 3, 27, 3, 11, 9, 9, 9, 25, 3, 9, 9, 21, 3, 27, 3, 15, 15, 9, 3, 27, 5, 15, 9, 15, 3, 21, 9, 21, 9, 9, 3, 45, 3, 9, 15, 13, 9, 27, 3, 15, 9, 27, 3, 35, 3, 9, 15, 15, 9, 27, 3, 27

Offset: 1

David Johnson-Davies

Inverse Moebius transform of A034444: Sum_{d|n} 2^omega(d), where omega(n) = A001221(n) is the number of distinct primes dividing n.
Number of elements in the set {(x,y): x|n, y|n, gcd(x,y)=1}.
Number of elements in the set {(x,y): lcm(x,y)=n}.
Also gives total number of positive integral solutions (x,y), order being taken into account, to the optical or parallel resistor equation 1/x + 1/y = 1/n. Indeed, writing the latter as X*Y=N, with X=x-n, Y=y-n, N=n^2, the one-to-one correspondence between solutions (X, Y) and (x, y) is obvious, so that clearly, the solution pairs (x, y) are tau(N)=tau(n^2) in number. - Lekraj Beedassy, May 31 2002
Number of ordered pairs of positive integers (a,c) such that n^2 - ac = 0. Therefore number of quadratic equations of the form ax^2 + 2nx + c = 0 where a,n,c are positive integers and each equation has two equal (rational) roots, -n/a. (If a and c are positive integers, but, instead, the coefficient of x is odd, it is impossible for the equation to have equal roots.) - Rick L. Shepherd, Jun 19 2005
Problem A1 on the 21st Putnam competition in 1960 (see John Scholes link) asked for the number of pairs of positive integers (x,y) such that xy/(x+y) = n: the answer is a(n); for n = 4, the a(4) = 5 solutions (x,y) are (5,20), (6,12), (8,8), (12,6), (20,5). - Bernard Schott, Feb 12 2023
Numbers k such that a(k)/d(k) is an integer are in A217584 and the corresponding quotients are in A339055. - Bernard Schott, Feb 15 2023

A. M. Gleason et al., The William Lowell Putnam Mathematical Competitions, Problems & Solutions:1938-1960 Soln. to Prob. 1 1960, p. 516, MAA, 1980.
Ross Honsberger, More Mathematical Morsels, Morsel 43, pp. 232-3, DMA No. 10 MAA, 1991.
Loren C. Larson, Problem-Solving Through Problems, Prob. 3.3.7, p. 102, Springer 1983.
Alfred S. Posamentier and Charles T. Salkind, Challenging Problems in Algebra, Prob. 9-9 pp. 143 Dover NY, 1988.
D. O. Shklarsky et al., The USSR Olympiad Problem Book, Soln. to Prob. 123, pp. 28, 217-8, Dover NY.
Wacław Sierpiński, Elementary Theory of Numbers, pp. 71-2, Elsevier, North Holland, 1988.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 91.
Charles W. Trigg, Mathematical Quickies, Question 194, pp. 53, 168, Dover, 1985.

Enrique Pérez Herrero, Table of n, a(n) for n = 1..10000
Ovidiu Bagdasar, On Some Functions Involving the lcm and gcd of Integer Tuples.
Umberto Cerruti, Percorsi tra i numeri (in Italian), pages 3-4.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seq., Vol. 6 (2003), Article 03.1.6.
John Scholes, Problem A1 of 21st Putnam Competition 1960, 2002. [Wayback Machine link]
Wacław Sierpiński, Elementary Theory of Numbers, Warszawa 1964.
Index to sequences related to Olympiads and other Mathematical competitions.

Cf. A000005, A034444, Mobius transf. of A035116, A048785, A061391, A018805, A002088, A015614, A018892, A063647, A182139.
Partial sums give A061503.
For similar LCM sequences, see A070919, A070920, A070921.
Cf. A005408, A124010.
For the earliest occurrence of 2n-1 see A016017.
Cf. A001620, A082633, A217584, A339055.

a048691 = product . map (a005408 . fromIntegral) . a124010_row
-- Reinhard Zumkeller, Jul 12 2012

A048691[n_]:=DivisorSigma[0,n^2] (* Enrique Pérez Herrero, May 30 2010 *)
DivisorSigma[0,Range[80]^2] (* Harvey P. Dale, Apr 08 2015 *)

numlib::tau (n^2)$ n=1..90 // Zerinvary Lajos, May 13 2008

A048691(n)=prod(i=1,#n=factor(n)[,2],n[i]*2+1) /* or, of course, a(n)=numdiv(n^2) */ \\ M. F. Hasler, Dec 30 2007

for(n=1, 100, print1(direuler(p=2, n, (1 - X^2)/(1 - X)^3)[n], ", ")) \\ Vaclav Kotesovec, Aug 21 2021

[sigma(n**2, 0) for n in range(1, 81)] # Stefano Spezia, Jul 14 2025

a(n) = A000005(A000290(n)).
tau(n^2) = Sum_{d|n} mu(n/d)*tau(d)^2, where mu(n) = A008683(n), cf. A061391.
Multiplicative with a(p^e) = 2e+1. - Vladeta Jovovic, Jul 23 2001
Also a(n) = Sum_{d|n} (tau(d)*moebius(n/d)^2), Dirichlet convolution of A000005 and A008966. - Benoit Cloitre, Sep 08 2002
a(n) = A055205(n) + A000005(n). - Reinhard Zumkeller, Dec 08 2009
Dirichlet g.f.: (zeta(s))^3/zeta(2s). - R. J. Mathar, Feb 11 2011
a(n) = Sum_{d|n} 2^omega(d). Inverse Mobius transform of A034444. - Enrique Pérez Herrero, Apr 14 2012
G.f.: Sum_{k>=1} 2^omega(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Mar 10 2018
Sum_{k=1..n} a(k) ~ n*(6/Pi^2)*(log(n)^2/2 + log(n)*(3*gamma - 1) + 1 - 3*gamma + 3*gamma^2 - 3*gamma_1 + (2 - 6*gamma - 2*log(n))*zeta'(2)/zeta(2) + (2*zeta'(2)/zeta(2))^2 - 2*zeta''(2)/zeta(2)), where gamma is Euler's constant (A001620) and gamma_1 is the first Stieltjes constant (A082633). - Amiram Eldar, Jan 26 2023

Additional comments from Vladeta Jovovic, Apr 29 2001

A005728 Number of fractions in Farey series of order n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, 81, 97, 103, 121, 129, 141, 151, 173, 181, 201, 213, 231, 243, 271, 279, 309, 325, 345, 361, 385, 397, 433, 451, 475, 491, 531, 543, 585, 605, 629, 651, 697, 713, 755, 775, 807, 831, 883, 901, 941, 965

Offset: 0

N. J. A. Sloane

Sometimes called Phi(n).
Leo Moser found an interesting way to generate this sequence, see Gardner.
a(n) is a prime number for nine consecutive values of n: n = 1, 2, 3, 4, 5, 6, 7, 8, 9. - Altug Alkan, Sep 26 2015
Named after the English geologist and writer John Farey, Sr. (1766-1826). - Amiram Eldar, Jun 17 2021

			a(5)=11 because the fractions are 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.

Martin Gardner, The Last Recreations, 1997, chapter 12.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, a foundation for computer science, Chapter 4.5 - Relative Primality, pages 118 - 120 and Chapter 9 - Asymptotics, Problem 6, pages 448 - 449, Addison-Wesley Publishing Co., Reading, Mass., 1989.
William Judson LeVeque, Topics in Number Theory, Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
Andrey O. Matveev, Farey Sequences, De Gruyter, 2017, Table 1.7.
Leo Moser, Solution to Problem P42, Canadian Mathematical Bulletin, Vol. 5, No. 3 (1962), pp. 312-313.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antoine Mathys, Table of n, a(n) for n = 0..20000 (terms 0 to 1000 from T. D. Noe)
Richard K. Guy, Letter to N. J. A. Sloane, 1986.
Richard K. Guy, Letter to N. J. A. Sloane, 1987.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]
Brady Haran and Grant Sanderson, Prime Pyramid (with 3Blue1Brown), Numberphile video (2022).
Sameen Ahmed Khan, Mathematica notebook.
Sameen Ahmed Khan, How Many Equivalent Resistances?, RESONANCE, May 2012.
Sameen Ahmed Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.), Vol. 122, No. 2 (May 2012), pp. 153-162.
Sameen Ahmed Khan, Beginning to count the number of equivalent resistances, Indian Journal of Science and Technology, Vol. 9, No. 44 (2016), pp. 1-7.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
Shmuel Schreiber and N. J. A. Sloane, Correspondence, 1980.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021. (Includes this sequence)
Vladimir Sukhoy and Alexander Stoytchev, Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle, Scientific Reports, Vol. 10, Article No. 4852 (2020).
Vladimir Sukhoy and Alexander Stoytchev, Formulas and algorithms for the length of a Farey sequence, Scientific Reports, Vol. 11 (2021), Article No. 22218.
Eric Weisstein's World of Mathematics, Farey Sequence.
Wikipedia, Farey sequence.

For the Farey series see A006842/A006843.
Essentially the same as A049643.
Cf. A002088, A055197, A055201.

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

a005728 n = a005728_list
a005728_list = scanl (+) 1 a000010_list
-- Reinhard Zumkeller, Aug 04 2012

[1] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // Vincenzo Librandi, Sep 27 2015

A005728 := proc(n)
    1+add(numtheory[phi](i),i=1..n) ;
end proc:
seq(A005728(n),n=0..80) ; # R. J. Mathar, Nov 29 2017

Accumulate@ Array[ EulerPhi, 54, 0] + 1
f[n_] := 1 + Sum[ EulerPhi[m], {m, n}]; Array[f, 55, 0] (* or *)
f[n_] := (Sum[ MoebiusMu[m] Floor[n/m]^2, {m, n}] + 3)/2; f[0] = 1; Array[f, 55, 0] (* or *)
f[n_] := n (n + 3)/2 - Sum[f[Floor[n/m]], {m, 2, n}]; f[0] = 1; Array[f, 55, 0] (* Robert G. Wilson v, Sep 26 2015 *)
a[n_] := If[n == 0, 1, FareySequence[n] // Length];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2022 *)

a(n)=1+sum(k=1,n,eulerphi(k)) \\ Charles R Greathouse IV, Jun 03 2013

from functools import lru_cache
@lru_cache(maxsize=None)
def A005728(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*A005728(k1)-3)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

a(n) = 1 + Sum_{i=1..n} phi(i).
a(n) = n*(n+3)/2 - Sum_{k=2..n} a(floor(n/k)). - David W. Wilson, May 25 2002
a(n) = a(n-1) + phi(n) with a(0) = 1. - Arkadiusz Wesolowski, Oct 13 2012
a(n) = 1 + A002088(n). - Robert G. Wilson v, Sep 26 2015

A010766 Triangle read by rows: row n gives the numbers floor(n/k), k = 1..n.

Original entry on oeis.org

1, 2, 1, 3, 1, 1, 4, 2, 1, 1, 5, 2, 1, 1, 1, 6, 3, 2, 1, 1, 1, 7, 3, 2, 1, 1, 1, 1, 8, 4, 2, 2, 1, 1, 1, 1, 9, 4, 3, 2, 1, 1, 1, 1, 1, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 13, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1

Offset: 1

N. J. A. Sloane

Number of times k occurs as divisor of numbers not greater than n. - Reinhard Zumkeller, Mar 19 2004
Viewed as a partition, row n is the smallest partition that contains every partition of n in the usual ordering. - Franklin T. Adams-Watters, Mar 11 2006
Row sums = A006218. - Gary W. Adamson, Oct 30 2007
A014668 = eigensequence of the triangle. A163313 = A010766 * A014668 (diagonalized) as an infinite lower triangular matrix. - Gary W. Adamson, Jul 30 2009
A018805(T(n,k)) = A242114(n,k). - Reinhard Zumkeller, May 04 2014
Viewed as partitions, all rows are self-conjugate. - Matthew Vandermast, Sep 10 2014
Row n is the partition whose Young diagram is the union of Young diagrams of all partitions of n (rewording of Franklin T. Adams-Watters's comment). - Harry Richman, Jan 13 2022

			Triangle starts:
   1:  1;
   2:  2,  1;
   3:  3,  1, 1;
   4:  4,  2, 1, 1;
   5:  5,  2, 1, 1, 1;
   6:  6,  3, 2, 1, 1, 1;
   7:  7,  3, 2, 1, 1, 1, 1;
   8:  8,  4, 2, 2, 1, 1, 1, 1;
   9:  9,  4, 3, 2, 1, 1, 1, 1, 1;
  10: 10,  5, 3, 2, 2, 1, 1, 1, 1, 1;
  11: 11,  5, 3, 2, 2, 1, 1, 1, 1, 1, 1;
  12: 12,  6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1;
  13: 13,  6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1;
  14: 14,  7, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1;
  15: 15,  7, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1;
  16: 16,  8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1;
  17: 17,  8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  18: 18,  9, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  19: 19,  9, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  20: 20, 10, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  ...

Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 407.

T. D. Noe, Rows n = 1..50 of triangle, flattened

Another version of A003988.
Finite differences of rows: A075993.
Cf. related triangles: A002260, A013942, A051731, A163313, A277646, A277647.
Cf. related sequences: A006218, A014668, A115725.
Columns of this triangle:
T(n,1) = n,
T(n,2) = A008619(n-2) for n>1,
T(n,3) = A008620(n-3) for n>2,
T(n,4) = A008621(n-4) for n>3,
T(n,5) = A002266(n) for n>4,
T(n,n) = A000012(n) = 1.
Rows of this triangle (with infinite trailing zeros):
T(1,k) = A000007(k-1),
T(2,k) = A033322(k),
T(3,k) = A278105(k),
T(4,k) = A033324(k),
T(5,k) = A033325(k),
T(6,k) = A033326(k),
T(7,k) = A033327(k),
T(8,k) = A033328(k),
T(9,k) = A033329(k),
T(10,k) = A033330(k),
...
T(99,k) = A033419(k),
T(100,k) = A033420(k),
T(1000,k) = A033421(k),
T(10^4,k) = A033422(k),
T(10^5,k) = A033427(k),
T(10^6,k) = A033426(k),
T(10^7,k) = A033425(k),
T(10^8,k) = A033424(k),
T(10^9,k) = A033423(k).

a010766 = div
a010766_row n = a010766_tabl !! (n-1)
a010766_tabl = zipWith (map . div) [1..] a002260_tabl
-- Reinhard Zumkeller, Apr 29 2015, Aug 13 2013, Apr 13 2012

seq(seq(floor(n/k),k=1..n),n=1..20); # Robert Israel, Sep 01 2014

Flatten[Table[Floor[n/k],{n,20},{k,n}]] (* Harvey P. Dale, Nov 03 2012 *)

a(n)=t=floor((-1+sqrt(1+8*(n-1)))/2);(t+1)\(n-t*(t+1)/2) \\ Edward Jiang, Sep 10 2014

T(n, k) = sum(i=1, n, (i % k) == 0); \\ Michel Marcus, Apr 08 2017

G.f.: 1/(1-x)*Sum_{k>=1} x^k/(1-y*x^k). - Vladeta Jovovic, Feb 05 2004
Triangle A010766 = A000012 * A051731 as infinite lower triangular matrices. - Gary W. Adamson, Oct 30 2007
Equals A000012 * A051731 as infinite lower triangular matrices. - Gary W. Adamson, Nov 14 2007
Let T(n,0) = n+1, then T(n,k) = (sum of the k preceding elements in the previous column) minus (sum of the k preceding elements in same column). - Mats Granvik, Gary W. Adamson, Feb 20 2010
T(n,k) = (n - A048158(n,k)) / k. - Reinhard Zumkeller, Aug 13 2013
T(n,k) = 1 + T(n-k,k) (where T(n-k,k) = 0 if n < 2*k). - Robert Israel, Sep 01 2014
T(n,k) = T(floor(n/k),1) if k>1; T(n,1) = 1 - Sum_{i=2..n} A008683(i)*T(n,i). If we modify the formula to T(n,1) = 1 - Sum_{i=2..n} A008683(i)*T(n,i)/i^s, where s is a complex variable, then the first column becomes the partial sums of the Riemann zeta function. - Mats Granvik, Apr 27 2016

Cross references edited by Jason Kimberley, Nov 23 2016

A038567 Denominators in canonical bijection from positive integers to positive rationals <= 1.

Original entry on oeis.org

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, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16

Offset: 0

N. J. A. Sloane

n occurs phi(n) times (cf. A000010).
Least k such that phi(1) + phi(2) + phi(3) + ... + phi(k) >= n. - Benoit Cloitre, Sep 17 2002
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.]
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

			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.

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.
Hans Lauwerier, Fractals, Princeton University Press, 1991, p. 23.

David Wasserman, Table of n, a(n) for n = 0..100000
Paul Yiu, Recreational Mathematics, 24.3.1 Appendix: Two enumerations of the rational numbers in (0,1), page 633. [Wayback Machine link]
Index entries for "core" sequences.
Index entries for sequences related to enumerating the rationals.
Index entries for sequences related to Stern's sequences.

Cf. A020652, A020653, A038566 - A038569, A093602, A182972, A182973 - A182976.
A054427 gives mapping to Stern-Brocot tree.
Cf. A037162.

import Data.List (genericTake)
a038567 n = a038567_list !! n
a038567_list = concatMap (\x -> genericTake (a000010 x) $ repeat x) [1..]
-- Reinhard Zumkeller, Dec 16 2013, Jul 29 2012

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)

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 *)
Flatten[Table[Table[n,{EulerPhi[n]}],{n,20}]] (* Harvey P. Dale, Mar 12 2013 *)

a(n)=if(n<0,0,s=1; while(sum(i=1,s,eulerphi(i))

from sympy import totient
def a(n):
    s=1
    while sum(totient(i) for i in range(1, s + 1))Indranil Ghosh, May 23 2017

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)*((A002088(k1)<<1)-1)
        j, k1 = j2, n//j2
    return n*(n-1)-c+j>>1
def A038567(n):
    kmin, kmax = 0, 1
    while A002088(kmax) <= n:
        kmax <<= 1
    kmin = kmax>>1
    while True:
        kmid = kmax+kmin>>1
        if A002088(kmid) > n:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Jun 10 2025

From Henry Bottomley, Dec 18 2000: (Start)
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]
n = a(A015614(n)) = a(A002088(n)) - 1 = a(A002088(n-1)). (End)
a(n) = A002024(A169581(n)). - Reinhard Zumkeller, Dec 02 2009
a(A002088(n)) = n for n > 1. - Reinhard Zumkeller, Jul 29 2012
a(n) = A071912(2*n+1). - Reinhard Zumkeller, Dec 16 2013
a(n) ~ c * sqrt(n), where c = Pi/sqrt(3) = 1.813799... (A093602). - Amiram Eldar, Dec 27 2024

More terms from Erich Friedman

A088453 Decimal expansion of 1/zeta(3).

Original entry on oeis.org

8, 3, 1, 9, 0, 7, 3, 7, 2, 5, 8, 0, 7, 0, 7, 4, 6, 8, 6, 8, 3, 1, 2, 6, 2, 7, 8, 8, 2, 1, 5, 3, 0, 7, 3, 4, 4, 1, 7, 0, 5, 6, 3, 9, 7, 7, 3, 3, 7, 2, 8, 0, 7, 9, 2, 7, 9, 6, 7, 0, 3, 3, 2, 8, 6, 4, 4, 5, 7, 8, 7, 9, 1, 7, 2, 3, 4, 7, 9, 8, 8, 8, 2, 1, 3, 6, 5, 6, 6, 8, 9, 8, 9, 9, 6, 5, 3, 0, 4, 0, 9, 8

Offset: 0

Eric W. Weisstein, Sep 30 2003

This is the probability that three randomly chosen integers are relatively prime (see A018805). - Gary McGuire, Dec 13 2004
This is also the probability that a random integer is cubefree. - Eugene Salamin, Dec 13 2004
On the other hand, the probability that three randomly-chosen integers are pairwise relatively prime is given by A065473. - Charles R Greathouse IV, Nov 14 2011
This is also the 'probability' that a random algebraic number's denominator is equal to its leading coefficient, see Arno, Robinson, & Wheeler. - Charles R Greathouse IV, Nov 12 2014
This is the probability that a random point on a cubic lattice is visible from the origin, i.e., there is no other lattice point that lies on the line segment between this point and the origin. - Amiram Eldar, Jul 08 2020

			0.831907372580707468683126278821530734417...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 1.6, p. 41.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 29.

Steven Arno, M. L. Robinson, and Ferell S. Wheeler, On denominators of algebraic numbers and integer polynomials, Journal of Number Theory 57:2 (April 1996), pp. 292-302.
Eric Weisstein's World of Mathematics, Relatively Prime.

Cf. A002117, A008683.

RealDigits[1/Zeta[3],10,120][[1]] (* Harvey P. Dale, May 31 2019 *)

fpprec : 200$ bfloat( 1/zeta(3))$ bfloat(%); /* Martin Ettl, Oct 15 2012 */

1/zeta(3) \\ Charles R Greathouse IV, Nov 12 2014

Equals 1/A002117.
From Amiram Eldar, Aug 20 2020: (Start)
Equals Sum_{k>=1} mu(k)/k^3, where mu is the Möbius function (A008683).
Equals Product_{p prime} (1 - 1/p^3). (End)

Entry revised by N. J. A. Sloane, Dec 16 2004

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

A177853 Partial sums of A018805.

Views

Author

Keywords

Links

Programs

Haskell

Mathematica

Formula

A122507 Triangle in which row n contains the first n terms of A018805.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A122506 A symmetrical triangular array based on A018805 constructed by hand by adding ones between the primes and making the result symmetrical.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

A048691 a(n) = d(n^2), where d(k) = A000005(k) is the number of divisors of k.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

MuPAD

PARI

PARI

Sage

Formula

Extensions

A005728 Number of fractions in Farey series of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell