Vo Hoang Anh - cp's OEIS frontend

User: Vo Hoang Anh

Vo Hoang Anh has authored 3 sequences.

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 abc <= t.

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, 64, 1, 4, 10, 20, 35, 50, 65, 85, 1, 4, 10, 20, 35, 53, 68, 86, 109, 1, 4, 10, 20, 35, 56, 71, 89, 110, 136, 1, 4, 10, 20, 35, 56, 77, 92, 113, 137, 166

Offset: 0

Vo Hoang Anh, Aug 24 2021

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

			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).
T(0,1) = 1: (0,0,0).
Array T(s,t) begins:
    1,   1,   1,   1,   1,   1,   1,   1,   1, ...
    4,   4,   4,   4,   4,   4,   4,   4,   4, ...
   10,  10,  10,  10,  10,  10,  10,  10,  10, ...
   19,  20,  20,  20,  20,  20,  20,  20,  20, ...
   31,  32,  35,  35,  35,  35,  35,  35,  35, ...
   46,  47,  50,  53,  56,  56,  56,  56,  56, ...
   64,  65,  68,  71,  77,  77,  83,  83,  84, ...
   85,  86,  89,  92,  98, 101, 107, 107, 114, ...
  109, 110, 113, 116, 122, 125, 134, 134, 141, ...

Vo Hoang Anh, O(t^(5/9)) C++ Code
Vo Hoang Anh, Power Regression C++ Code
Codeforces, Algorithm discussion
MathStackExchange, Math discussion
D. H. J. Polymath, Deterministic methods to find primes, arXiv:1009.3956 [math.NT], 2012.
Richard Sladkey, A Successive Approximation Algorithm for Computing the Divisor Summatory Function, arXiv:1206.3369 [math.NT], 2012.

Cf. A000005, A000012, A000217, A000292, A000578, A006501, A061201, A124011, A139482,

Cf. A005448 (column 0), A347252 (main diagonal).

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; }

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

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

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.
T(n, n) = A347252(n).
T(0, t) = A000012(t).
T(s, 0) = A005448(s).
T(s, A006501(s) + x) = A000292(s + 1), for all x >= 0.
This leads to: T(s, A000578(s) + x) = A000292(s + 1), for all x >= 0.
T(s, t) = (3s^2 + 3s) / 2 + A061201(t) + 1, for s > t + 1 > 1.
T(s, 1) = (3s^2 + 3s) / 2 + 2 = A139482(s + 2), for s > t + 1 > 1.
T(s, 2) = (3s^2 + 3s) / 2 + 5 = A124011(s), for s > t + 1 > 2.
T(s, t) = T(s + k, t) - 3*k*s - 3*A000217(k), for s > t + 1 > 5.
T(t + 2 - k, t) = T(t + 2, t) - 3*k*s - 6k + 3*A000217(k), for 0 <= 2k <= (t-1), for t > 4.
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.

A347275 a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).

Original entry on oeis.org

1, 3, 6, 10, 15, 19, 25, 29, 35, 40, 46, 50, 58, 62, 68, 74, 81, 85, 93, 97, 105, 111, 117, 121, 131, 136, 142, 148, 156, 160, 170, 174, 182, 188, 194, 200, 211, 215, 221, 227, 237, 241, 251, 255, 263, 271, 277, 281, 293, 298, 306, 312, 320, 324, 334, 340, 350, 356

Offset: 0

Vo Hoang Anh, Aug 25 2021

Except for a(0) and a(1), a(n) = A006218(n + 1) - A049820(n + 1) + 2n - 1. Tested with first 10^9 numbers.
Since there are only O(sqrt(n)) different integers in the set S = {floor(n / 1), floor(n / 2), ..., floor(n / n)}, we can calculate a(n) in O(sqrt(n)).
There are many methods based on different kinds of formulas that are also known to work in O(n^(1/3)), but not all are effective. Some of them have lower complexity, but their use of too much division and multiplication makes them slower than expected; 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.
a(n) is approximately epsilon*n^(1+delta) as delta approaches 0 and epsilon approaches +oo for n approaching +oo. The tighter relationship between epsilon and delta is unknown. Tested with 10^7 numbers n <= 10^15 using power regression algorithm.
For n > 1, a(n) = A006218(n)+2n-1. - Chai Wah Wu, Oct 07 2021

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

Richard Sladkey, A Successive Approximation Algorithm for Computing the Divisor Summatory Function, arXiv:1206.3369 [math.NT], 2012.

Cf. A006218, A049820, A091626.

int T(int n) { int cnt = 0; for (int a = 0; a <= n; ++a) for (int b = 0; b <= n - a; ++b) if (a * b <= n) ++cnt; return cnt; }

A347275 := proc(n)
    local a,i,j ;
    a := 0 ;
    for i from 0 to n do
    for j from 0 to n-i do
        if i*j <= n then
            a := a+1 ;
        end if;
    end do:
    end do:
    a ;
end proc:
seq(A347275(n),n=0..40) ; # R. J. Mathar, Sep 15 2021

a[n_] := Sum[Boole[i*j <= n], {i, 0, n}, {j, 0, n-i}];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Nov 08 2023 *)

from math import isqrt
def A347275(n): return 2*n+1 if n <= 1 else 2*(n+sum(n//k for k in range(1, isqrt(n)+1)))-isqrt(n)**2-1 # Chai Wah Wu, Oct 07 2021

a(n) = Sum_{a=0..n} Sum_{b=0..n-a} [a*b<=n], where [] is the Iverson bracket.

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

Original entry on oeis.org

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

Vo Hoang Anh, Aug 24 2021

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.

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

Cf. A347221.

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; }

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

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

cp's OEIS Frontend

User: Vo Hoang Anh

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 abc <= t.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

PARI

Formula

A347275 a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

C

PARI

Formula

cp's OEIS Frontend

User: Vo Hoang Anh

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

PARI

Formula

A347275 a(n) is the number of nonnegative ordered pairs (a,b) satisfying (a+b <= n) and (a*b <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

C

PARI

Formula

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 abc <= t.