A048896 -id:A048896 - cp's OEIS frontend

A335063 a(n) = Sum_{k=0..n} (binomial(n,k) mod 2) * k.

0, 1, 2, 6, 4, 10, 12, 28, 8, 18, 20, 44, 24, 52, 56, 120, 16, 34, 36, 76, 40, 84, 88, 184, 48, 100, 104, 216, 112, 232, 240, 496, 32, 66, 68, 140, 72, 148, 152, 312, 80, 164, 168, 344, 176, 360, 368, 752, 96, 196, 200, 408, 208, 424, 432, 880, 224, 456, 464, 944, 480

Offset: 0

Ilya Gutkovskiy, May 21 2020

nonn

Modulo 2 binomial transform of nonnegative integers.

Robert Israel, Table of n, a(n) for n = 0..3000

Cf. A000120, A001316, A001787, A048298, A048896, A333176.

g:= proc(n,k) local L,M,t,j;
   L:= convert(k,base,2);
   M:= convert(n,base,2);
   1-max(zip(`*`,L,M))
end proc:
f:= n -> add(k*g(n-k,k),k=0..n):
map(f, [$0..100]); # Robert Israel, May 24 2020

Table[Sum[Mod[Binomial[n, k], 2] k, {k, 0, n}], {n, 0, 60}]
(* or *)
nmax = 60; CoefficientList[Series[(x/2) D[Product[(1 + 2 x^(2^k)), {k, 0, Log[2, nmax]}], x], {x, 0, nmax}], x]

a(n) = n*2^(hammingweight(n)-1); \\ Michel Marcus, May 22 2020

G.f.: (x/2) * (d/dx) Product_{k>=0} (1 + 2 * x^(2^k)).

a(n) = n * 2^(A000120(n) - 1) = n * A001316(n) / 2.

A101691 A modular binomial sum sequence.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 2, 2, 5, 1, 2, 2, 4, 2, 4, 4, 9, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 17, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 33, 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8

Offset: 0

Paul Barry, Dec 11 2004

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Cf. A048896.

Table[Sum[Mod[Binomial[2n-2,k],2],{k,0,n}],{n,0,100}] (* Harvey P. Dale, Oct 20 2011 *)

def A101691(n): return sum((not ~(n-1<<1)&k) for k in range(n+1)) # Chai Wah Wu, Jul 31 2025

a(n) = Sum_{k=0..n} mod(binomial(2n-2, k), 2).

a(2^n) = A094373(n). a(2^n-1) = 1,1,1,2,4,8,16,...

A193494 Worst case of an unbalanced recursive algorithm over all n-node binary trees.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 13, 14, 16, 18, 22, 24, 28, 32, 40, 41, 43, 45, 49, 51, 55, 59, 67, 69, 73, 77, 85, 89, 97, 105, 121, 122, 124, 126, 130, 132, 136, 140, 148, 150, 154, 158, 166, 170, 178, 186, 202, 204, 208, 212, 220, 224, 232, 240, 256, 260, 268, 276, 292, 300

Offset: 0

Don Knuth, Jul 28 2011

nonn

Solves the recurrence a(0) = 0, a(n+1) = 1 + Max_{0 <= k <= n-k} (2*a(k) + a(n-k)).

a(floor(n/2)) is also the number of white areas in the elementary cellular automata based on rule 126 completed up to generation n. - Philippe Beaudoin, Feb 03 2014

(I think I've seen it years ago, but I have no idea where.)

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 30.
Don Knuth: I may refer to this sequence in my "Christmas tree lecture" this year (2011).
Eric Weisstein's World of Mathematics, Rule 126.

log_2(a(n) - a(n-1)) is A000120(n) - 1, for n > 0.

Cf. A048896 (first differences), A006046.

a:= proc(n) option remember;
      `if`(n=0, 0, 1 +max(seq(2*a(k)+a(n-1-k), k=0..(n-1)/2)))
    end:
seq(a(n), n=0..60); # Alois P. Heinz, Jul 29 2011

a[0]=0; a[n_]:=a[n]=1+Max[Table[2a[k]+a[n-1-k],{k,0,(n-1)/2}]]

a=vector(60); a[1]=0; for(n=0,#a-2,a[n+2]=1+vecmax(vector(n\2+1,k,2*a[k]+a[n-k+2])));a \\ Charles R Greathouse IV, Jul 29 2011

a(n) = O(n^(log_2(3)));
a(n) = 2^(nu(n)-1) + a(n-1) when n>0 and has nu(n) 1-bits in binary (A000120);
If n = 2^(e_1) + ... + 2^(e_t) with e_1 > ... > e_t >= 0, then a(n) = (3^(e_1) + 2*3^(e_2) + ... + 2^(t-1)*3^(e_t) + 2^t-1)/2;
The generating function has the form (t_0 + t_0*t_1 + t_0*t_1*t_2 + ...)/ (1-z), where t_0 = z and t_k = z^{2^{k-1}} + 2*z^{2^k} for k > 0.
a(n) = (A006046(n+1) - 1) / 2. - Kevin Ryde, Jan 30 2022

Third formula corrected by Don Knuth, Dec 08 2011

A333306 a(n) = sqrt(Pi/4)2^A048881(2n)L(2n) where L(s) = lim_{t->s} (t/2)!/((1-t)/2)!.

Original entry on oeis.org

1, 1, -1, 9, -45, 1575, -42525, 3274425, -42567525, 5746615875, -488462349375, 102088631019375, -6431583754220625, 1923043542511966875, -336532619939594203125, 136295711075535652265625, -3952575621190533915703125, 2083007352367411373575546875

Offset: 0

Peter Luschny, May 17 2020

sign

Cf. A048881, A048896, A046161, A034386, A278617.

L := s -> limit((factorial(t/2)/factorial((1-t)/2)), t=s):
G := n -> 2^(add(i, i = convert(n+1, base, 2)) - 1): # A048896
a := s -> sqrt(Pi/4)*G(2*s)*L(2*s): seq(a(n), n=0..17);

A333306[n_] := (-1)^n ((2 n)!/(1 - 2 n)) 2^(-2 n + DigitCount[2 n, 2, 1]);
Table[A333306[n], {n, 0, 17}]

a(n) = Z(2*n)*A048896(2*n)/2 where Z(n) = Pi^n*(n*Zeta(1 - n))/((1 - n)*Zeta(n)) for n >= 1.
a(n) = (-1)^n*(2*n)!/((1 - 2*n)*A046161(2*n)).
A034386(2*n-2)/2 divides a(n), i.e., all odd primes <= 2*(n-1) divide a(n).
The number of distinct prime divisors of a(n) is A278617(n).

A348647 Irregular table read by rows; the n-th row contains the lengths of the runs of consecutive terms with the same parity in the n-th row of Pascal's triangle (A007318).

Original entry on oeis.org

1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 8, 1, 7, 1, 2, 6, 2, 1, 1, 1, 5, 1, 1, 1, 4, 4, 4, 1, 3, 1, 3, 1, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 16, 1, 15, 1, 2, 14, 2, 1, 1, 1, 13, 1, 1, 1, 4, 12, 4, 1, 3, 1, 11, 1, 3, 1

Offset: 0

Rémy Sigrist, Oct 27 2021

For any n >= 0, the n-th row:
- is palindromic,
- has A038573(n+1) terms,
- has leading term A006519(n+1),
- has central term A080079(n+1).

			Triangle begins:
    1;
    2;
    1, 1, 1;
    4;
    1, 3, 1;
    2, 2, 2;
    1, 1, 1, 1, 1, 1, 1;
    8;
    1, 7, 1;
    2, 6, 2;
    1, 1, 1, 5, 1, 1, 1;
    4, 4, 4;
    1, 3, 1, 3, 1, 3, 1;
    2, 2, 2, 2, 2, 2, 2;
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
    16;
    ...

Rémy Sigrist, Table of n, a(n) for n = 0..6304 (rows for n = 0..254, flattened)
Index entries for triangles and arrays related to Pascal's triangle

Cf. A006519, A007318, A038573, A047999, A048896, A080079.

row(n) = { my (b=binomial(n)%2, r=[], p=1, w=1); for (k=2, #b, if (p==b[k], w++, r=concat(r, w); p=b[k]; w=1)); concat(r, w) }

Sum_{k = 1..A038573(n+1)} T(n, k) = n+1.
T(n, 1) = A006519(n+1).
T(n, A048896(n)) = A080079(n+1).
T(2^k-1, 1) = 2^k for any k >= 0.

A355811 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the product of the two numbers directly below it; a(0) = 1.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 8, 16, 8, 8, 16, 32, 32, 128, 256, 4096, 16, 16, 32, 64, 64, 256, 512, 8192, 128, 1024, 2048, 65536, 4096, 524288, 1048576, 4294967296, 32, 32, 64, 128, 128, 512, 1024, 16384, 256, 2048, 4096, 131072, 8192, 1048576, 2097152, 8589934592, 512

Offset: 0

Rémy Sigrist, Jul 18 2022

			For n = 27:
- we have the following triangle:
           65536
         32  2048
       2    16   128
    1     2     8    16
- so a(27) = 65536.

Index entries for sequences related to binary expansion of n

See A355807 for similar sequences.

Cf. A048896, A348296.

a(n) = { my (b=vector(hammingweight(n))); for (k=1, #b, n-=b[k]=2^valuation(n, 2)); while (#b>1, b=vector(#b-1, k, b[k+1]*b[k])); if (#b, b[1], 1) }

a(n) = n iff n is a power of 2.

a(2*n) = a(n) * 2^A048896(n-1) for any n > 0.

A358138 Difference between maximum and minimum part in the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 31 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
The first and last parts are A065120 and A001511, difference A358135.
This is the maximum minus minimum part in row n of A066099.
The version for Heinz numbers of partitions is A243055.
The maximum and minimum parts are A333766 and A333768.
The partial sums of standard compositions are A358134, adjusted A242628.
A011782 counts compositions.
A351014 counts distinct runs in standard compositions.
Cf. A000120, A029837, A029931, A048896, A058891, A070939, A133494, A329395, A357187, A358133.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Max[stc[n]]-Min[stc[n]],{n,1,100}]

a(n) = A333766(n) - A333768(n).

A358330 By concatenating the standard compositions of each part of the a(n)-th standard composition, we get a weakly increasing sequence.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 14, 15, 18, 19, 24, 25, 26, 28, 30, 31, 32, 36, 38, 39, 40, 42, 50, 51, 56, 57, 58, 60, 62, 63, 64, 72, 73, 74, 76, 78, 79, 96, 100, 102, 103, 104, 106, 114, 115, 120, 121, 122, 124, 126, 127, 128, 129, 130, 136, 146, 147

Offset: 1

Gus Wiseman, Nov 10 2022

nonn

Note we shorten the language, "the k-th composition in standard order," to "the standard composition of k."

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The terms together with their standard compositions begin:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   6: (1,2)
   7: (1,1,1)
   8: (4)
   9: (3,1)
  10: (2,2)
  12: (1,3)
  14: (1,1,2)
  15: (1,1,1,1)
  18: (3,2)
  19: (3,1,1)
  24: (1,4)
  25: (1,3,1)
  26: (1,2,2)
For example, the 532,488-th composition is (6,10,4), with standard compositions ((1,2),(2,2),(3)), with weakly increasing concatenation (1,2,2,2,3), so 532,488 is in the sequence.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
Standard compositions are listed by A066099.
Indices of rows of A357135 (ranked by A357134) that are weakly increasing.
Cf. A000120, A001511, A029931, A048896, A058891, A070939, A333766, A335404, A357137, A357186.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],OrderedQ[Join@@stc/@stc[#]]&]

A060318 Powers of 3 in the odd Catalan numbers Catalan(2^n - 1).

Original entry on oeis.org

0, 0, 1, 2, 0, 1, 3, 0, 3, 3, 3, 6, 2, 2, 9, 5, 5, 4, 8, 5, 9, 10, 5, 4, 4, 4, 9, 9, 8, 11, 13, 13, 10, 11, 10, 8, 6, 12, 13, 14, 13, 11, 14, 15, 16, 13, 11, 10, 12, 18, 20, 19, 20, 11, 13, 19, 22, 18, 15, 26, 20, 17, 17, 26, 21, 22, 18, 18, 23, 26, 20, 19, 23, 21, 22, 19, 27, 17, 35

Offset: 1

Wouter Meeussen, Mar 28 2001

nonn

Conjecture: all odd Catalan numbers have smallest prime factor 3, except Catalan(3), which has smallest prime factor 5, and Catalan(31) and Catalan(255), which have smallest prime factor 7 (checked up to Catalan(-1 + 2^2048)).

			a(5)=0 because 2^5 -1 = 31 and Catalan(31) = 7*11*17*19*37*41*43*47*53*59*61 so the power of 3 is zero.

Cf. A007949, A038003.

Cf. A000108, A048896, A048881.

pow3[ nfac_ ] := (nfac - Plus @@ IntegerDigits[ nfac, 3 ])/(3-1); powcat3[ n_ ] := pow3[ 2n ]-pow3[ n+1 ]-pow3[ n ]; Table[ powcat3[ 2^n-1 ], {n, 2048} ]

a(n) = A007949(A038003(n)). - Michel Marcus, Feb 02 2020

A064984 Triangle of coefficients T[n,m] of polynomials n, n^2, (n+2n^3)/3, n^2(2+n^2)/3, n(3+10n^2+2n^4)/15, etc. after multiplication by the denominators (A049606).

Original entry on oeis.org

1, 0, 1, 1, 0, 2, 0, 2, 0, 1, 3, 0, 10, 0, 2, 0, 23, 0, 20, 0, 2, 45, 0, 196, 0, 70, 0, 4, 0, 132, 0, 154, 0, 28, 0, 1, 315, 0, 1636, 0, 798, 0, 84, 0, 2, 0, 5067, 0, 7180, 0, 1806, 0, 120, 0, 2, 14175, 0, 83754, 0, 50270, 0, 7392, 0, 330, 0, 4, 0, 146430, 0, 239327, 0, 74800, 0

Offset: 1

Wouter Meeussen, Oct 30 2001

These polynomials are P(1, n) = 2*Sum[k, {k,1,n-1}] + n, counting up to n and down again; P(2, m) = 2*Sum[P(1,n), {n,1,m-1}] + P(1,m), meaning up and down to n and this for n from 1 up to m and down again; etc.

			1+2+3+2+1 = 3^2, (1)+(1+2+1)+(1+2+3+2+1)+(1+2+1)+(1) = (n+2n^3)/3.

Row sums give A049606 again, final entry in each row seems to give A048896.

CoefficientList[ #, n ]&/@(NestList[ ((2*Sum[ #, {n, k-1} ]+(#/. n->k)//Simplify)/.k->n)&, n, -1+16 ] Denominator[ 2^#/#!&/@Range[ 16 ] ])

cp's OEIS Frontend

A335063 a(n) = Sum_{k=0..n} (binomial(n,k) mod 2) * k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A101691 A modular binomial sum sequence.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A193494 Worst case of an unbalanced recursive algorithm over all n-node binary trees.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A333306 a(n) = sqrt(Pi/4)*2^A048881(2*n)*L(2*n) where L(s) = lim_{t->s} (t/2)!/((1-t)/2)!.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A348647 Irregular table read by rows; the n-th row contains the lengths of the runs of consecutive terms with the same parity in the n-th row of Pascal's triangle (A007318).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A355811 a(n) is the number at the apex of a triangle whose base contains the distinct powers of 2 summing to n (in ascending order), and each number in a higher row is the product of the two numbers directly below it; a(0) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A358138 Difference between maximum and minimum part in the n-th composition in standard order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A358330 By concatenating the standard compositions of each part of the a(n)-th standard composition, we get a weakly increasing sequence.

Views

Author

A333306 a(n) = sqrt(Pi/4)2^A048881(2n)L(2n) where L(s) = lim_{t->s} (t/2)!/((1-t)/2)!.