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

%I #32 Feb 20 2022 20:26:01

%S 1,4,10,20,35,56,83,107,141,174,213,249,303,345,396,450,513,567,639,

%T 699,777,849,924,996,1098,1179,1266,1357,1459,1549,1666,1762,1879,

%U 1987,2098,2212,2356,2470,2593,2719,2869,2995,3148,3280,3430,3583,3730,3874,4063

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

%C 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.

%C 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.

%C a(n) ~ 1.5*n^2. Tested with 10^7 numbers n <= 10^9 using a power regression algorithm.

%F 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.

%F a(n) = A347221(n,n).

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

%o (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; }

%o (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

%Y Cf. A347221.

%K nonn,easy

%O 0,2

%A _Vo Hoang Anh_, Aug 24 2021