login
a(n) = 2^(n - HammingWeight(n)) = 2^(n - BitCount(n)) = 2^(n - A000120(n)).
32

%I #101 Mar 23 2024 09:24:48

%S 1,1,2,2,8,8,16,16,128,128,256,256,1024,1024,2048,2048,32768,32768,

%T 65536,65536,262144,262144,524288,524288,4194304,4194304,8388608,

%U 8388608,33554432,33554432,67108864,67108864,2147483648,2147483648,4294967296

%N a(n) = 2^(n - HammingWeight(n)) = 2^(n - BitCount(n)) = 2^(n - A000120(n)).

%C a(n) is the size of the Sylow 2-subgroup of the symmetric group S_n.

%C Also largest power of 2 which is a factor of n! and (apart from a(3)) the largest perfect power which is a factor of n!.

%C Denominator of e(n,n) (see Maple line).

%C Denominator of the coefficient of x^n in n-th Legendre polynomial; numerators are in A001790. - _Benoit Cloitre_, Nov 29 2002

%H Harry J. Smith, <a href="/A060818/b060818.txt">Table of n, a(n) for n = 0..200</a>

%H Tyler Ball, Tom Edgar, and Daniel Juda, <a href="http://dx.doi.org/10.4169/math.mag.87.2.135">Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem</a>, Mathematics Magazine, 87(2) (2014), 135-143.

%H V. H. Moll, <a href="http://www.ams.org/notices/200203/fea-moll.pdf">The evaluation of integrals: a personal story</a>, Notices Amer. Math. Soc., 49(3) (2002), 311-317.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RandomWalk1-Dimensional.html">Random Walk 1-Dimensional</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LegendrePolynomial.html">Legendre Polynomial</a>.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%F a(n) = 2^(floor(n/2) + floor(n/4) + floor(n/8) + floor(n/16) + ...).

%F a(n) = 2^(A011371(n)).

%F a(n) = gcd(n!, 2^n). - _Labos Elemer_, Apr 22 2003

%F a(n) = denominator(L(n)) with rational L(n):=binomial(2*n,n)/2^n. L(n) is the leading coefficient of the Legendre polynomial P_n(x).

%F L(n) = (2*n-1)!!/n!, with the double factorial (2*n-1)!! = A001147(n), n>=0.

%F a(n) = Product_{i=1..n} A006519(i). - _Tom Edgar_, Apr 30 2014

%F a(n) = (n! XOR floor(n!/2)) XOR (n!-1 XOR floor((n!-1)/2)). - _Gary Detlefs_, Jun 13 2014

%F a(n) = denominator(Catalan(n-1)/2^(n-1)) for n>0. - _Vincenzo Librandi_, Sep 01 2014

%F a(2*n) = a(2*n+1) = 2^n*a(n). - _Robert Israel_, Sep 01 2014

%F a(n) = n!*A063079(n+1)/A334907(n). - _Petros Hadjicostas_, May 16 2020

%e G.f. = 1 + x + 2*x^2 + 2*x^3 + 8*x^4 + 8*x^5 + 16*x^6 + 16*x^7 + 128*x^8 + ...

%e e(n,n) sequence begins 1, 1, 3/2, 5/2, 35/8, 63/8, 231/16, 429/16, 6435/128, 12155/128, 46189/256, ... .

%p e := proc(l,m) local k; add(2^(k-2*m) * binomial(2*m-2*k,m-k) * binomial(m+k,m) * binomial(k,l), k=l..m); end;

%p A060818 := proc(n) option remember; `if`(n=0,1,2^(padic[ordp](n,2))*A060818(n-1)) end: seq(A060818(i), i=0..34); # _Peter Luschny_, Nov 16 2012

%p HammingWeight := n -> add(convert(n, base, 2)):

%p seq(2^(n - HammingWeight(n)), n = 0..34); # _Peter Luschny_, Mar 23 2024

%t Table[GCD[w!, 2^w], {w, 100}]

%t (* Second program, more efficient *)

%t Array[2^(# - DigitCount[#, 2, 1]) &, 35, 0] (* _Michael De Vlieger_, Mar 23 2024 *)

%o (PARI) {a(n) = denominator( polcoeff( pollegendre(n), n))};

%o (PARI) {a(n) = if( n<0, 0, 2^sum(k=1, n, n\2^k))};

%o (PARI) { for (n=0, 200, s=0; d=2; while (n>=d, s+=n\d; d*=2); write("b060818.txt", n, " ", 2^s); ) } \\ _Harry J. Smith_, Jul 12 2009

%o (Sage)

%o def A060818(n):

%o A005187 = lambda n: A005187(n//2) + n if n > 0 else 0

%o return 2^A005187(n//2)

%o [A060818(i) for i in (0..34)] # _Peter Luschny_, Nov 16 2012

%o (Magma) [1] cat [Denominator(Catalan(n)/2^n): n in [0..50]]; // _Vincenzo Librandi_, Sep 01 2014

%o (Python 3.10+)

%o def A060818(n): return 1<<n-n.bit_count() # _Chai Wah Wu_, Jul 11 2022

%Y Cf. A000120, A005187, A001790, A011371, A334907.

%Y a(n) = A046161([n/2]).

%Y Row sums of triangle A100258.

%K nonn,easy,frac

%O 0,3

%A Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 29 2001

%E Additional comments from _Henry Bottomley_, May 01 2001

%E New name from _Peter Luschny_, Mar 23 2024