A347252 Number of nonnegative triples (a, b, c) satisfying (a + b + c <= n) and (a * b * c <= n).

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

Offset: 0

Author

Vo Hoang Anh, Aug 24 2021

Keywords

• nonn
• easy

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.

Examples

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

Crossrefs

Cf. A347221.

Programs

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

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