|
%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
|
