cp's OEIS Frontend

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.

%I A386912 #57 Aug 19 2025 12:28:08
%S A386912 1,2,6,16,60,192,672,2048,8640,30720,118272,393216,1597440,5505024,
%T A386912 20643840,67108864,300810240,1132462080,4602200064,16106127360,
%U A386912 68702699520,248034361344,972407439360,3298534883328,14495514624000,53601191854080
%N 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.
%H A386912 Alois P. Heinz, <a href="/A386912/b386912.txt">Table of n, a(n) for n = 1..1666</a> (first 300 terms from Mareike Fischer)
%H A386912 Sean Cleary, Mareike Fischer, and Katherine St. John, <a href="https://arxiv.org/abs/2502.12854">The GFB Tree and Tree Imbalance Indices</a>, arXiv:2502.12854 [q-bio.PE], 2025.
%F A386912 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 ).
%F A386912 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).
%F A386912 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
%e A386912 a(1)=1, because a(1)=Product(i=2..1)=1 (empty product).
%e A386912 a(2)=2, because q(2,2)=1, so a(2)=2^q(2,2)=2^1=2.
%e A386912 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.
%p A386912 a:= proc(n) option remember; `if`(n<2, 1, (b-> (f->
%p A386912       a(f)*n*a(n-f))(min(b, n-b/2)))(2^ilog2(n-1)))
%p A386912     end:
%p A386912 seq(a(n), n=1..26);  # _Alois P. Heinz_, Aug 18 2025
%t A386912 q[n_, i_] := Module[{factor, ki}, factor = FactorInteger[i];
%t A386912   ki = Ceiling[Log2[i]];
%t A386912   If[(i == 1 || i == n), Return[n/i],
%t A386912    If[(Length[factor] == 1 && factor[[1]][[1]] == 2),
%t A386912      If[(Mod[n, i] == 0 || Mod[n, i] >= 2^(ki - 1)),
%t A386912       Return[Floor[n/i]], Return[Floor[n/i] - 1]],
%t A386912      If[Mod[n - i, 2^(ki - 1)] == 0, Return[1], Return[0]]];
%t A386912    ]];
%t A386912 a[n_] := Product[i^q[n, i], {i, 2, n}]; alist = {};
%t A386912 For[n = 1, n <= 300, n++, AppendTo[alist, a[n]]]; Print[alist]
%t A386912 (* Alternative, after _Alois P. Heinz_: *)
%t A386912 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 *)
%o A386912 (Python)
%o A386912 from functools import lru_cache
%o A386912 @lru_cache(maxsize=None)
%o A386912 def a(n: int) -> int:
%o A386912     if n < 2: return 1
%o A386912     b = 1 << ((n - 1).bit_length() - 1)
%o A386912     f = min(b, n - b // 2)
%o A386912     return a(f) * n * a(n - f)
%o A386912 print([a(n) for n in range(1, 27)])  # after _Alois P. Heinz_, _Peter Luschny_, Aug 19 2025
%Y A386912 Cf. A132862.
%K A386912 nonn
%O A386912 1,2
%A A386912 _Mareike Fischer_, Aug 07 2025