A006218 a(n) = Sum_{k=1..n} floor(n/k); also Sum_{k=1..n} d(k), where d = number of divisors (A000005); also number of solutions to x*y = z with 1 <= x,y,z <= n.

0, 1, 3, 5, 8, 10, 14, 16, 20, 23, 27, 29, 35, 37, 41, 45, 50, 52, 58, 60, 66, 70, 74, 76, 84, 87, 91, 95, 101, 103, 111, 113, 119, 123, 127, 131, 140, 142, 146, 150, 158, 160, 168, 170, 176, 182, 186, 188, 198, 201, 207, 211, 217, 219, 227, 231, 239, 243, 247, 249

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

The identity Sum_{k=1..n} floor(n/k) = Sum_{k=1..n} d(k) is Equation (10), p. 58, of Apostol (1976). - N. J. A. Sloane, Dec 06 2020

The "Dirichlet divisor problem" is to find a precise asymptotic estimate for this sequence - see formula lines below, also Apostol (1976), Chap. 3.

Number of increasing arithmetic progressions where n+1 is the second or later term. - Mambetov Timur, Takenov Nurdin, Haritonova Oksana (timus(AT)post.kg; oksanka-61(AT)mail.ru), Jun 13 2002. E.g., a(3) = 5 because there are 5 such arithmetic progressions: (1, 2, 3, 4); (2, 3, 4); (1, 4); (2, 4); (3, 4).

Binomial transform of A001659.

Area covered by overlapped partitions of n, i.e., sum of maximum values of the k-th part of a partition of n into k parts. - Jon Perry, Sep 08 2005

Equals inverse Mobius transform of A116477. - Gary W. Adamson, Aug 07 2008

The Polymath project (see the Tao-Croot-Helfgott link) sketches an algorithm for computing a(n) in essentially cube root time, see section 2.1. - Charles R Greathouse IV, Oct 10 2010 [Sladkey gives another. - Charles R Greathouse IV, Oct 02 2017]

The Dirichlet inverse starts (offset 1) 1, -3, -5, 1, -10, 16, -16, 1, 2, 33, -29, -6, -37, 55, 55, -1, -52, -5, -60, ... - R. J. Mathar, Oct 17 2012

The inverse Mobius transforms yields A143356. - R. J. Mathar, Oct 17 2012

An improved approximation vs. Dirichlet is: a(n) = log(Gamma(n+1)) + 2n*gamma. Using sample ranges of {n = k^2-k to k^2 + (k-1)} the means of the new error term are < +- 0.5 up to k=150, except on two values of k. These ranges appear to give means closest to zero for such small sample sizes. It is not clear sample means remain < +- 0.5 at larger k. The standard deviations are ~(n*log(n))^(1/4)/2, with n near sample range center. - Richard R. Forberg, Jan 06 2015

The values of n for which a(n) is even are given by 4*m^2 <= n <= 4*m(m+1) for m >= 0. Example: for m=1 the values of n are 4 <= n <= 8 for which a(4) to a(8) are even. - G. C. Greubel, Sep 30 2015

For n > 0, a(n) = count(x|y), 1 <= y <= x <= n, that is, the number of pairs in the ordered list of x and y, where y divides x, up to and including n. - Torlach Rush, Jan 31 2017

a(n) is also the total number of partitions of all positive integers <= n into equal parts. - Omar E. Pol, May 29 2017

a(n) is the rank of the join of the set of elements of rank n in Young's lattice, the lattice of all integer partitions ordered by inclusion of their Ferrers diagrams. - Geoffrey Critzer, Jul 11 2018

a(n) always has the same parity as floor(sqrt(n)) = A000196(n): see A211264 (proof in Diophante link). - Bernard Schott, Feb 13 2021

From Omar E. Pol, Feb 16 2021: (Start)

Apart from initial zero this is the convolution of A341062 and A000027.

Nonzero terms convolved with A341062 gives A055507. (End)

From Bernard Schott, Apr 17 2022: (Start)

a(n-1) is the number of lattice points in the first quadrant lying under the hyperbola x*y = n, excluding the lattice points on the axes.

a(n) is the number of lattice points in the first quadrant lying on or under the hyperbola x*y = n, excluding the lattice points on the axes. (Reference Hari Kishan). (End)

Let tiles Tn (for n >= 1) be initially placed on square n on an infinite 1D board. At each step, the leftmost unblocked tile (i.e., the top tile in the leftmost stack) jumps forward exactly n squares. Tiles can stack, and only the top tile of a stack can move. This sequence gives the step number when tile n moves for the first time. - Ali Sada, May 23 2025

Examples

			a(3) = 5 because 3 + floor(3/2) + 1 = 3 + 1 + 1 = 5. Or tau(1) + tau(2) + tau(3) = 1 + 2 + 2 = 5.
a(4) = 8 because 4 + floor(4/2) + floor(4/3) + 1 = 4 + 2 + 1 + 1 = 8. Or
tau(1) + tau(2) + tau(3) + tau(4) = 1 + 2 + 2 + 3 = 8.
a(5) = 10 because 5 + floor(5/2) + floor(5/3) + floor (5/4) + 1 = 5 + 2 + 1 + 1 + 1 = 10. Or tau(1) + tau(2) + tau(3) + tau(4) + tau(5) = 1 + 2 + 2 + 3 + 2 = 10.
		

References

• T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
• K. Chandrasekharan, Introduction to Analytic Number Theory. Springer-Verlag, 1968, Chap. VI.
• K. Chandrasekharan, Arithmetical Functions. Springer-Verlag, 1970, Chapter VIII, pp. 194-228. Springer-Verlag, Berlin.
• P. G. L. Dirichlet, Werke, Vol. ii, pp. 49-66.
• M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972, p. 7.
• M. N. Huxley, Area, Lattice Points and Exponential Sums, Oxford, 1996; p. 239.
• Hari Kishan, Number Theory, Krishna, Educational Publishers, 2014, Theorem 1, p. 133.
• H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 56.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• Nurdin N. Takenov and Oksana Haritonova, Representation of positive integers by a special set of digits and sequences, in Dolmatov, S. L. et al. editors, Materials of Science, Practical seminar "Modern Mathematics".
• James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, Exercise 3.6.13 on page 107.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (first 1000 terms from T. D. Noe)
• Dorin Andrica and Ovidiu Bagdasar, On some results concerning the polygonal polynomials, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
• D. Andrica and E. J. Ionascu, On the number of polynomials with coefficients in [n], An. St. Univ. Ovidius Constanța, Vol. 22(1),2014, 13-23.
• R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.5.
• D. Berkane, O. Bordellès, and O. Ramaré, Explicit upper bounds for the remainder term in the divisor problem, Math. Comp. 81:278 (2012), pp. 1025-1051.
• Peter J. Cameron and Hamid Reza Dorbidi, Minimal cover groups, arXiv:2311.15652 [math.GR], 2023. See p. 13.
• Diophante, A1712, La même parité (in French).
• Xiaoxi Duan and M. W. Wong, The Dirichlet divisor problem, traces and determinants for complex powers of the twisted bi-Laplacian, J. of Math. Analysis and Applications, Volume 410, Issue 1, Feb 01 2014, Pages 151-157
• L. Hoehn and J. Ridenhour, Summations involving computer-related functions, Math. Mag., 62 (1989), 191-196.
• M. N. Huxley, Exponential Sums and Lattice Points III, Proc. London Math. Soc., 87 (2003), pp. 591-609.
• Vaclav Kotesovec, Graph - The asymptotic ratio (1000000 terms)
• Richard Sladkey, A successive approximation algorithm for computing the divisor summatory function, arXiv:1206.3369 [math.NT], 2012.
• Terence Tao, Ernest Croot III, and Harald Helfgott, Deterministic methods to find primes, Math. Comp. 81 (2012), 1233-1246; also at arXiv:1009.3956 [math.NT], 2010-2012.

Crossrefs

Right edge of A056535. Cf. A000005, A001659, A052511, A143236.

Row sums of triangle A003988, A010766 and A143724.

A061017 is an inverse.

It appears that the partial sums give A078567. - N. J. A. Sloane, Nov 24 2008

Cf. A116477, A051731, A055507, A161700, A004125, A212120, A341062.

Programs

Haskell

a006218 n = sum $ map (div n) [1..n]
-- Reinhard Zumkeller, Jan 29 2011

Magma

[0] cat [&+[Floor(n/k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Aug 25 2019

Maple

with(numtheory): A006218 := n->add(sigma[0](i), i=1..n);

Mathematica

Table[Sum[DivisorSigma[0, k], {k, n}], {n, 70}]
FoldList[Plus, 0, Table[DivisorSigma[0, x], {x, 61}]] //Rest (* much faster *)
Join[{0},Accumulate[DivisorSigma[0,Range[60]]]] (* Harvey P. Dale, Jan 06 2016 *)

PARI

a(n)=sum(k=1,n,n\k)

PARI

a(n)=sum(k=1,sqrtint(n),n\k)*2-sqrtint(n)^2 \\ Charles R Greathouse IV, Oct 10 2010

Python

from sympy import integer_nthroot
def A006218(n): return 2*sum(n//k for k in range(1,integer_nthroot(n,2)[0]+1))-integer_nthroot(n,2)[0]**2 # Chai Wah Wu, Mar 29 2021

Formula

a(n) = n * ( log(n) + 2*gamma - 1 ) + O(sqrt(n)), where gamma is the Euler-Mascheroni number ~ 0.57721... (see A001620), Dirichlet, 1849. Again, a(n) = n * ( log(n) + 2*gamma - 1 ) + O(log(n)*n^(1/3)). The determination of the precise size of the error term is an unsolved problem (the so-called Dirichlet divisor problem) - see references, especially Huxley (2003).

The bounds from Chandrasekharan lead to the explicit bounds n log(n) + (2 gamma - 1) n - 4 sqrt(n) - 1 <= a(n) <= n log(n) + (2 gamma - 1) n + 4 sqrt(n). - David Applegate, Oct 14 2008

a(n) = 2*(Sum_{i=1..floor(sqrt(n))} floor(n/i)) - floor(sqrt(n))^2. - Benoit Cloitre, May 12 2002

G.f.: (1/(1-x))*Sum_{k >= 1} x^k/(1-x^k). - Benoit Cloitre, Apr 23 2003

For n > 0: A027750(a(n-1) + k) = k-divisor of n, = k <= A000005(n). - Reinhard Zumkeller, May 10 2006

a(n) = A161886(n) - n + 1 = A161886(n-1) - A049820(n) + 2 = A161886(n-1) + A000005(n) - n + 2 = A006590(n) + A000005(n) - n = A006590(n+1) - n - 1 = A006590(n) + A000005(n) - n for n >= 2. a(n) = a(n-1) + A000005(n) for n >= 1. - Jaroslav Krizek, Nov 14 2009

D(n) = Sum_{m >= 2, r >= 1} (r/m^(r+1)) * Sum_{j = 1..m - 1} * Sum_{k = 0 .. m^(r+1) - 1} exp{ 2*k*pi i(p^n + (m - j)m^r) / m^(r+1) } where p is some fixed prime number. - A. Neves, Oct 04 2010

Let E(n) = a(n) - n(log n + 2 gamma - 1). Then Berkane-Bordellès-Ramaré show that |E(n)| <= 0.961 sqrt(n), |E(n)| <= 0.397 sqrt(n) for n > 5559, and |E(n)| <= 0.764 n^(1/3) log n for x > 9994. - Charles R Greathouse IV, Jul 02 2012

a(n) = Sum_{k = 1..floor(sqrt(n))} A005408(floor((n/k) - (k-1))). - Gregory R. Bryant, Apr 20 2013

Dirichlet g.f. for s > 2: Sum_{n>=1} a(n)/n^s = Sum_{k>=1} (Zeta(s-1) - Sum_{n=1..k-1} (HurwitzZeta(s,n/k)*n/k^s))/k. - Mats Granvik, Sep 24 2017

From Ridouane Oudra, Dec 31 2022: (Start)

a(n) = n^2 - Sum_{i=1..n} Sum_{j=1..n} floor(log(i*j)/log(n+1));

a(n) = floor(sqrt(n)) + 2*Sum_{i=1..n} floor((sqrt(i^2 + 4*n) - i)/2);

a(n) = n + Sum_{i=1..n} v_2(i)*round(n/i), where v_2(i) = A007814(i). (End)