login
Triangle read by rows: T(m,k) = exponent of the highest power of 2 dividing the binomial coefficient binomial(m,k).
6

%I #46 Oct 09 2021 03:17:16

%S 0,0,0,0,1,0,0,0,0,0,0,2,1,2,0,0,0,1,1,0,0,0,1,0,2,0,1,0,0,0,0,0,0,0,

%T 0,0,0,3,2,3,1,3,2,3,0,0,0,2,2,1,1,2,2,0,0,0,1,0,3,1,2,1,3,0,1,0,0,0,

%U 0,0,1,1,1,1,0,0,0,0,0,2,1,2,0,3,2,3,0,2,1,2,0,0,0,1,1,0,0,2,2,0,0,1,1,0,0

%N Triangle read by rows: T(m,k) = exponent of the highest power of 2 dividing the binomial coefficient binomial(m,k).

%C T(m,k) is the number of 'carries' that occur when adding k and m-k in base 2 using the traditional addition algorithm. - _Tom Edgar_, Jun 10 2014

%H Antti Karttunen, <a href="/A065040/b065040.txt">Table of n, a(n) for n = 0..10010; the first 141 antidiagonals, flattened</a>

%H Tyler Ball, Tom Edgar, and Daniel Juda, <a href="http://dx.doi.org/10.4169/math.mag.87.2.135">Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem</a>, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.

%F As an array f(i,j) = f(j,i) = T(i+j,j) read by antidiagonals: f(0,j) = 0, f(1,j) = A007814(j+1), f(i,j) = Sum_{k=0..i-1} (f(1,j+k) - f(1,k)). [corrected by _Kevin Ryde_, Oct 07 2021]

%F The n-th term a(n) is equal to the binomial coefficient binomial(m,k), where m = floor((1+sqrt(8*n+1))/2) - 1 and k = n - m(m+1)/2. Also a(n) = g(m) - g(k) - g(m-k), where g(x) = Sum_{i=1..floor(log_2(x))} floor(x/2^i), m = floor((1+sqrt(8*n+1))/2) - 1, k = n - m(m+1)/2. - _Hieronymus Fischer_, May 05 2007

%F T(m,k) <= log_2 m, for m > 0. - _Charles R Greathouse IV_, Mar 26 2013

%F T(m,k) = log_2(A082907(m,k)). - _Tom Edgar_, Jun 10 2014

%F From _Antti Karttunen_, Oct 28 2014: (Start)

%F a(n) = A007814(A007318(n)).

%F a(n) * A047999(n) = 0 and a(n) + A047999(n) > 0 for all n.

%F (End)

%e Triangle begins:

%e [0]

%e [0, 0]

%e [0, 1, 0]

%e [0, 0, 0, 0]

%e [0, 2, 1, 2, 0]

%e [0, 0, 1, 1, 0, 0]

%e [0, 1, 0, 2, 0, 1, 0]

%e [0, 0, 0, 0, 0, 0, 0, 0]

%e [0, 3, 2, 3, 1, 3, 2, 3, 0]

%e [0, 0, 2, 2, 1, 1, 2, 2, 0, 0]

%e [0, 1, 0, 3, 1, 2, 1, 3, 0, 1, 0]

%e ... - _N. J. A. Sloane_, Aug 21 2021

%p A065040 := (n, k) -> padic[ordp](binomial(n, k), 2):

%p seq(seq(A065040(n,k), k=0..n), n=0..13); # _Peter Luschny_, Aug 15 2017

%t T[m_, k_] := IntegerExponent[Binomial[m, k], 2]; Table[T[m, k], {m, 0, 13}, {k, 0, m}] // Flatten (* _Jean-François Alcover_, Oct 06 2016 *)

%o (PARI) T(m,k)=hammingweight(k)+hammingweight(m-k)-hammingweight(m)

%o for(m=0,9,for(k=0,m,print1(T(m,k)", "))) \\ _Charles R Greathouse IV_, Mar 26 2013

%Y Row sums: A187059.

%Y Cf. A007318, A007814, A001511, A000120, A047999, A049606, A000680, A048881, A011371, A005187, A000265, A001316, A001317, A243759.

%K nonn,tabl,easy

%O 0,12

%A Claude Lenormand (hlne.lenormand(AT)voono.net), Nov 05 2001

%E Name clarified by _Antti Karttunen_, Oct 28 2014