A249152 -id:A249152 - 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

A174605 Partial sums of A011371.

Original entry on oeis.org

0, 0, 1, 2, 5, 8, 12, 16, 23, 30, 38, 46, 56, 66, 77, 88, 103, 118, 134, 150, 168, 186, 205, 224, 246, 268, 291, 314, 339, 364, 390, 416, 447, 478, 510, 542, 576, 610, 645, 680, 718, 756, 795, 834, 875, 916, 958, 1000, 1046, 1092, 1139, 1186, 1235, 1284, 1334

Offset: 0

Jonathan Vos Post, Mar 23 2010

Exponent of 2 in the superfactorials, i.e., a(n) = A007814(A000178(n)). - Ralf Stephan, Jan 03 2014

Amiram Eldar, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47. Also first authors' copy, 2016.
Jeffrey C. Lagarias and Harsh Mehta, Products of Binomial Coefficients and Unreduced Farey Fractions, arXiv:1409.4145 [math.NT], 2014, see a(n) = ord_p(N*_n) for p=2 in theorem 4.1.
A. Mir, F. Rossello and L. Rotger, A new balance index for phylogenetic trees, arXiv preprint arXiv:1202.1223 [q-bio.PE], 2012, see proposition 15, a(n) = x(n) = f(n+1).

Cf. A000120, A011371 (first differences).
Cf. A000178 (superfactorials), A007814 (2-adic valuation), A272011 (binary exponents).
Cf. A249152 (hyperfactorial valuation), A187059 (binomial valuation), A173345 (superfactorial 10-valuation).

a:= proc(n) option remember; `if`(n<1, 0,
      a(n-1)+n-add(i, i=Bits[Split](n)))
    end:
seq(a(n), n=0..54);  # Alois P. Heinz, Oct 30 2021

Accumulate[Table[n-DigitCount[n,2,1],{n,0,130}]] (* Harvey P. Dale, Feb 26 2015 *)
a[n_] := IntegerExponent[BarnesG[n + 2], 2]; Array[a, 100, 0] (* Amiram Eldar, Aug 08 2024 *)

a(n) = n++; my(v=binary(n),t=#v-1); for(i=1,#v, if(v[i],v[i]=t++,t--)); (n^2 - fromdigits(v,2))>>1; \\ Kevin Ryde, Oct 29 2021

def A174605(n): return (n*(n+1)>>1)-(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))>>1)  # Chai Wah Wu, Nov 12 2024

a(n) = Sum_{i=0..n} A011371(i).
From Kevin Ryde, Oct 29 2021: (Start)
a(n) = n*(n+1)/2 - A000788(n).
a(n) ~ (n^2)/2 + O(n*log_2(n)). [Lagarias and Mehta, theorem 4.2 with p=2]
a(n) = ( (n+1)^2 - Sum_{i=1..k} (e[i]+2*i-1) * 2^e[i] )/2, where binary expansion n+1 = 2^e[1] + ... + 2^e[k] with descending exponents e[1] > e[2] > ... > e[k] (A272011).
(End)

A143157 Partial sums of A091512.

Original entry on oeis.org

0, 1, 5, 8, 20, 25, 37, 44, 76, 85, 105, 116, 152, 165, 193, 208, 288, 305, 341, 360, 420, 441, 485, 508, 604, 629, 681, 708, 792, 821, 881, 912, 1104, 1137, 1205, 1240, 1348, 1385, 1461, 1500, 1660, 1701, 1785, 1828, 1960, 2005, 2097, 2144, 2384, 2433, 2533, 2584, 2740, 2793, 2901, 2956, 3180

Offset: 0

Gary W. Adamson, Jul 27 2008

			a(4) = 20 = sum of row 4 terms of triangle A143156, (7 + 6 + 4 + 3).
a(4) = 20 = partial sums of first 4 terms of A091512: (1 + 4 + 3 + 12).
a(4) = 20 = Sum_{j=1..4} j*A001511(j) = 1*1 + 2*2 + 3*1 + 4*3.

Antti Karttunen, Table of n, a(n) for n = 0..8191

Cf. A001511, A007814, A091512, A143156, A249152, A249153.

{0}~Join~Accumulate@ Array[IntegerExponent[(2 #)^#, 2] &, 56] (* Michael De Vlieger, Sep 29 2019 *)

def A143157(n): return sum(i*(~i&i-1).bit_length() for i in range(2,2*n+1,2))>>1 # Chai Wah Wu, Jul 11 2022

Partial sums of A091512 = Sum_{j>=1} j*A001511(j), where A001511 is the ruler sequence.
Row sums of triangle A143156.
a(n) = A249152(2*n)/2 = A249153(n) / 2. - Antti Karttunen, Oct 25 2014
a(n) = (1/2)*n*(n + 1) + Sum_{i=1..n} i*v_2(i), where v_2(i) = A007814(i) is the exponent of the highest power of 2 dividing i. - Ridouane Oudra, Sep 03 2019; Jan 22 2021
G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 - x)^3. - Ilya Gutkovskiy, Oct 30 2019
a(n) ~ n^2. - Amiram Eldar, Sep 10 2024

a(0) = 0 prepended and more terms computed by Antti Karttunen, Oct 25 2014

A249153 Exponent of 2 in the hyperfactorial of 2n: a(n) = A007814(A002109(2n)).

Original entry on oeis.org

0, 2, 10, 16, 40, 50, 74, 88, 152, 170, 210, 232, 304, 330, 386, 416, 576, 610, 682, 720, 840, 882, 970, 1016, 1208, 1258, 1362, 1416, 1584, 1642, 1762, 1824, 2208, 2274, 2410, 2480, 2696, 2770, 2922, 3000, 3320, 3402, 3570, 3656, 3920, 4010, 4194, 4288, 4768, 4866, 5066, 5168, 5480, 5586, 5802, 5912

Offset: 0

Antti Karttunen, Oct 25 2014

nonn

Chai Wah Wu, Table of n, a(n) for n = 0..10000

Bisection of A249152.

Cf. A002109, A007814, A143157, A069895 (first differences).

Table[IntegerExponent[Hyperfactorial[2*n], 2], {n, 0, 55}] (* Amiram Eldar, Sep 10 2024 *)

from sympy import multiplicity
A249153_list, n = [0], 0
for i in range(2,20002,2):
    n += multiplicity(2,i)*i
    A249153_list.append(n) # Chai Wah Wu, Aug 21 2015

a(n) = A249152(2*n) = A007814(A002109(2*n)).
a(n) = 2*A143157(n).
a(n) ~ 2*n^2. - Amiram Eldar, Sep 10 2024

A246839 Number of trailing zeros in A002109(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 15, 15, 15, 15, 15, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 100, 100, 100, 100, 100, 130, 130, 130, 130, 130, 165, 165, 165, 165, 165, 205, 205, 205, 205, 205, 250, 250, 250, 250, 250, 350, 350, 350, 350, 350, 405, 405, 405, 405

Offset: 0

Chai Wah Wu, Sep 04 2014

Chai Wah Wu, Table of n, a(n) for n = 0..999

Cf. A002109, A112765, A122840, A246817, A027868, A249152.

(n=#;k=0;While[Mod[n,10]==0,n=n/10;k++];k)&/@Hyperfactorial@Range[0,60] (* Giorgos Kalogeropoulos, Sep 14 2021 *)

a(n) = sum(i=1, n, i*valuation(i, 5)); \\ Michel Marcus, Sep 14 2021

def a(n):
  s = 1
  for k in range(n+1):
    s *= k**k
  i = 1
  while not s % 10**i:
    i += 1
  return i-1
n = 1
while n < 100:
  print(a(n),end=', ')
  n += 1 # Derek Orr, Sep 04 2014

from sympy import multiplicity
A246839, p5 = [0,0,0,0,0], 0
for n in range(5,10**3,5):
    p5 += multiplicity(5,n)*n
    A246839.extend([p5]*5)
# Chai Wah Wu, Sep 05 2014

From Michel Marcus, Sep 14 2021: (Start)
a(n) = A122840(A002109(n)), but also,
a(n) = A112765(A002109(n)), see explanation in A002109; so
a(n) = Sum_{i=1..n} i*v_5(i), where v_5(i) = A112765(i) is the exponent of the highest power of 5 dividing i. After a similar formula in A249152. (End)

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

A174605 Partial sums of A011371.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A143157 Partial sums of A091512.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A249153 Exponent of 2 in the hyperfactorial of 2n: a(n) = A007814(A002109(2n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A246839 Number of trailing zeros in A002109(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula