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
Examples
For example, if n = 4, the power of 2 that divides 1*4*6*4*1 is 5.
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 and Harsh Mehta, Products of binomial coefficients and unreduced Farey fractions, arXiv:1409.4145 [math.NT], 2014.
Crossrefs
Programs
-
Haskell
a187059 = a007814 . a001142 -- Reinhard Zumkeller, Mar 16 2015
-
Mathematica
a[n_] := Sum[IntegerExponent[Binomial[n, k], 2], {k, 0, n}]; Array[a, 100, 0] A187059[n_] := Sum[#*((#+1)*2^k - n - 1) & [Floor[n/2^k]], {k, Floor[Log2[n]]}]; Array[A187059, 100, 0] (* Paolo Xausa, Feb 11 2025 *) 2*Accumulate[#] - Range[Length[#]]*# & [DigitCount[Range[0, 99], 2, 1]] (* Paolo Xausa, Feb 11 2025 *) -
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
-
Python
def A187059(n): return (n+1)*n.bit_count()+sum((m:=1<
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) = 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) = 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
a(n) = Sum_{k=1..floor(log_2(n))} t*((t+1)*2^k - n - 1), where t = floor(n/(2^k)). - Paolo Xausa, Feb 11 2025, derived from Ridouane Oudra's formula above.
Extensions
Name clarified by Antti Karttunen, Oct 22 2014
Comments