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

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, 16, 47, 22, 26, 0, 129, 98, 100, 68, 106, 72, 75, 40, 122, 84, 87, 48, 95, 54, 58, 16, 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

Offset

0,5

Comments

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.

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

References

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

Links

Antti Karttunen and Paul Tek, Table of n, a(n) for n = 0..8191 (First 4096 terms from Karttunen)

J. Lagarias, Products of binomial coefficients and Farey fractions, Lecture in DIMACS Conference on Challenges of Identifying Integer Sequences, October 9, 2014; Part 1, Part 2.

Jeffrey C. Lagarias, Harsh Mehta, Products of binomial coefficients and unreduced Farey fractions, arXiv:1409.4145 [math.NT], 2014.

Formula

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

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)].

a(n) = A007814(A001142(n)). - Jason Kimberley, Nov 02 2011

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

a(n) = 2*A000788(n) - A249154(n). - Antti Karttunen, Nov 02 2014

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

Example

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

Mathematica

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

Prog

(PARI) a(n)=sum(k=0, n, valuation(binomial(n, k), 2))
(PARI)
\\ 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):
A065040(m, k) = (hammingweight(k)+hammingweight(m-k)-hammingweight(m));
A187059(n) = sum(k=0, n, A065040(n, k));
for(n=0, 4095, write("b187059.txt", n, " ", A187059(n)));
\\ Antti Karttunen, Oct 25 2014
(Haskell)
a187059 = a007814 . a001142  -- Reinhard Zumkeller, Mar 16 2015

Crossrefs

Row sums of triangular table A065040.

Row 1 of array A249421.

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)).

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

Sequence in context: A256167 A207528 A019901 * A267120 A267484 A181697

Adjacent sequences: A187056 A187057 A187058 * A187060 A187061 A187062

Keyword

nonn,easy,look

Author

Bruce Reznick, Mar 05 2011

Extensions

Name clarified by Antti Karttunen, Oct 22 2014

Status

approved