

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.
(Formerly M2432)


159



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The "Dirichlet divisor problem" is to find a precise asymptotic estimate for this sequence  see formula lines below.
Number of increasing arithmetic progressions where n + 1 is the second or later term.  Mambetov Timur, Takenov Nurdin, Haritonova Oksana (timus(AT)post.kg; oksanka61(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 kth 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 subsequence of prime partial sums of A000005 begins: a(2) = 3, a(3) = 5, a(9) = 23, a(11) = 29, a(13) = 37, a(14) = 41, a(28) = 101, a(29) = 103, a(31) = 113, a(34) = 127, a(35) = 131, a(51) = 211, a(54) = 227, a(56) = 239.  Jonathan Vos Post, Feb 10 2010
The Polymath project (see the TaoCrootHelfgott 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^2k to k^2 + (k1)} 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(xy), 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


REFERENCES

K. Chandrasekharan, Introduction to Analytic Number Theory. SpringerVerlag, 1968, Chap. VI.
K. Chandrasekharan, Arithmetical Functions. SpringerVerlag, 1970, Chapter VIII, pp. 194228. SpringerVerlag, Berlin.
P. G. L. Dirichlet, Werke, Vol. ii, pp. 4966.
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.
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).
Takenov Nurdin N. and Haritonova Oksana, 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."


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 [First 1000 terms from T. D. Noe]
D. Andrica and E. J. Ionascu, On the number of polynomials with coefficients in [n], An. St. Univ. Ovidius Constanta, 2013, to appear.
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333340. 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. 10251051.
Xiaoxi Duan and M. W. Wong, The Dirichlet divisor problem, traces and determinants for complex powers of the twisted biLaplacian, J. of Math. Analysis and Applications, Volume 410, Issue 1, Feb 01 2014, Pages 151157
L. Hoehn and J. Ridenhour, Summations involving computerrelated functions, Math. Mag., 62 (1989), 191196.
M. N. Huxley, Exponential Sums and Lattice Points III, Proc. London Math. Soc., 87 (2003), p. 591609.
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), 12331246; also at arXiv:1009.3956 [math.NT].


FORMULA

a(n) = n * ( log(n) + 2*gamma  1 ) + O(sqrt(n)), where gamma is the EulerMascheroni 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 socalled 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/(1x))*Sum_{k >= 1} x^k/(1x^k).  Benoit Cloitre, Apr 23 2003
For n > 0: A027750(a(n1) + k) = kdivisor of n, = k <= A000005(n).  Reinhard Zumkeller, May 10 2006
a(n) = A161886(n)  n + 1 = A161886(n1)  A049820(n) + 2 = A161886(n1) + 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(n1) + 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 BerkaneBordellèsRamaré 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)  (k1))).  Gregory R. Bryant, Apr 20 2013
From Mats Granvik, May 28 2017: (Start)
Sum_{k=1..n} A255315(n, k) = n.
a(n) = (n^2  (2*(Sum_{k=1..n} A255315(n, k)*(n  k + 1))  n)) + 2*n  round(1 + (1/2)*(3 + sqrt(n) + sqrt(1 + n))).
a(n) = ((n^2  (2*(Sum_{k=1..n} A255315(n, n  k + 1)*(n  k + 1))  n))  2*n + round(1 + (1/2)*(3 + sqrt(n) + sqrt(1 + n)))). (End)
Dirichlet g.f. for s > 2: Sum_{n=1..infinity} a(n)/n^s = Sum_{k=1..infinity}(Zeta(s1)Sum_{n=1..k1}(HurwitzZeta(s,n/k)*n/k^s))/k.  Mats Granvik, Sep 24 2017


EXAMPLE

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.


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


PROG

(PARI) a(n)=sum(k=1, n, n\k)
(PARI) a(n)=sum(k=1, sqrtint(n), n\k)*2sqrtint(n)^2 \\ Charles R Greathouse IV, Oct 10 2010
(Haskell)
a006218 n = sum $ map (div n) [1..n]
 Reinhard Zumkeller, Jan 29 2011


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, A161700, A004125, A212120.
Sequence in context: A051611 A258028 A005004 * A062839 A253081 A088940
Adjacent sequences: A006215 A006216 A006217 * A006219 A006220 A006221


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



