This site is supported by donations to The OEIS Foundation.

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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; 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 [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 REFERENCES 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. 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), 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. 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), p. 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]. 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 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(s-1)-Sum_{n=1..k-1}(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)*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, 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 STATUS approved

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

Last modified September 22 20:30 EDT 2018. Contains 315270 sequences. (Running on oeis4.)