A101622 -id:A101622 - cp's OEIS frontend

A084639 Expansion of x(1+2x)/((1+x)(1-x)(1-2*x)).

0, 1, 4, 9, 20, 41, 84, 169, 340, 681, 1364, 2729, 5460, 10921, 21844, 43689, 87380, 174761, 349524, 699049, 1398100, 2796201, 5592404, 11184809, 22369620, 44739241, 89478484, 178956969, 357913940, 715827881, 1431655764, 2863311529, 5726623060, 11453246121

Offset: 0

Paul Barry, Jun 06 2003

Original name was: Generalized Jacobsthal numbers.
This is the sequence A(0,1;1,2;3) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
Entries correspond to value bound adjustment for an N-bit string having M bits set and a(n+1) bit transitions. Wolfram Alpha can easily generate an entry. a(5)=41 stems from input as 1111110_2 - 1010101_2. The subtraction pattern alternates (begins at 1), and bit count is ptr+2 both terms, with the lead term having only its LSB clear. - Bill McEachen, Jul 15 2011
Also a(n) = 2*A000975(n) if n even, a(n) = 2*A000975(n) - 1 if n odd. - Michel Lagneau, Jan 11 2012
In the above comment by Bill McEachen the binary pattern (in an obvious notation) is for even n 1^(n+1)0 - (10)^((n+2)/2) and for odd n 1^(n+1)0 - (10)^((n+1)/2)1. That is for even n a(n) = sum(2^k, k=1..(n+1)) - sum(2^(2*k-1), k=1..(n+2)/2)  = (2^(n+2) - 4)/3, and for odd n a(n) = sum(2^k , k=1..(n+1)) - sum(2^(2*k), k=0..(n+1)/2) = (2^(n+2) - 5)/3. This checks with the formula a(n) = (2^(n+3) + (-1)^n - 9)/6 given below. After a correspondence with Bill McEachen. - Wolfdieter Lang, Jan 24 2014
Michel Lagneau's comment above is equal to the fact that a(n) = A000975(n)-1, or in other words, this sequence gives the partial sums of Jacobsthal sequence, starting from its second 1, A001045(2). From this also follows that this sequence gives the positions of repunits in "Jacobsthal greedy base", A265747. - Antti Karttunen, Dec 17 2015
From Kensuke Matsuoka, Aug 11 2020: (Start)
This sequence is the sum of diagonally arranged powers of 2 repeated in an L shape. For example, a(1)=1, a(2) = 4, a(3)=9, a(4)= 20, a(5)=41, a(6)=84 are obtained from the figure below.
  32
  16  8
   8  4  2
   4  2  1  2
   2  1  2  4  8
   1  2  4  8 16 32
From this figure, a(n) = a(n-2) + 2^n is obtained. (End)
For n > 0, also the total distance that the disks travel from the leftmost peg to the middle peg in the Tower of Hanoi puzzle, in the unique solution with 2^n - 1 moves (see links). - Sela Fried, Dec 17 2023

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Sela Fried, Economically solving the Tower of Hanoi puzzle.
A. F. Horadam, Jacobsthal Representation Numbers, Fib Quart. 34, 40-54, 1996.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
El-Mehdi Mehiri, Saad Mneimneh, and Hacène Belbachir, The Towers of Fibonacci, Lucas, Pell, and Jacobsthal, arXiv:2502.11045 [math.CO], 2025. See p. 12.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A000975, A000225, A001045.

Cf. A265747.

[2^(n+2)/3+(-1)^n/6-3/2: n in [0..35]]; // Vincenzo Librandi, Aug 08 2011

a:=proc(n) (2^(n+3) + (-1)^n - 9)/6 end proc: [seq(a(n), n=0..33)]; # Wolfdieter Lang, Jan 24 2014

a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n - 1] + 2 a[n - 2] + 3; Array[a, 32, 0] (* Or *)
a[0] = 0; a[1] = 1; a[n_] := a[n] = 3 a[n - 1] - 2 a[n - 2] + (-1)^n; Array[a, 32, 0]
CoefficientList[Series[x*(1+2*x)/((1+x)*(1-x)*(1-2*x)),{x,0,40}],x] (* or *) LinearRecurrence[{2,1,-2},{0,1,4},40]  (* Vladimir Joseph Stephan Orlovsky, Jan 30 2012 *)

a(n)=2^(n+2)/3-if(n%2,5,4)/3 \\ Charles R Greathouse IV, Aug 08 2011

concat(0, Vec(x*(1+2*x)/((1+x)*(1-x)*(1-2*x)) + O(x^100))) \\ Altug Alkan, Dec 17 2015

def A084639(n): return (4<Chai Wah Wu, Apr 25 2025

G.f.: x*(1+2*x)/((1+x)*(1-x)*(1-2*x)).
E.g.f.: 4*exp(2*x)/3-3*exp(x)/2+exp(-x)/6.
a(n) = a(n-1)+2*a(n-2)+3, a(0)=0, a(1)=1.
a(n) = 2^(n+2)/3+(-1)^n/6-3/2.
a(n) = A001045(n+2) - A000034(n).
a(n) = 5*a(n-2)-4*a(n-4). Cf. A084640, A101622. - Paul Curtz, Apr 03 2008
a(n) = 2*a(n-1) + a(n-2) -2*a(n-3). - R. J. Mathar, Jun 28 2010
a(n) = a(n-1)+2*a(n-2)+3, n>1. - Gary Detlefs, Dec 19 2010
a(n) = 3*a(n-1)-2*a(n-2) +(-1)^n, n>1. - Gary Detlefs, Dec 19 2010
a(n) = a(n-2) + 2^n for n >= 2. - Kensuke Matsuoka, Aug 11 2020

Replaced duplicate of a formula by another recurrence - R. J. Mathar, Jun 28 2010

A049332 Number of conjugacy classes in Clifford group CL(n).

Original entry on oeis.org

2, 4, 5, 10, 17, 34, 65, 130, 257, 514, 1025, 2050, 4097, 8194, 16385, 32770, 65537, 131074, 262145, 524290, 1048577, 2097154, 4194305, 8388610, 16777217, 33554434, 67108865, 134217730, 268435457, 536870914, 1073741825, 2147483650

Offset: 0

N. J. A. Sloane

Floretion Algebra Multiplication Program, FAMP Code: 4tesforseq[ (- .25'i - .25i' - .25'ii' + .25'jj' + .25'kk' + .25'jk' + .25'kj' - .25e)*( + .5'i + .5i' + .5'ii' + .5'jk' + .5'kj' + .5e ) ], 1vesforseq = (1,1,1,1,1,1,1). (Dement)

B. Simon, Representations of Finite and Compact Groups, Amer. Math. Soc., 1996, p. 69.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A101622, A014551 (first differences)

[(3/2-(-1)^n/2+2^n): n in [0..40]]; // Vincenzo Librandi, Apr 27 2012

A049332 := proc(n) if n mod 2 = 0 then 2^n+1 else 2^n+2; fi; end;

CoefficientList[Series[(2-5*x^2)/((1-x)*(1+x)*(1-2*x)),{x,0,40}],x] (* Vincenzo Librandi, Apr 27 2012 *)
Table[2^n + Mod[n, 2] + 1, {n, 0, 31}] (* Jean-François Alcover, Feb 11 2014 *)
LinearRecurrence[{2,1,-2},{2,4,5},40] (* Harvey P. Dale, Nov 29 2014 *)

a(n) = 3/2 - (-1)^n/2 + 2^n \\ Charles R Greathouse IV, Feb 10 2017

a(n+2) - A101622(n+1) = 4. - Creighton Dement, Mar 07 2005
From Colin Barker, Apr 18 2012: (Start)
a(n) = (3/2 - (-1)^n/2 + 2^n).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
G.f.: (2-5*x^2)/((1-x)*(1+x)*(1-2*x)). (End)
E.g.f.: cosh(x) + cosh(2*x) + 2*sinh(x) + sinh(2*x). - Stefano Spezia, May 27 2022
a(n) = 2*A000975(n+1) -5*A000975(n-1). - R. J. Mathar, Oct 12 2022

A284483 Binary representation of the x-axis, from the left edge to the origin, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 0, 111, 1101, 11110, 111101, 1111110, 11111101, 111111110, 1111111101, 11111111110, 111111111101, 1111111111110, 11111111111101, 111111111111110, 1111111111111101, 11111111111111110, 111111111111111101, 1111111111111111110, 11111111111111111101

Offset: 0

Robert Price, Mar 27 2017

Initialized with a single black (ON) cell at stage zero.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..126
Robert Price, Diagrams of first 20 stages
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

Cf. A284484, A101622, A284485.

CAStep[rule_, a_] := Map[rule[[10 - #]] &, ListConvolve[{{0, 2, 0},{2, 1, 2}, {0, 2, 0}}, a, 2],{2}];
code = 961; stages = 128;
rule = IntegerDigits[code, 2, 10];
g = 2 * stages + 1; (* Maximum size of grid *)
a = PadLeft[{{1}}, {g, g}, 0,Floor[{g, g}/2]]; (* Initial ON cell on grid *)
ca = a;
ca = Table[ca = CAStep[rule, ca], {n, 1, stages + 1}];
PrependTo[ca, a];
(* Trim full grid to reflect growth by one cell at each stage *)
k = (Length[ca[[1]]] + 1)/2;
ca = Table[Table[Part[ca[[n]] [[j]],Range[k + 1 - n, k - 1 + n]], {j, k + 1 - n, k - 1 + n}], {n, 1, k}];
Table[FromDigits[Part[ca[[i]] [[i]], Range[1, i]], 10], {i, 1, stages - 1}]

Conjectures from Colin Barker, Mar 28 2017: (Start)
G.f.: (1 - 10*x + 110*x^2 + x^3 - 11*x^4 + 10*x^5) / ((1 - x)*(1 + x)*(1 - 10*x)).
a(n) = (10^(n+1) - 10)/9 for n>2 and even.
a(n) = (10^(n+1) - 91)/9 for n>2 and odd.
a(n) = 10*a(n-1) + a(n-2) - 10*a(n-3) for n>5.
(End)

A284484 Binary representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 0, 111, 1011, 1111, 101111, 111111, 10111111, 11111111, 1011111111, 1111111111, 101111111111, 111111111111, 10111111111111, 11111111111111, 1011111111111111, 1111111111111111, 101111111111111111, 111111111111111111, 10111111111111111111

Offset: 0

Robert Price, Mar 27 2017

Initialized with a single black (ON) cell at stage zero.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..126
Robert Price, Diagrams of first 20 stages
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata

Cf. A284483, A101622, A284485.

CAStep[rule_, a_] := Map[rule[[10 - #]] &, ListConvolve[{{0, 2, 0},{2, 1, 2}, {0, 2, 0}}, a, 2],{2}];
code = 961; stages = 128;
rule = IntegerDigits[code, 2, 10];
g = 2 * stages + 1; (* Maximum size of grid *)
a = PadLeft[{{1}}, {g, g}, 0,Floor[{g, g}/2]]; (* Initial ON cell on grid *)
ca = a;
ca = Table[ca = CAStep[rule, ca], {n, 1, stages + 1}];
PrependTo[ca, a];
(* Trim full grid to reflect growth by one cell at each stage *)
k = (Length[ca[[1]]] + 1)/2;
ca = Table[Table[Part[ca[[n]] [[j]],Range[k + 1 - n, k - 1 + n]], {j, k + 1 - n, k - 1 + n}], {n, 1, k}];
Table[FromDigits[Part[ca[[i]] [[i]], Range[i, 2 * i - 1]], 10], {i, 1, stages - 1}]

Conjectures from Colin Barker, Mar 28 2017: (Start)
G.f.: (1 - x + 11*x^2 + 1000*x^3 - 11000*x^4 + 10000*x^5) / ((1 - x)*(1 - 10*x)*(1 + 10*x)).
a(n) = (-20 - 81*(-10)^n + 101*10^n)/180 for n>2.
a(n) = a(n-1) + 100*a(n-2) - 100*a(n-3) for n>5.
(End)

A284485 Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood.

Original entry on oeis.org

1, 0, 7, 11, 15, 47, 63, 191, 255, 767, 1023, 3071, 4095, 12287, 16383, 49151, 65535, 196607, 262143, 786431, 1048575, 3145727, 4194303, 12582911, 16777215, 50331647, 67108863, 201326591, 268435455, 805306367, 1073741823, 3221225471, 4294967295, 12884901887

Offset: 0

Robert Price, Mar 27 2017

Initialized with a single black (ON) cell at stage zero.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

Robert Price, Table of n, a(n) for n = 0..126
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Robert Price, Diagrams of first 20 stages

Cf. A284483, A284484, A101622.

CAStep[rule_, a_] := Map[rule[[10 - #]] &, ListConvolve[{{0, 2, 0},{2, 1, 2}, {0, 2, 0}}, a, 2],{2}];
code = 961; stages = 128;
rule = IntegerDigits[code, 2, 10];
g = 2 * stages + 1; (* Maximum size of grid *)
a = PadLeft[{{1}}, {g, g}, 0,Floor[{g, g}/2]]; (* Initial ON cell on grid *)
ca = a;
ca = Table[ca = CAStep[rule, ca], {n, 1, stages + 1}];
PrependTo[ca, a];
(* Trim full grid to reflect growth by one cell at each stage *)
k = (Length[ca[[1]]] + 1)/2;
ca = Table[Table[Part[ca[[n]] [[j]],Range[k + 1 - n, k - 1 + n]], {j, k + 1 - n, k - 1 + n}], {n, 1, k}];
Table[FromDigits[Part[ca[[i]] [[i]], Range[i, 2 * i - 1]], 2], {i ,1, stages - 1}]

Conjectures from Colin Barker, Mar 28 2017: (Start)
G.f.: (1 - x + 3*x^2 + 8*x^3 - 24*x^4 + 16*x^5) / ((1 - x)*(1 - 2*x)*(1 + 2*x)).
a(n) = (-4 - (-2)^n + 5*2^n)/4 for n>2.
a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3) for n>5.
(End)

A131953 A130321 + A059268 - A000012(signed).

Original entry on oeis.org

1, 4, 2, 4, 5, 4, 10, 5, 7, 8, 16, 11, 7, 11, 16, 34, 17, 13, 11, 19, 32, 64, 35, 19, 17, 19, 35, 64, 130, 65, 37, 23, 25, 35, 67, 128, 256, 131, 67, 41, 31, 41, 67, 131, 256, 514, 257, 133, 71, 49, 47, 73, 131, 259, 512

Offset: 0

Gary W. Adamson, Jul 30 2007

Row sums = A101622 starting (1, 6, 13, 30, 61, 126, ...).

			First few rows of the triangle:
   1;
   4,  2;
   4,  5,  4;
  10,  5,  7,  8;
  16, 11,  7, 11, 16;
  34, 17, 13, 11, 19, 32;
  64, 35, 19, 17, 19, 35, 64;
  ...

Cf. A130321, A059268, A101622.

A130321 + A059268 - A000012 (signed + - + -, ... by columns) as infinite lower triangular matrices.

A167193 a(n) = (1/3)(1 - (-2)^n + 3(-1)^n ) = (-1)^(n+1)*A167030(n).

Original entry on oeis.org

1, 0, 0, 2, -4, 10, -20, 42, -84, 170, -340, 682, -1364, 2730, -5460, 10922, -21844, 43690, -87380, 174762, -349524, 699050, -1398100, 2796202, -5592404, 11184810, -22369620, 44739242, -89478484, 178956970, -357913940, 715827882, -1431655764, 2863311530, -5726623060, 11453246122, -22906492244, 45812984490

Offset: 0

Paul Curtz, Oct 30 2009

This is the inverse binomial transform of 1, 1, 1, 3, 5, 11,.. (continued as in A001045 and conjectured to be equal to A152046).

Any sequence (like this one) which obeys a(n)= -2a(n-1)+a(n-2)+2a(n-3) also obeys a(n)=5a(n-2)-4a(n-4), proved by telescoping; see A101622.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (-2,1,2).

[( 1-(-1)^n*2^n)/3+(-1)^n: n in [0..40] ]; // Vincenzo Librandi, Aug 06 2011

LinearRecurrence[{-2,1,2},{1,0,0}, 25] (* or *) Table[(1/3)*(1 + 3*(-1)^n - (-2)^n), {n,0,25}] (* G. C. Greubel, Jun 04 2016 *)

a(2n) = (-1)^n* A084240(n). a(2n+1) = A020988(n).
G.f.: ( -1 - 2*x + x^2 ) / ( (x-1)*(1+2*x)*(1+x) ).
a(n) = -a(n-1) + 2*a(n-2) - 2*(-1)^n.
a(n) = -2*a(n-1) + a(n-2) + 2*a(n-3).
E.g.f.: (1/3)*(exp(x) + 3*exp(-x) - exp(-2*x)). - G. C. Greubel, Jun 04 2016

cp's OEIS Frontend

A084639 Expansion of x*(1+2*x)/((1+x)*(1-x)*(1-2*x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A049332 Number of conjugacy classes in Clifford group CL(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A284483 Binary representation of the x-axis, from the left edge to the origin, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A284484 Binary representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A284485 Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 961", based on the 5-celled von Neumann neighborhood.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A131953 A130321 + A059268 - A000012(signed).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A167193 a(n) = (1/3)*(1 - (-2)^n + 3*(-1)^n ) = (-1)^(n+1)*A167030(n).

Views

Author

Keywords

Comments

Links

Programs

Magma

A084639 Expansion of x(1+2x)/((1+x)(1-x)(1-2*x)).

A167193 a(n) = (1/3)(1 - (-2)^n + 3(-1)^n ) = (-1)^(n+1)*A167030(n).