|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
LINKS
|
|
|
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
|
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:
|
|
MATHEMATICA
|
a[n_] := Sum[Boole[i*j <= n], {i, 0, n}, {j, 0, n-i}];
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|