|
%I M2432 #274 Nov 30 2023 10:47:02
%S 0,1,3,5,8,10,14,16,20,23,27,29,35,37,41,45,50,52,58,60,66,70,74,76,
%T 84,87,91,95,101,103,111,113,119,123,127,131,140,142,146,150,158,160,
%U 168,170,176,182,186,188,198,201,207,211,217,219,227,231,239,243,247,249
%N 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.
%C The identity Sum_{k=1..n} floor(n/k) = Sum_{k=1..n} d(k) is Equation (10), p. 58, of Apostol (1976). - _N. J. A. Sloane_, Dec 06 2020
%C The "Dirichlet divisor problem" is to find a precise asymptotic estimate for this sequence - see formula lines below, also Apostol (1976), Chap. 3.
%C 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).
%C Binomial transform of A001659.
%C 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
%C Equals inverse Mobius transform of A116477. - _Gary W. Adamson_, Aug 07 2008
%C 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]
%C 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
%C The inverse Mobius transforms yields A143356. - _R. J. Mathar_, Oct 17 2012
%C 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
%C 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
%C 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
%C a(n) is also the total number of partitions of all positive integers <= n into equal parts. - _Omar E. Pol_, May 29 2017
%C 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
%C a(n) always has the same parity as floor(sqrt(n)) = A000196(n): see A211264 (proof in Diophante link). - _Bernard Schott_, Feb 13 2021
%C From _Omar E. Pol_, Feb 16 2021: (Start)
%C Apart from initial zero this is the convolution of A341062 and A000027.
%C Nonzero terms convolved with A341062 gives A055507. (End)
%C From _Bernard Schott_, Apr 17 2022: (Start)
%C a(n-1) is the number of lattice points in the first quadrant lying under the hyperbola x*y = n, excluding the lattice points on the axes.
%C a(n) is the number of lattice points in the first quadrant lying on or under the hyperbola x*y = n, excluding the lattice points on the axes. (Reference Hari Kishan). (End)
%D T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
%D K. Chandrasekharan, Introduction to Analytic Number Theory. Springer-Verlag, 1968, Chap. VI.
%D K. Chandrasekharan, Arithmetical Functions. Springer-Verlag, 1970, Chapter VIII, pp. 194-228. Springer-Verlag, Berlin.
%D P. G. L. Dirichlet, Werke, Vol. ii, pp. 49-66.
%D M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972, p. 7.
%D M. N. Huxley, Area, Lattice Points and Exponential Sums, Oxford, 1996; p. 239.
%D Hari Kishan, Number Theory, Krishna, Educational Publishers, 2014, Theorem 1, p. 133.
%D H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 56.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D 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."
%H N. J. A. Sloane, <a href="/A006218/b006218.txt">Table of n, a(n) for n = 0..20000</a> (first 1000 terms from T. D. Noe)
%H Dorin Andrica and Ovidiu Bagdasar, <a href="http://hdl.handle.net/10545/623501">On some results concerning the polygonal polynomials</a>, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
%H D. Andrica and E. J. Ionascu, <a href="http://www.anstuocmath.ro/mathematics/vol22-1/Andrica_D__Ionascu_E.J._nou-1__final_.pdf">On the number of polynomials with coefficients in [n]</a>, An. St. Univ. Ovidius Constanta, Vol. 22(1),2014, 13-23.
%H R. Bellman and H. N. Shapiro, <a href="http://www.jstor.org/stable/1969281">On a problem in additive number theory</a>, Annals Math., 49 (1948), 333-340. See Eq. 1.5.
%H D. Berkane, O. Bordellès, and O. Ramaré, <a href="http://dx.doi.org/10.1090/S0025-5718-2011-02535-4">Explicit upper bounds for the remainder term in the divisor problem</a>, Math. Comp. 81:278 (2012), pp. 1025-1051.
%H Peter J. Cameron and Hamid Reza Dorbidi, <a href="https://arxiv.org/abs/2311.15652">Minimal cover groups</a>, arXiv:2311.15652 [math.GR], 2023. See p. 13.
%H Diophante, <a href="http://www.diophante.fr/problemes-par-themes/arithmetique-et-algebre/a1-pot-pourri/4498-a1712-la-meme-parite">A1712, La même parité</a> (in French).
%H Xiaoxi Duan and M. W. Wong, <a href="http://dx.doi.org/10.1016/j.jmaa.2013.08.017">The Dirichlet divisor problem, traces and determinants for complex powers of the twisted bi-Laplacian</a>, J. of Math. Analysis and Applications, Volume 410, Issue 1, Feb 01 2014, Pages 151-157
%H L. Hoehn and J. Ridenhour, <a href="http://www.jstor.org/stable/2689932">Summations involving computer-related functions</a>, Math. Mag., 62 (1989), 191-196.
%H M. N. Huxley, <a href="http://dx.doi.org/10.1112/S0024611503014485">Exponential Sums and Lattice Points III</a>, Proc. London Math. Soc., 87 (2003), pp. 591-609.
%H Vaclav Kotesovec, <a href="/A006218/a006218_1.jpg">Graph - The asymptotic ratio (1000000 terms)</a>
%H Richard Sladkey, <a href="http://arxiv.org/abs/1206.3369">A successive approximation algorithm for computing the divisor summatory function</a>, arXiv:1206.3369 [math.NT], 2012.
%H Terence Tao, Ernest Croot III, and Harald Helfgott, <a href="http://dx.doi.org/10.1090/S0025-5718-2011-02542-1">Deterministic methods to find primes</a>, Math. Comp. 81 (2012), 1233-1246; also at <a href="http://arxiv.org/abs/1009.3956">arXiv:1009.3956 [math.NT]</a>, 2010-2012.
%F 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).
%F 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
%F a(n) = 2*(Sum_{i=1..floor(sqrt(n))} floor(n/i)) - floor(sqrt(n))^2. - _Benoit Cloitre_, May 12 2002
%F G.f.: (1/(1-x))*Sum_{k >= 1} x^k/(1-x^k). - _Benoit Cloitre_, Apr 23 2003
%F For n > 0: A027750(a(n-1) + k) = k-divisor of n, = k <= A000005(n). - _Reinhard Zumkeller_, May 10 2006
%F 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
%F 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
%F 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
%F a(n) = Sum_{k = 1..floor(sqrt(n))} A005408(floor((n/k) - (k-1))). - _Gregory R. Bryant_, Apr 20 2013
%F Dirichlet g.f. for s > 2: Sum_{n>=1} a(n)/n^s = Sum_{k>=1} (Zeta(s-1) - Sum_{n=1..k-1} (HurwitzZeta(s,n/k)*n/k^s))/k. - _Mats Granvik_, Sep 24 2017
%F From _Ridouane Oudra_, Dec 31 2022: (Start)
%F a(n) = n^2 - Sum_{i=1..n} Sum_{j=1..n} floor(log(i*j)/log(n+1));
%F a(n) = floor(sqrt(n)) + 2*Sum_{i=1..n} floor((sqrt(i^2 + 4*n) - i)/2);
%F a(n) = n + Sum_{i=1..n} v_2(i)*round(n/i), where v_2(i) = A007814(i). (End)
%e a(3) = 5 because 3 + floor(3/2) + 1 = 3 + 1 + 1 = 5. Or tau(1) + tau(2) + tau(3) = 1 + 2 + 2 = 5.
%e a(4) = 8 because 4 + floor(4/2) + floor(4/3) + 1 = 4 + 2 + 1 + 1 = 8. Or
%e tau(1) + tau(2) + tau(3) + tau(4) = 1 + 2 + 2 + 3 = 8.
%e 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.
%p with(numtheory): A006218 := n->add(sigma[0](i), i=1..n);
%t Table[Sum[DivisorSigma[0, k], {k, n}], {n, 70}]
%t FoldList[Plus, 0, Table[DivisorSigma[0, x], {x, 61}]] //Rest (* much faster *)
%t Join[{0},Accumulate[DivisorSigma[0,Range[60]]]] (* _Harvey P. Dale_, Jan 06 2016 *)
%o (PARI) a(n)=sum(k=1,n,n\k)
%o (PARI) a(n)=sum(k=1,sqrtint(n),n\k)*2-sqrtint(n)^2 \\ _Charles R Greathouse IV_, Oct 10 2010
%o (Haskell)
%o a006218 n = sum $ map (div n) [1..n]
%o -- _Reinhard Zumkeller_, Jan 29 2011
%o (Magma) [0] cat [&+[Floor(n/k):k in [1..n]]:n in [1..60]]; // _Marius A. Burtea_, Aug 25 2019
%o (Python)
%o from sympy import integer_nthroot
%o def A006218(n): return 2*sum(n//k for k in range(1,integer_nthroot(n,2)[0]+1))-integer_nthroot(n,2)[0]**2 # _Chai Wah Wu_, Mar 29 2021
%Y Right edge of A056535. Cf. A000005, A001659, A052511, A143236.
%Y Row sums of triangle A003988, A010766 and A143724.
%Y A061017 is an inverse.
%Y It appears that the partial sums give A078567. - _N. J. A. Sloane_, Nov 24 2008
%Y Cf. A116477, A051731, A055507, A161700, A004125, A212120, A341062.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
|
