A382732 Number of proper hypercubic bipartitions of n.

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

Offset

0,6

Comments

a(n) is the number of ways n can be written as n = n_0 + n_1 where n_0 >= n_1 >= 1, f(n) = n_1 + f(n_1) + f(n_0) and f is given by the well-known divide-and-conquer maxmin recurrence f(n) = max_{n_0 + n_1 = n, n_0,n_1 >= 1}(min(n_0,n_1) + f(n_0) + f(n_1)) that describes the maximum number of edges of an induced subgraph on n vertices in the rectangular grid Z^k where k >= ceiling(log_2(n)) (large enough). f(n) is given in A000788 (shifted by 1).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Geir Agnarsson, On the number of hypercubic bipartitions of an integer, Discrete Math. 313 (2013), no. 24, 2857-2864.

Formula

a(0) = a(1) = 0, a(n) = a(2^ceiling(log_2(n)) - n) + 1 for n > 1.

a(n) = A382733(n) - 1. - Paolo Xausa, Apr 16 2025

Maple

a:= proc(n) option remember;
      `if`(n<2, 0, 1+a(2^ilog2(2*n-1)-n))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 04 2025

Mathematica

A382732[n_] := A382732[n] = If[n <= 1, 0, A382732[2^BitLength[n - 1] - n] + 1];
Array[A382732, 100, 0] (* Paolo Xausa, Apr 16 2025 *)

Prog

(PARI) a(n) = if(n<2, 0, a(2^(logint(n-1, 2) + 1) - n) + 1) \\ Andrew Howroyd, Apr 03 2025

Crossrefs

Cf. A000788, A382733.

Sequence in context: A284321 A004739 A156282 * A203776 A343559 A242357

Adjacent sequences: A382729 A382730 A382731 * A382733 A382734 A382735

Keyword

nonn

Author

Geir Agnarsson, Apr 03 2025

Status

approved