|
|
A347252
|
|
Number of nonnegative triples (a, b, c) satisfying (a + b + c <= n) and (a * b * c <= n).
|
|
1
|
|
|
1, 4, 10, 20, 35, 56, 83, 107, 141, 174, 213, 249, 303, 345, 396, 450, 513, 567, 639, 699, 777, 849, 924, 996, 1098, 1179, 1266, 1357, 1459, 1549, 1666, 1762, 1879, 1987, 2098, 2212, 2356, 2470, 2593, 2719, 2869, 2995, 3148, 3280, 3430, 3583, 3730, 3874, 4063
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
LINKS
|
|
|
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.
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|