A378126 Array read by antidiagonals: T(n, m) is the maximal size of partitions of (n, m) into sums of distinct pairs of nonnegative integers, excluding (0, 0).

0, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 4, 4, 4, 3, 3, 3, 4, 4, 4, 4, 4, 4, 3, 3, 4, 4, 4, 5, 4, 4, 4, 3, 3, 4, 5, 5, 5, 5, 5, 5, 4, 3, 4, 4, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 5, 5, 5, 4, 4, 5, 5, 6, 6, 6, 6

Offset

0,5

Comments

A378379(n) is the least number x such that T(x, x) >= n, and as the growth rate of A378379(n) is Theta(n^(3/2)), the growth rate of T(n, m) is O((n+m)^(2/3)).

Links

Jimin Park, Table of n, a(n) for n = 0..1000

Formula

T(n, m) = T(m, n).

T(n, m) >= T(n, 0) + T(0, m).

T(n, m) = A086435(p^n * q^m) for any distinct primes p and q.

T(n, 0) = A003056(n).

T(n, 1) = T(n, 0) + 1.

T(n, 2) = T(n-1, 0) + 2, for n >= 1.

T(n, m) = O((n+m)^(2/3)).

Example

Table begins:
  0 1 1 2 2 2 3 3 3 3 ...
  1 2 2 3 3 3 4 4 4 4 ...
  1 2 3 3 4 4 4 5 5 5 ...
  2 3 3 4 4 4 5 5 5 6 ...
  2 3 4 4 5 5 5 6 6 6 ...
  2 3 4 4 5 5 6 6 6 7 ...
  3 4 4 5 5 6 6 6 7 7 ...
  3 4 5 5 6 6 6 7 7 7 ...
  3 4 5 5 6 6 7 7 7 8 ...
  3 4 5 6 6 7 7 7 8 8 ...
  ...
T(9, 5) = 7, as (9, 5) can be expressed as the sum (0, 1) + (0, 2) + (1, 0) + (1, 1) + (2, 0) + (2, 1) + (3, 0), which is the longest for (9, 5).

Prog

(Python)
import functools
@functools.cache
def A378126(n: int, m: int, t: tuple[int, int] = (0, 0)) -> int:
  if (n, m) <= t: return 0
  v = 1
  for nn in range(t[0], n//2+1):
    for nm in range(m+1):
      if (nn, nm) <= t: continue
      rn, rm = n-nn, m-nm
      if (rn, rm) <= (nn, nm): continue
      nv = 1 + A378126(rn, rm, (nn, nm))
      if nv > v: v = nv
  return v

Crossrefs

Maximal size among partitions considered by A054242 and A201377.

The first row is T(n, 0) = A003056(n).

Cf. A086435, A378379.

Sequence in context: A230198 A024939 A024937 * A350823 A143977 A115265

Adjacent sequences: A378123 A378124 A378125 * A378127 A378128 A378129

Keyword

nonn,tabl

Author

Jimin Park, Nov 17 2024

Status

approved