OFFSET
0,2
COMMENTS
It is known that a(n) can be calculated in O(n^(2/3)) using the same algorithm as for A347221. It might be possible to improve to O(n^(1/3)) but the mathematics would require a lot of work.
Unlike A347221, in this case there are many more alternative formulas, but not all are effective in reducing the complexity; some might be very difficult to use to improve it.
a(n) ~ 1.5*n^2. Tested with 10^7 numbers n <= 10^9 using a power regression algorithm.
FORMULA
a(n) = Sum_{a=0..n} Sum_{b=0..n-a} Sum_{c=0..n-a-b} [a*b*c<=n], where [] is the Iverson bracket.
a(n) = A347221(n,n).
EXAMPLE
a(1) = 4: (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0).
PROG
(C) int T(int n) { int cnt = 0; for (int a = 0; a <= n; ++a) for (int b = 0; b <= n - a; ++b) for (int c = 0; c <= n - a - b; ++c) if (a * b * c <= n) ++cnt; return cnt; }
(PARI) a(n) = sum(a=0, n, sum(b=0, n-a, sum(c=0, n-a-b, a*b*c <= n))); \\ Michel Marcus, Aug 25 2021
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vo Hoang Anh, Aug 24 2021
STATUS
approved