OFFSET
0,2
COMMENTS
Except for a(0) and a(1), a(n) = A006218(n + 1) - A049820(n + 1) + 2n - 1. Tested with first 10^9 numbers.
Since there are only O(sqrt(n)) different integers in the set S = {floor(n / 1), floor(n / 2), ..., floor(n / n)}, we can calculate a(n) in O(sqrt(n)).
There are many methods based on different kinds of formulas that are also known to work in O(n^(1/3)), but not all are effective. Some of them have lower complexity, but their use of too much division and multiplication makes them slower than expected; some of them use precalculation and caching to speed things up but are not as effective as the division-free algorithm that Richard Sladkey described.
a(n) is approximately epsilon*n^(1+delta) as delta approaches 0 and epsilon approaches +oo for n approaching +oo. The tighter relationship between epsilon and delta is unknown. Tested with 10^7 numbers n <= 10^15 using power regression algorithm.
For n > 1, a(n) = A006218(n)+2n-1. - Chai Wah Wu, Oct 07 2021
LINKS
Richard Sladkey, A Successive Approximation Algorithm for Computing the Divisor Summatory Function, arXiv:1206.3369 [math.NT], 2012.
FORMULA
a(n) = Sum_{a=0..n} Sum_{b=0..n-a} [a*b<=n], where [] is the Iverson bracket.
EXAMPLE
a(1) = 3: (0, 0), (0, 1), (1, 0).
MAPLE
A347275 := proc(n)
local a, i, j ;
a := 0 ;
for i from 0 to n do
for j from 0 to n-i do
if i*j <= n then
a := a+1 ;
end if;
end do:
end do:
a ;
end proc:
seq(A347275(n), n=0..40) ; # R. J. Mathar, Sep 15 2021
MATHEMATICA
a[n_] := Sum[Boole[i*j <= n], {i, 0, n}, {j, 0, n-i}];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Nov 08 2023 *)
PROG
(C) int T(int n) { int cnt = 0; for (int a = 0; a <= n; ++a) for (int b = 0; b <= n - a; ++b) if (a * b <= n) ++cnt; return cnt; }
(Python)
from math import isqrt
def A347275(n): return 2*n+1 if n <= 1 else 2*(n+sum(n//k for k in range(1, isqrt(n)+1)))-isqrt(n)**2-1 # Chai Wah Wu, Oct 07 2021
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vo Hoang Anh, Aug 25 2021
STATUS
approved