login
A347275
a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).
1
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,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
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