login
The exponent of highest power of 2 dividing the product of the elements of the n-th row of Pascal's triangle (A001142).
14

%I #73 Jun 03 2022 11:06:32

%S 0,0,1,0,5,2,4,0,17,10,12,4,18,8,11,0,49,34,36,20,42,24,27,8,58,36,39,

%T 16,47,22,26,0,129,98,100,68,106,72,75,40,122,84,87,48,95,54,58,16,

%U 162,116,119,72,127,78,82,32,147,94,98,44,108,52,57,0,321,258,260,196,266,200,203,136,282,212,215,144,223,150,154,80,322,244,247,168,255,174,178,96,275,190,194,108,204,116,121,32,418,324,327,232,335

%N The exponent of highest power of 2 dividing the product of the elements of the n-th row of Pascal's triangle (A001142).

%C The exponent of the highest power of 2 which divides Product_{k=0..n} binomial(n, k). This can be computed using de Polignac's formula.

%C This is the function ord_2(Ḡ_n) extensively studied in Lagarias-Mehta (2014), and plotted in Fig. 1.1. - _Antti Karttunen_, Oct 22 2014

%D I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, Wiley, 1991, pages 182, 183, 187 (Ex. 34).

%H Antti Karttunen and Paul Tek, <a href="/A187059/b187059.txt">Table of n, a(n) for n = 0..8191</a> (First 4096 terms from Karttunen)

%H J. Lagarias, Products of binomial coefficients and Farey fractions, Lecture in DIMACS Conference on Challenges of Identifying Integer Sequences, October 9, 2014; <a href="http://vimeo.com/album/3082332/video/108501186">Part 1</a>, <a href="http://vimeo.com/108501187">Part 2</a>.

%H Jeffrey C. Lagarias, Harsh Mehta, <a href="http://arxiv.org/abs/1409.4145">Products of binomial coefficients and unreduced Farey fractions</a>, arXiv:1409.4145 [math.NT], 2014.

%F a(2^k-1) = 0 (19th century); a(2^k) = (k-1)*2^k+1 for k >= 1. (Use de Polignac.)

%F a(n) = Sum_{i=0..n} A065040(n,i) [where the entries of triangular table A065040(m,k) give the exponent of the maximal power of 2 dividing binomial coefficient A007318(m,k)].

%F a(n) = A007814(A001142(n)). - _Jason Kimberley_, Nov 02 2011

%F a(n) = A249152(n) - A174605(n). [Exponent of 2 in the n-th hyperfactorial minus exponent of 2 in the n-th superfactorial. Cf. for example Lagarias & Mehta paper or Peter Luschny's formula for A001142.] - _Antti Karttunen_, Oct 25 2014

%F a(n) = 2*A000788(n) - A249154(n). - _Antti Karttunen_, Nov 02 2014

%F a(n) = Sum_{i=1..n} (2*i-n-1)*v_2(i), where v_2(i) = A007814(i) is the exponent of the highest power of 2 dividing i. - _Ridouane Oudra_, Jun 02 2022

%e For example, if n = 4, the power of 2 that divides 1*4*6*4*1 is 5.

%t a[n_] := Sum[IntegerExponent[Binomial[n, k], 2], {k, 0, n}]; Array[a, 100, 0]

%o (PARI) a(n)=sum(k=0,n,valuation(binomial(n,k),2))

%o (PARI)

%o \\ Much faster version, based on code for A065040 by _Charles R Greathouse IV_ which if reduced even further gives the formula a(n) = 2*A000788(n) - A249154(n):

%o A065040(m,k) = (hammingweight(k)+hammingweight(m-k)-hammingweight(m));

%o A187059(n) = sum(k=0, n, A065040(n, k));

%o for(n=0, 4095, write("b187059.txt", n, " ", A187059(n)));

%o \\ _Antti Karttunen_, Oct 25 2014

%o (Haskell)

%o a187059 = a007814 . a001142 -- _Reinhard Zumkeller_, Mar 16 2015

%Y Row sums of triangular table A065040.

%Y Row 1 of array A249421.

%Y Cf. A000295 (a(2^k-2)), A000337 (a(2^k)), A005803 (a(2^k-3)), A036799 (a(2^k+1)), A109363 (a(2^k-4)).

%Y Cf. A000178, A000788, A001142, A002109, A007318, A007814, A174605, A249152, A249150, A249151, A249154, A249343, A249345, A249346, A249347.

%K nonn,easy,look

%O 0,5

%A _Bruce Reznick_, Mar 05 2011

%E Name clarified by _Antti Karttunen_, Oct 22 2014