A347275 a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).

1, 3, 6, 10, 15, 19, 25, 29, 35, 40, 46, 50, 58, 62, 68, 74, 81, 85, 93, 97, 105, 111, 117, 121, 131, 136, 142, 148, 156, 160, 170, 174, 182, 188, 194, 200, 211, 215, 221, 227, 237, 241, 251, 255, 263, 271, 277, 281, 293, 298, 306, 312, 320, 324, 334, 340, 350, 356

Offset: 0

Author

Vo Hoang Anh, Aug 25 2021

Keywords

• nonn
• easy

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

Examples

			a(1) = 3: (0, 0), (0, 1), (1, 0).
		

Links

• Richard Sladkey, A Successive Approximation Algorithm for Computing the Divisor Summatory Function, arXiv:1206.3369 [math.NT], 2012.

Crossrefs

Cf. A006218, A049820, A091626.

Programs

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; }

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 *)

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

Formula

a(n) = Sum_{a=0..n} Sum_{b=0..n-a} [a*b<=n], where [] is the Iverson bracket.