A065040 -id:A065040 - 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).

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

Bruce Reznick, Mar 05 2011

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.

This is the function ord_2(Ḡ_n) extensively studied in Lagarias-Mehta (2014), and plotted in Fig. 1.1. - Antti Karttunen, Oct 22 2014

			For example, if n = 4, the power of 2 that divides 1*4*6*4*1 is 5.

I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, Wiley, 1991, pages 182, 183, 187 (Ex. 34).

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.

Row sums of triangular table A065040.
Row 1 of array A249421.
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)).
Cf. A000178, A000788, A001142, A002109, A007318, A007814, A174605, A249152, A249150, A249151, A249154, A249343, A249345, A249346, A249347.

a187059 = a007814 . a001142  -- Reinhard Zumkeller, Mar 16 2015

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

a(n)=sum(k=0,n,valuation(binomial(n,k),2))

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

def A187059(n): return (n+1)*n.bit_count()+sum((m:=1<>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

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) = A007814(A001142(n)). - Jason Kimberley, Nov 02 2011
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) = 2*A000788(n) - A249154(n). - Antti Karttunen, Nov 02 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.

Name clarified by Antti Karttunen, Oct 22 2014

A385458 Triangle read by rows: T(n,k) = exponent of the highest power of 2 dividing each Fibonomial coefficient fibonomial(n, k).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 2, 3, 3, 0, 0, 0, 3, 2, 2, 3, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 1, 1, 0, 3, 3, 0, 1, 1, 0, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 3, 4, 4, 1, 4, 4, 3, 4, 4, 0

Offset: 0

David Radcliffe, Jun 29 2025

			Triangle begins:
   n\k  0  1  2  3  4  5  6  7  8  9 10 11 12
   0:   0
   1:   0  0
   2:   0  0  0
   3:   0  1  1  0
   4:   0  0  1  0  0
   5:   0  0  0  0  0  0
   6:   0  3  3  2  3  3  0
   7:   0  0  3  2  2  3  0  0
   8:   0  0  0  2  2  2  0  0  0
   9:   0  1  1  0  3  3  0  1  1  0
  10:   0  0  1  0  0  3  0  0  1  0  0
  11:   0  0  0  0  0  0  0  0  0  0  0  0
  12:   0  4  4  3  4  4  1  4  4  3  4  4  0

Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of triangle, flattened).
Donald E. Knuth and Herbert S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math., 396:212-219, 1989.
Romeo Meštrović, Lucas' theorem: its generalizations, extensions and applications (1878--2014), arXiv preprint arXiv:1409.3820 [math.NT], 2014.
David Radcliffe, Matrix plot of the first 768 rows
Diana L. Wells, The Fibonacci and Lucas triangles modulo 2, Fibonacci Quart. 32, no. 2 (1994), 111-123. (Theorem 2)

Cf. A000120, A010048, A007814, A065040, A337923, A385456, A385457, A385608.

function T_row(n)
    function T(n, k)
        c(a, b) = 2 * a + b ÷ 6 - count_ones(a)
        (nd, nm) = divrem(n, 3)
        (kd, km) = divrem(k, 3)
        !(nm < km || (kd & (nd - kd)) != 0) && return 0
        c(nd, n) - c(kd, k) - c((n - k) ÷ 3, n - k)
    end
    [T(n, k) for k in 0:n]
end
for n in 0:12 println(T_row(n)) end  # Peter Luschny, Jul 02 2025

A385608[n_] := A385608[n] = 2*# + Quotient[n, 6] - DigitSum[#, 2] & [Quotient[n, 3]];
A385458[n_, k_] := A385608[n] - A385608[k] - A385608[n-k];
Table[A385458[n, k], {n, 0, 15}, {k, 0, n}] (* Paolo Xausa, Jul 04 2025 *)

def b(n): return 2*(n//3) + n//6 - (n//3).bit_count()
def T(n, k): return b(n) - b(k) - b(n-k) # David Radcliffe, Jul 01 2025

T(n, k) = A007814(A010048(n, k)).
T(n, k) = Sum_{i=1..k} (A337923(n+1-i) - A337923(i)).
T(n, k) = b(n) - b(k) - b(n - k), where b(n) = 2*floor(n/3) + floor(n/6) - A000120(floor(n/3)) = A385608(n) is the 2-adic valuation of the product of the first n Fibonacci numbers.
sign(T(n, k)) = 1 - A385456(n, k). - Peter Luschny, Jul 03 2025

A243759 Triangle T(m,k): exponent of the highest power of 3 dividing the binomial coefficient binomial(m,k).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 1, 2, 2, 1, 2, 2, 0, 0, 0, 2, 1, 1, 2, 1, 1, 2, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 2, 2, 1, 2, 2

Offset: 0

Tom Edgar, Jun 10 2014

T(m,k) is the number of 'carries' that occur when adding k and n-k in base 3 using the traditional addition algorithm.

			The triangle begins:
0,
0, 0,
0, 0, 0,
0, 1, 1, 0;
0, 0, 1, 0, 0;
0, 0, 0, 0, 0, 0;
0, 1, 1, 0, 1, 1, 0;
0, 0, 1, 0, 0, 1, 0, 0;
0, 0, 0, 0, 0, 0, 0, 0, 0;
0, 2, 2, 1, 2, 2, 1, 2, 2, 0;

Robert Israel, Table of n, a(n) for n = 0..10010
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.

Row sums: A249343.

Cf. A007318, A007949, A083093, A065040, A242849, A060828, A038500.

A243759:= (m,k) -> padic[ordp](binomial(m,k),3);
for m from 0 to 50 do
  seq(A243759(m,k),k=0..m)
od;   # Robert Israel, Jun 15 2014

T[m_, k_] := IntegerExponent[Binomial[m, k], 3];
Table[T[m, k], {m, 0, 12}, {k, 0, m}] // Flatten (* Jean-François Alcover, Jun 05 2022 *)

m=50
T=[0]+[3^valuation(i, 3) for i in [1..m]]
Table=[[prod(T[1:i+1])/(prod(T[1:j+1])*prod(T[1:i-j+1])) for j in [0..i]] for i in [0..m-1]]
[log(Integer(x),base=3) for sublist in Table for x in sublist]

(define (A243759 n) (A007949 (A007318 n))) ;; Antti Karttunen, Oct 28 2014

T(m,k) = log_3(A242849(m,k)).
From Antti Karttunen, Oct 28 2014: (Start)
a(n) = A007949(A007318(n)).
a(n) * A083093(n) = 0 and a(n) + A083093(n) > 0 for all n.
(End)

Name clarified by Antti Karttunen, Oct 28 2014

A130067 Binomial coefficients binomial(m,2^k) where m>=1 and 1<=2^k<=m.

Original entry on oeis.org

1, 2, 1, 3, 3, 4, 6, 1, 5, 10, 5, 6, 15, 15, 7, 21, 35, 8, 28, 70, 1, 9, 36, 126, 9, 10, 45, 210, 45, 11, 55, 330, 165, 12, 66, 495, 495, 13, 78, 715, 1287, 14, 91, 1001, 3003, 15, 105, 1365, 6435, 16, 120, 1820, 12870, 1, 17, 136, 2380, 24310, 17, 18, 153, 3060, 43758

Offset: 1

Hieronymus Fischer, May 05 2007, Sep 10 2007

nonn

Provided m and k are given, the sequence index n is n=A001855(m)+k+1. Ordered by m as rows and k as columns the sequence forms a sort of a logarithmically distorted triangle. a(n) is odd if and only if A030308(n)=1.

			a(6)=4 since n=6 gives m=4, k=0 and so binomial(4,2^0)=4.
a(20)=70 since n=20 gives m=8, k=2 and so binomial(8,2^2)=70.

Cf. A130068, A065040, A001855, A030308.

a(n)=binomial(m,2^k), where m=max(j|A001855(j)A001855(m).

A130068 Maximal power of 2 dividing the binomial coefficient binomial(m, 2^k) where m >= 1 and 1 <= 2^k <= m.

Original entry on oeis.org

0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 3, 2, 1, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 2, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 3, 2, 1, 0, 0, 3, 2, 1, 0, 1, 0, 2, 1, 0, 0, 0, 2, 1, 0, 2, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 3, 2, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0

Offset: 1

Hieronymus Fischer, May 05 2007, Sep 10 2007

Provided m and k are given, the sequence index n is n=A001855(m)+k+1. Ordered by m as rows and k as columns the sequence forms a sort of a logarithmically distorted triangle.
a(n) is the maximal power of 2 dividing A130067(n).
Equivalent propositions: (1) a(n)=0; (2) A130067(n) is odd; (3) the k-th digit of m is 1; (4) A030308(n)=1.

			a(6)=2 since 2^2 divides binomial(4,2^0)=4 and 2^3 is not a factor (here n=6 gives m=4, k=0).
a(20)=1 since 2^1 divides binomial(8,2^2)=70 and 2^2 is not a factor (here n=20 gives m=8, k=2).

Cf. A130067, A065040, A001855, A030308.

a(n)=g(m)-g(m-2^k) where g(x)=sum(floor(x/2^i), kA001855(j)A001855(m). Also true: a(n)=sum(product(1-b(i), k<=i

A355604 Table T(n, k), n >= 0, k = 0..n, read by rows; row n is obtained by replacing in row n of Pascal's triangle (A007318) runs of k consecutive even numbers by the terms of row k+1 of the present triangle.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 15, 1, 15, 1, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 1, 1, 15, 1, 15, 1, 1, 1, 1, 9, 1, 5, 1, 1, 5, 1, 9, 1, 1, 1, 45, 1, 1, 1, 1, 1, 45, 1, 1, 1, 11, 55, 165, 1, 3, 3, 1, 165, 55, 11, 1, 1, 1, 1, 1, 495, 1, 1, 1, 495, 1, 1, 1, 1

Offset: 0

Rémy Sigrist, Jul 09 2022

This triangle has fractal features: even terms of Pascal's triangle are clustered as wXwXw subtriangles; these subtriangles are replaced by the first w rows (flipped upside-down) of the present triangle.

			Triangle T(n, k) begins (stars indicate replacements):
  n\k|   0    1    2    3    4    5    6    7    8    9   10   11   12
  ---+-----------------------------------------------------------------
    0|   1
    1|   1    1
    2|   1    1*   1
    3|   1    3    3    1
    4|   1    1*   1*   1*   1
    5|   1    5    1*   1*   5    1
    6|   1    1*  15    1*  15    1*   1
    7|   1    7   21   35   35   21    7    1
    8|   1    1*   1*  15*   1*  15*   1*   1*   1
    9|   1    9    1*   5*   1*   1*   5*   1*   9    1
   10|   1    1*  45    1*   1*   1*   1*   1*  45    1*   1
   11|   1   11   55  165    1*   3*   3*   1* 165   55   11    1
   12|   1    1*   1*   1* 495    1*   1*   1* 495    1*   1*   1*   1

Rémy Sigrist, Table of n, a(n) for n = 0..8384 (rows for n = 0..128 flattened)
Rémy Sigrist, Colored representation of the first 2^10 rows (where the hue is function of T(n, k), black pixels correspond to 1's)
Index entries for triangles and arrays related to Pascal's triangle

Cf. A007318, A065040, A014421, A143333, A348648.

row(n) = { my (r=binomial(n)); for (i=1, #r, if (r[i]%2==0, for (w=1, oo, if (r[i+w]%2==1, my (t=row(w-1)); for (j=1, #t, r[i-1+j]=t[j]); i+=w; break)))); return (r) }

Showing 1-6 of 6 results.

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

A385458 Triangle read by rows: T(n,k) = exponent of the highest power of 2 dividing each Fibonomial coefficient fibonomial(n, k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Julia

Mathematica

Python

Formula

A243759 Triangle T(m,k): exponent of the highest power of 3 dividing the binomial coefficient binomial(m,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Scheme

Formula

Extensions

A130067 Binomial coefficients binomial(m,2^k) where m>=1 and 1<=2^k<=m.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A130068 Maximal power of 2 dividing the binomial coefficient binomial(m, 2^k) where m >= 1 and 1 <= 2^k <= m.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A355604 Table T(n, k), n >= 0, k = 0..n, read by rows; row n is obtained by replacing in row n of Pascal's triangle (A007318) runs of k consecutive even numbers by the terms of row k+1 of the present triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI