|
%I #73 Oct 23 2023 15:13:36
%S 1,4,7,13,16,25,28,38,44,53,56,74,77,86,95,110,113,131,134,152,161,
%T 170,173,203,209,218,228,246,249,276,279,300,309,318,327,363,366,375,
%U 384,414,417,444,447,465,483,492,495,540,546,564,573,591,594,624,633,663
%N Partial sums of A007425: (tau<=)_3(n).
%C (tau<=)_k(n) = |{(x_1,x_2,...,x_k): x_1*x_2*...*x_k<=n}|, i.e., tau<=_k(n) is number of solutions to x_1*x_2*...*x_k<=n, x_i > 0.
%C A061201(n) is the number of 4-tuples (w,x,y,z) having all terms in {1,...,n} and w=x*y*z; see A211795 for a list of related counting sequences. - _Clark Kimberling_, Apr 28 2012
%C The formula for Sum_{k=1..n} d3(k) in the Benoit Cloitre article on page 15 is incorrect. For correct asymptotic formula see below or generate it in the Mathematica: Residue[Zeta[s]^3 * n^s/s, {s, 1}] // Expand. - _Vaclav Kotesovec_, Aug 19 2021
%D M. N. Huxley, Area, Lattice Points and Exponential Sums, Oxford, 1996; p. 239.
%H Vaclav Kotesovec, <a href="/A061201/b061201.txt">Table of n, a(n) for n = 1..100000</a> (terms 1..1000 from Harry J. Smith)
%H Benoit Cloitre, <a href="/A013936/a013936.pdf">On the divisor and circle problems</a>
%H Vaclav Kotesovec, <a href="/A061201/a061201_1.jpg">Graph - The asymptotic ratio (1000000 terms)</a>
%F (tau<=)_k(n) = Sum_{i=1..n} tau_k(i).
%F a(n) = n * ( log(n)^2/2 + (3*g-1)*log(n) + 3*g^2-3*g-3*g1+1 ) + O(sqrt(n)), where g is the Euler-Mascheroni number ~ 0.57721... (see A001620), and g1 is the first Stieltjes constant ~ -0.072816 (see A082633). The determination of the precise size of the error term is an unsolved problem - see references. - _Andrew Lelechenko_, Apr 15 2011 [corrected by _Vaclav Kotesovec_, Sep 09 2018]
%F a(n) = Sum_{k=1..n} A000005(k)*floor(n/k). - _Benoit Cloitre_, Apr 19 2007
%F To compute a(n) for huge n (see A180365) in sublinear use a(n) = 3*Sum_{i=1..n3} A006218(n/i) - Sum_{j=1..n3} floor(n/(i*j)) + n3^3, where n3 = floor(n^(1/3)). - _Andrew Lelechenko_, Apr 15 2011
%F a(n) = Sum_{k=1..n} Sum_{i=1..n} floor(n/(i*k)). - _Wesley Ivan Hurt_, Sep 14 2017
%F G.f.: (1/(1-x)) * Sum_{k>=1} A000005(k) * x^k/(1 - x^k). - _Seiichi Manyama_, Jul 24 2022
%p b:= proc(k, n) option remember; uses numtheory;
%p `if`(k=1, 1, add(b(k-1, d), d=divisors(n)))
%p end:
%p a:= proc(n) option remember; `if`(n=0, 0, b(3, n)+a(n-1)) end:
%p seq(a(n), n=1..76); # _Alois P. Heinz_, Oct 23 2023
%t a[n_] := Sum[ DivisorSigma[0, k]*Floor[n/k], {k, 1, n}]; Table[a[n], {n, 1, 56}] (* _Jean-François Alcover_, Sep 20 2011, after _Benoit Cloitre_ *)
%t (* Asymptotics: *) n*(Log[n]^2/2 + (3*EulerGamma - 1)*Log[n] + 3*EulerGamma^2 - 3*EulerGamma - 3*StieltjesGamma[1] + 1) (* _Vaclav Kotesovec_, Sep 09 2018 *)
%t Accumulate[a[n_]:=DivisorSum[n, DivisorSigma[0, #]&]; Array[a, 60]] (* _Vincenzo Librandi_, Jan 12 2020 *)
%o (PARI) a(n)=sum(k=1,n,numdiv(k)*floor(n/k)) \\ _Benoit Cloitre_, Apr 19 2007
%o (PARI) { for (n=1, 1000, write("b061201.txt", n, " ", sum(k=1, n, numdiv(k)*(n\k))) ) } \\ _Harry J. Smith_, Jul 18 2009
%o (PARI) my(N=60, x='x+O('x^N)); Vec(sum(k=1, N, numdiv(k)*x^k/(1-x^k))/(1-x)) \\ _Seiichi Manyama_, Jul 24 2022
%o (Magma) [&+[NumberOfDivisors(k)*Floor(n/k): k in [1..n]]: n in [1..56]]; // _Bruno Berselli_, Apr 13 2011
%o (Python)
%o from math import isqrt
%o from sympy import integer_nthroot
%o def A061201(n): return (m:=integer_nthroot(n,3)[0])**3+3*sum(-(s:=isqrt(r:=n//i))**2+(sum(r//k for k in range(1,s+1))<<1)-sum(n//(i*j) for j in range(1,m+1)) for i in range(1,m+1)) # _Chai Wah Wu_, Oct 23 2023
%Y Cf. tau_2(n): A000005, tau_3(n): A007425, tau_4(n): A007426, tau_5(n): A061200, tau_6(n): A034695, (unordered) 2-factorizations of n: A038548, (unordered) 3-factorizations of n: A034836, A001055, (tau<=)_2(n): A006218, (tau<=)_4(n): A061202, (tau<=)_5(n): A061203, (tau<=)_6(n): A061204.
%K easy,nonn
%O 1,2
%A _Vladeta Jovovic_, Apr 21 2001
|
