This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A347221 #116 Feb 20 2022 20:26:08
%S A347221 1,1,4,1,4,10,1,4,10,19,1,4,10,20,31,1,4,10,20,32,46,1,4,10,20,35,47,
%T A347221 64,1,4,10,20,35,50,65,85,1,4,10,20,35,53,68,86,109,1,4,10,20,35,56,
%U A347221 71,89,110,136,1,4,10,20,35,56,77,92,113,137,166
%N A347221 Square array T(s,t), s >= 0, t >= 0, read by downward antidiagonals: T(s,t) is the number of nonnegative ordered triples (a,b,c) satisfying a+b+c <= s and a*b*c <= t.
%C A347221 Based on the fact that there are only O(sqrt(t)) distinct integers in the set S = {floor(t/1), floor(t/2), ..., floor(t/t)} and using combinatorics by fixing the number (a) as minimum, we can easily calculate this function in O(sigma(a=1->t^(1/3)) (log_2(floor(t/a)) + floor(t/a)^(1/2))).
%C A347221 The complexity can be reduced to O(sigma(a=1->t^(1/3)) (log_2(floor(t/a)) + floor(t/a)^(1/3))) = O(t^(5/9)).
%C A347221 There are many methods that take O(t^(5/9)) steps, but not all are effective; some of them have lower complexity but use too many division and multiplication steps. Some of them use precalculation and caching to speed things up, but are not as effective as the division-free algorithm that Richard Sladkey described.
%C A347221 It is known that for each (a), we only need a For loop of at most K = min((s-a)/2,sqrt(t/a)) iterations. If we can somehow calculate this in O(K^(1/2)) or even O(K^(1/3)) for each (a) then it is possible to calculate in O(t^(1/3)).
%C A347221 We can also calculate T(s, t) in O(t^(1/3)) if this function can be calculated fast enough: g(l, r, a, t) = Sum_{p = l..r} floor(t/(a*p)) for all a such that 1 <= a <= t^(1/3).
%C A347221 When s is small, we can try not fixing a as minimum and get O(s * t^(1/3)) complexity. You can also make the complexity not depend on O(f(t)) and get O(s^2) complexity and this can be further improved.
%C A347221 When s = t, the values on the main diagonal, T(s, s), are approximately 1.5*s^2 (tested with 10^7 numbers s <= 10^9 using a power regression algorithm).
%C A347221 The current best known algorithm O(t^(5/9)) (with modulo for large result) can run for s <= 10^18 and t <= 10^12 under 1 second and constant memory (820ms on GNU C++17 7.3.0 codeforces and 310ms on C++14 ideone).
%C A347221 As far as I know, the best complexity in theory is O(t^(2/3-c+o(1))) for small c > 0. Computing this table faster is as hard as the prime counting function and/or the divisor summatory function.
%H A347221 Vo Hoang Anh, <a href="https://ideone.com/yMi8tu">O(t^(5/9)) C++ Code</a>
%H A347221 Vo Hoang Anh, <a href="https://ideone.com/mmoWxJ">Power Regression C++ Code</a>
%H A347221 Codeforces, <a href="https://codeforces.com/blog/entry/93981">Algorithm discussion</a>
%H A347221 MathStackExchange, <a href="https://math.stackexchange.com/questions/4230187/faster-algorithm-for-counting-non-negative-tripplea-b-c-satisfied-a-b-c">Math discussion</a>
%H A347221 D. H. J. Polymath, <a href="https://arxiv.org/abs/1009.3956">Deterministic methods to find primes</a>, arXiv:1009.3956 [math.NT], 2012.
%H A347221 Richard Sladkey, <a href="https://arxiv.org/abs/1206.3369">A Successive Approximation Algorithm for Computing the Divisor Summatory Function</a>, arXiv:1206.3369 [math.NT], 2012.
%F A347221 T(s,t) = Sum_{a=0..s} Sum_{b=0..s-a} Sum_{c=0..s-a-b} [a*b*c<=t], where [] is the Iverson bracket.
%F A347221 T(n, n) = A347252(n).
%F A347221 T(0, t) = A000012(t).
%F A347221 T(s, 0) = A005448(s).
%F A347221 T(s, A006501(s) + x) = A000292(s + 1), for all x >= 0.
%F A347221 This leads to: T(s, A000578(s) + x) = A000292(s + 1), for all x >= 0.
%F A347221 T(s, t) = (3s^2 + 3s) / 2 + A061201(t) + 1, for s > t + 1 > 1.
%F A347221 T(s, 1) = (3s^2 + 3s) / 2 + 2 = A139482(s + 2), for s > t + 1 > 1.
%F A347221 T(s, 2) = (3s^2 + 3s) / 2 + 5 = A124011(s), for s > t + 1 > 2.
%F A347221 T(s, t) = T(s + k, t) - 3*k*s - 3*A000217(k), for s > t + 1 > 5.
%F A347221 T(t + 2 - k, t) = T(t + 2, t) - 3*k*s - 6k + 3*A000217(k), for 0 <= 2k <= (t-1), for t > 4.
%F A347221 When n > 4, T(n, n) = T(n + 2, n) - 6n - 15 = A347252(n) = Sum_{k=1..n} floor(n/k)*A000005(k) + (3n^2 + 3n - 10) / 2 = A061201(n) + (3n^2 + 3n - 10) / 2 = (1/2)n(6g^2 + (6g-2)log(n) - 6g - 6g1 + log^2(n) + 2) + (3n^2)/2 + (3n)/2 - 5 + O(sqrt(n)) where g is the Euler-Mascheroni number and g1 is the first Stieltjes constant.
%e A347221 T(2,0) = 10: (0,0,0), (0,0,1), (0,0,2), (0,1,0), (0,1,1), (0,1,2), (0,2,0), (1,0,0), (1,0,1), (2,0,0).
%e A347221 T(0,1) = 1: (0,0,0).
%e A347221 Array T(s,t) begins:
%e A347221 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e A347221 4, 4, 4, 4, 4, 4, 4, 4, 4, ...
%e A347221 10, 10, 10, 10, 10, 10, 10, 10, 10, ...
%e A347221 19, 20, 20, 20, 20, 20, 20, 20, 20, ...
%e A347221 31, 32, 35, 35, 35, 35, 35, 35, 35, ...
%e A347221 46, 47, 50, 53, 56, 56, 56, 56, 56, ...
%e A347221 64, 65, 68, 71, 77, 77, 83, 83, 84, ...
%e A347221 85, 86, 89, 92, 98, 101, 107, 107, 114, ...
%e A347221 109, 110, 113, 116, 122, 125, 134, 134, 141, ...
%t A347221 Table[Function[s, Sum[Boole[a b c <= t], {a, 0, s}, {b, 0, s - a}, {c, 0, s - a - b}]][n - t], {n, 0, 10}, {t, n, 0, -1}] // Flatten (* _Michael De Vlieger_, Aug 25 2021 *)
%o A347221 (C) int T(int s, int t) { int cnt = 0; for (int a = 0; a <= s; ++a) for (int b = 0; b <= s - a; ++b) for (int c = 0; c <= s - a - b; ++c) if (a * b * c <= t) ++cnt; return cnt; }
%o A347221 (PARI) T(s, t) = sum(a=0, s, sum(b=0, s-a, sum(c=0, s-a-b, a*b*c <= t))); \\ _Michel Marcus_, Aug 25 2021
%Y A347221 Cf. A000005, A000012, A000217, A000292, A000578, A006501, A061201, A124011, A139482,
%Y A347221 Cf. A005448 (column 0), A347252 (main diagonal).
%K A347221 nonn,easy,tabl
%O A347221 0,3
%A A347221 _Vo Hoang Anh_, Aug 24 2021