cp's OEIS Frontend

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

%I A347252 #32 Feb 20 2022 20:26:01
%S A347252 1,4,10,20,35,56,83,107,141,174,213,249,303,345,396,450,513,567,639,
%T A347252 699,777,849,924,996,1098,1179,1266,1357,1459,1549,1666,1762,1879,
%U A347252 1987,2098,2212,2356,2470,2593,2719,2869,2995,3148,3280,3430,3583,3730,3874,4063
%N A347252 Number of nonnegative triples (a, b, c) satisfying (a + b + c <= n) and (a * b * c <= n).
%C A347252 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 A347252 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 A347252 a(n) ~ 1.5*n^2. Tested with 10^7 numbers n <= 10^9 using a power regression algorithm.
%F A347252 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 A347252 a(n) = A347221(n,n).
%e A347252 a(1) = 4: (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0).
%o A347252 (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 A347252 (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 A347252 Cf. A347221.
%K A347252 nonn,easy
%O A347252 0,2
%A A347252 _Vo Hoang Anh_, Aug 24 2021