A112884 Number of bits required to represent binomial(2^n, 2^(n-1)).

1, 2, 3, 7, 14, 30, 61, 125, 252, 508, 1019, 2043, 4090, 8186, 16377, 32761, 65528, 131064, 262135, 524279, 1048566, 2097142, 4194293, 8388597, 16777204, 33554420, 67108851, 134217715, 268435442, 536870898, 1073741809, 2147483633, 4294967280, 8589934576, 17179869167

Offset: 0

Author

Matt Erbst (matt(AT)erbst.org), Oct 04 2005

Keywords

• easy
• nonn

Examples

			a(2) = 3 because binomial(2^2, 2^1) in binary = 110.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3321
• Sela Fried, The number of bits required to represent binomial(2^n, 2^(n-1)), 2024.
• Sela Fried, Proofs of some Conjectures from the OEIS, arXiv:2410.07237 [math.NT], 6 October 2024.
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Crossrefs

a(n) represents the size of A037293 in binary - see also the central binomial coefficients: A001405.

Cf. A000079, A004526, A070939.

Programs

Mathematica

Table[IntegerLength[Binomial[2^n,2^(n-1)],2],{n,25}] (* or *)
CoefficientList[Series[(-2 x^3+3x-2)/((x-1)^2 (2x^2+x-1)), {x,0,25}], x] (* Harvey P. Dale, Apr 06 2011 *)

PHP

$LastFact = gmp_init('1'); for ($i = 2; $i !== 65536; $i *= 2) { $Fact = gmp_fact($i); $Result = gmp_div_q($Fact, gmp_pow($OldFact, 2)); $LastFact = $Fact; echo gmp_strval($Result, 2).'
'; }

Formula

Appears to be equal to 2^n - floor(n/2) = A000079(n) - A004526(n).

G.f.: (-3*x^3 + 2*x^2 + x - 1)/((x - 1)^2*(2*x^2 + x - 1)). - Conjectured by Harvey P. Dale, Apr 06 2011

a(n) = A070939(A037293(n)). - Alois P. Heinz, Feb 17 2024

The conjectured formula 2^n - floor(n/2) and consequent g.f. are true (see links). - Sela Fried, Oct 03 2024

Extensions

a(0)=1 prepended and g.f. adapted by Alois P. Heinz, Oct 11 2024