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

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

Offset: 0

Author

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

Keywords

• nonn
• tabl
• easy

Comments

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

Examples

			Triangle begins:
[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, 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]
... - _N. J. A. Sloane_, Aug 21 2021
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..10010; the first 141 antidiagonals, flattened
• Tyler Ball, Tom Edgar, and Daniel Juda, Dominance Orders, Generalized Binomial Coefficients, and Kummer's Theorem, Mathematics Magazine, Vol. 87, No. 2, April 2014, pp. 135-143.

Crossrefs

Row sums: A187059.

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

Programs

Maple

A065040 := (n, k) -> padic[ordp](binomial(n, k), 2):
seq(seq(A065040(n,k), k=0..n), n=0..13); # Peter Luschny, Aug 15 2017

Mathematica

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

PARI

T(m,k)=hammingweight(k)+hammingweight(m-k)-hammingweight(m)
for(m=0,9,for(k=0,m,print1(T(m,k)", "))) \\ Charles R Greathouse IV, Mar 26 2013

Formula

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]

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

T(m,k) <= log_2 m, for m > 0. - Charles R Greathouse IV, Mar 26 2013

T(m,k) = log_2(A082907(m,k)). - Tom Edgar, Jun 10 2014

From Antti Karttunen, Oct 28 2014: (Start)

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

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

(End)

Extensions

Name clarified by Antti Karttunen, Oct 28 2014