cp's OEIS Frontend

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

%I A187059 #83 Feb 11 2025 07:51:39
%S A187059 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 A187059 16,47,22,26,0,129,98,100,68,106,72,75,40,122,84,87,48,95,54,58,16,
%U A187059 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 A187059 The exponent of highest power of 2 dividing the product of the elements of the n-th row of Pascal's triangle (A001142).
%C A187059 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 A187059 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 A187059 I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, Wiley, 1991, pages 182, 183, 187 (Ex. 34).
%H A187059 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 A187059 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 A187059 Jeffrey C. Lagarias and 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 A187059 a(2^k-1) = 0 (19th century); a(2^k) = (k-1)*2^k+1 for k >= 1. (Use de Polignac.)
%F A187059 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 A187059 a(n) = A007814(A001142(n)). - _Jason Kimberley_, Nov 02 2011
%F A187059 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 A187059 a(n) = 2*A000788(n) - A249154(n). - _Antti Karttunen_, Nov 02 2014
%F A187059 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
%F A187059 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.
%e A187059 For example, if n = 4, the power of 2 that divides 1*4*6*4*1 is 5.
%t A187059 a[n_] := Sum[IntegerExponent[Binomial[n, k], 2], {k, 0, n}]; Array[a, 100, 0]
%t A187059 A187059[n_] := Sum[#*((#+1)*2^k - n - 1) & [Floor[n/2^k]], {k, Floor[Log2[n]]}];
%t A187059 Array[A187059, 100, 0] (* _Paolo Xausa_, Feb 11 2025 *)
%t A187059 2*Accumulate[#] - Range[Length[#]]*# & [DigitCount[Range[0, 99], 2, 1]] (* _Paolo Xausa_, Feb 11 2025 *)
%o A187059 (PARI) a(n)=sum(k=0,n,valuation(binomial(n,k),2))
%o A187059 (PARI)
%o A187059 \\ 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 A187059 A065040(m,k) = (hammingweight(k)+hammingweight(m-k)-hammingweight(m));
%o A187059 A187059(n) = sum(k=0, n, A065040(n, k));
%o A187059 for(n=0, 4095, write("b187059.txt", n, " ", A187059(n)));
%o A187059 \\ _Antti Karttunen_, Oct 25 2014
%o A187059 (Haskell)
%o A187059 a187059 = a007814 . a001142  -- _Reinhard Zumkeller_, Mar 16 2015
%o A187059 (Python)
%o A187059 def A187059(n): return (n+1)*n.bit_count()+sum((m:=1<<j)*((k:=n>>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1)) # _Chai Wah Wu_, Nov 11 2024
%Y A187059 Row sums of triangular table A065040.
%Y A187059 Row 1 of array A249421.
%Y A187059 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 A187059 Cf. A000178, A000788, A001142, A002109, A007318, A007814, A174605, A249152, A249150, A249151, A249154, A249343, A249345, A249346, A249347.
%K A187059 nonn,easy,look
%O A187059 0,5
%A A187059 _Bruce Reznick_, Mar 05 2011
%E A187059 Name clarified by _Antti Karttunen_, Oct 22 2014