A386912 The base-2 logarithm of this sequence equals the Q statistic value of the greedy-from-the-bottom tree with n leaves, which is the minimal Q statistic value for n.

1, 2, 6, 16, 60, 192, 672, 2048, 8640, 30720, 118272, 393216, 1597440, 5505024, 20643840, 67108864, 300810240, 1132462080, 4602200064, 16106127360, 68702699520, 248034361344, 972407439360, 3298534883328, 14495514624000, 53601191854080

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1666 (first 300 terms from Mareike Fischer)

Sean Cleary, Mareike Fischer, and Katherine St. John, The GFB Tree and Tree Imbalance Indices, arXiv:2502.12854 [q-bio.PE], 2025.

Formula

a(n) = Product_{i=2..n} i^q(n,i), with k(i)=ceiling(log_2(i)) and q(n,i)=floor(n/i) if (i=2^(k(i)) and ((n mod i)=0 or (n mod i)>=2^(k(i)-1))), and q(n,i)=floor(n/i)-1 if (i=2^(k(i)) and (0 < (n mod i)< 2^(k(i)-1))) and q(n,i)=1 if (i!=2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) =0 ) and q(n,i)=0 if (i!=2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) >0 ).

a(n) = Product_{i=0..k(n)-1} (2^(k(n)-i))^(2^i) if d(n)=2^(k(n)-1). Else, a(n) = Product_{i=0..k(n)-2} (2^(k(n)-i-1))^(2^i) * 2^d(n) * Product_{i=1..k(n)-1} ( 2^floor(d(n)/(2^i)) * ((2^i + (d(n)-2^i*(floor(d(n)/(2^i))))) / (2^i) )^(ceiling(d(n)/2^i)-floor(d(n)/(2^i))) if d(n) < 2^(k(n)-1), with k(n)=ceiling(log_2(n)) and d(n)=n-2^(k(n)-1).

a(n) = n*a(f)*a(n-f) with f = min(b,n-b/2) and b = 2^floor(log_2(n-1)) for n>1, a(1) = 1. - Alois P. Heinz, Aug 18 2025

Example

a(1)=1, because a(1)=Product(i=2..1)=1 (empty product).
a(2)=2, because q(2,2)=1, so a(2)=2^q(2,2)=2^1=2.
a(3)=6, because q(3,2)=1 and q(3,3)=1, so a(3)=2^q(3,2)*3^q(3,3)=2^1*3^1=6.

Maple

a:= proc(n) option remember; `if`(n<2, 1, (b-> (f->
      a(f)*n*a(n-f))(min(b, n-b/2)))(2^ilog2(n-1)))
    end:
seq(a(n), n=1..26);  # Alois P. Heinz, Aug 18 2025

Mathematica

q[n_, i_] := Module[{eki = 2^(Ceiling[Log2[i]]-1)},
  If[i == 1 || i == n, n/i,
   If[MatchQ[FactorInteger[i], {{2, _}}],
     If[Mod[n, i] == 0 || Mod[n, i] >= eki,
      Floor[n/i], Floor[n/i] - 1],
     Boole[Mod[n - i, eki] == 0]]
   ]];
a[n_] := Product[i^q[n, i], {i, 2, n}];
Table[a[n], {n, 50}]
(* Alternative: after Alois P. Heinz: *)
A386912[n_] := A386912[n] = If[n == 1, 1, n*A386912[#]*A386912[n - #]] & [Min[#, n - #/2] & [2^(BitLength[n - 1] - 1)]]; Array[A386912, 30] (* Paolo Xausa, Aug 19 2025 *)

Prog

(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def a(n: int) -> int:
    if n < 2: return 1
    b = 1 << ((n - 1).bit_length() - 1)
    f = min(b, n - b // 2)
    return a(f) * n * a(n - f)
print([a(n) for n in range(1, 27)])  # after Alois P. Heinz, Peter Luschny, Aug 19 2025

Crossrefs

Cf. A132862.

Sequence in context: A006820 A131385 A027742 * A324062 A033301 A197102

Adjacent sequences: A386909 A386910 A386911 * A386913 A386914 A386915

Keyword

nonn,changed

Author

Mareike Fischer, Aug 07 2025

Status

approved