|
| |
|
|
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)
|
|
128
|
|
|
|
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. [From 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. [From 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. [From 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
|
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.5. [From N. J. A. Sloane, Mar 12 2009]
K. Chandrasekharan, Introduction to Analytic Number Theory, Sringer-Verlag, 1968, Chap. VI.
K. Chandrasekharan, (1970): Arithmetical Functions; Chapter VIII, pp. 194-228. Springer-Verlag, Berlin.
P. G. L. Dirichlet, Werke, Vol. ii, pp. 49-66.
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, N. N. and Haritonova, O., 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) [From 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. [From 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. [From 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
|
|
|
MAPLE
|
with(numtheory): A006218 := n->add(sigma[0](i), i=1..n);
|
|
|
MATHEMATICA
|
Table[Sum[DivisorSigma[0, k], {k, 1, n}], {n, 1, 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 [From 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
|
| |
|
|
