

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)


141



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


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

T. D. Noe, Table of n, a(n) for n = 0..1000
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, 1 February 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.
Richard Sladkey, A successive approximation algorithm for computing the divisor summatory function, 2012, arXiv:1206.3369
Terence Tao, Ernest Croot III, and Harald Helfgott, Deterministic methods to find primes, Mathematics of Computation. arXiv:1009.3956


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


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


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 and A143724.
A061017 is an inverse.
It appears that the partial sums give A078567.  N. J. A. Sloane, Nov 24 2008
Cf. A116477, A051731, A143724, 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



