login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006218 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)
132
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; 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 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 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

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

REFERENCES

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), 333-340. See Eq. 1.5.

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.

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, 1 February 2014, Pages 151-157

L. Hoehn and J. Ridenhour, Summations involving computer-related functions, Math. Mag., 62 (1989), 191-196.

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.

M. N. Huxley, Exponential Sums and Lattice Points III, P. L. M. S., 87 (2003), p. 591-609.

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

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

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)*2-sqrtint(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: A027922 A051611 A005004 * A062839 A088940 A088937

Adjacent sequences:  A006215 A006216 A006217 * A006219 A006220 A006221

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 23 19:18 EDT 2014. Contains 240946 sequences.