A006978 -id:A006978 - cp's OEIS frontend

A038183 One-dimensional cellular automaton 'sigma-minus' (Rule 90): 000,001,010,011,100,101,110,111 -> 0,1,0,1,1,0,1,0.

1, 5, 17, 85, 257, 1285, 4369, 21845, 65537, 327685, 1114129, 5570645, 16843009, 84215045, 286331153, 1431655765, 4294967297, 21474836485, 73014444049, 365072220245, 1103806595329, 5519032976645, 18764712120593, 93823560602965, 281479271743489, 1407396358717445

Offset: 0

Antti Karttunen, Feb 09 1999

nonn

Generation n (starting from the generation 0: 1) interpreted as a binary number.
Observation: for n <= 15, a(n) = smallest number whose Euler totient is divisible by 4^n. This is not true for n = 16. - Arkadiusz Wesolowski, Jul 29 2012
Orbit of 1 under iteration of Rule 90 = A048725 = (n -> n XOR 4n). - M. F. Hasler, Oct 09 2017

			Successive states are:
          1
         101
        10001
       1010101
      100000001
     10100000101
    1000100010001
   101010101010101
  10000000000000001
  ...
which when converted from binary to decimal give the sequence. - _N. J. A. Sloane_, Jul 21 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..200
A. J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata..., Fig.9
Eric Weisstein's World of Mathematics, Rule 90
Wikipedia, Rule 90
Stephen Wolfram, Geometry of Binomial Coefficients, Amer. Math. Monthly, Volume 91, Number 9, November 1984, pages 566-571.
S. Wolfram, O. Martin, and A.M. Odlyzko, Algebraic Properties of Cellular Automata (1984), Communications in Mathematical Physics, 93 (March 1984) 219-258.
Index entries for sequences related to cellular automata

Cf. A006977, A006978, A038184, A038185 (other cellular automata), A000215 (Fermat numbers).
Also alternate terms of A001317. Cf. A048710, A048720, A048757 (same 0/1-patterns interpreted in Fibonacci number system).
Equals 4*A089893(n)+1.
For right half of triangle (excluding the middle bit) see A245191.
Cf. Sierpiński's gasket, A047999.

bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);
# A recursive, cellular automaton rule version:
sigmaminus := proc(n) option remember: if (0 = n) then (1)
else sum('((bit_n(sigmaminus(n-1),i)+bit_n(sigmaminus(n-1),i-2)) mod 2)*(2^i)', 'i'=0..(2*n)) fi: end:

r = 24; c = CellularAutomaton[90, {{1}, 0}, r - 1]; Table[FromDigits[c[[k, r - k + 1 ;; r + k - 1]], 2], {k, r}] (* Arkadiusz Wesolowski, Jun 09 2013 *)
a[ n_] := Sum[ 4^(n - k) Mod[Binomial[2 n, 2 k], 2], {k, 0, n}]; (* Michael Somos, Jun 30 2018 *)
a[ n_] := If[ n < 0, 0, Product[ BitGet[n, k] (2^(2^(k + 1))) + 1, {k, 0, n}]]; (* Michael Somos, Jun 30 2018 *)

vector(100,i,a=if(i>1,bitxor(a<<2,a),1)) \\ M. F. Hasler, Oct 09 2017

{a(n) = sum(k=0, n, binomial(2*n, 2*k)%2 * 4^(n-k))}; /* Michael Somos, Jun 30 2018 */

a=1
for n in range(55):
    print(a, end=",")
    a ^= a*4
# Alex Ratushnyak, May 04 2012

def A038183(n): return sum((bool(~(m:=n<<1)&m-k)^1)<Chai Wah Wu, May 02 2023

a(n) = Product_{i>=0} bit_n(n, i)*(2^(2^(i+1)))+1: A direct algebraic formula!
a(n) = Sum_{k=0..n} (C(2*n, 2*k) mod 2)*4^(n-k). - Paul Barry, Jan 03 2005
a(2*n+1) = 5*a(2n); a(n+1) = a(n) XOR 4*a(n) where XOR is binary exclusive OR operator. - Philippe Deléham, Jun 18 2005
a(n) = A001317(2n). - Alex Ratushnyak, May 04 2012

A038184 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, converted to a decimal number.

Original entry on oeis.org

1, 7, 21, 107, 273, 1911, 5189, 28123, 65793, 460551, 1381653, 7039851, 17829905, 124809335, 340873541, 1840690907, 4295032833, 30065229831, 90195689493, 459568513131, 1172543963409, 8207807743863, 22286925370437

Offset: 0

Antti Karttunen, Feb 15 1999

nonn

Generation n (starting from the generation 0: 1) interpreted as a binary number, but written in base 10.
Rows of the mod 2 trinomial triangle (A027907), interpreted as binary numbers: 1, 111, 10101, 1101011, ... (A118110). - Jacob A. Siehler, Aug 25 2006
See A071053 for number of ON cells. - N. J. A. Sloane, Jul 28 2014

			Bit patterns with "0" replaced by "." for visibilty [_Georg Fischer_, Dec 16 2021]:
  0:                    1
  1:                   111
  2:                  1.1.1
  3:                 11.1.11
  4:                1...1...1
  5:               111.111.111
  6:              1.1...1...1.1
  7:             11.11.111.11.11
  8:            1.......1.......1
  9:           111.....111.....111
  10:         1.1.1...1.1.1...1.1.1
  11:        11.1.11.11.1.11.11.1.11
  12:       1...1.......1.......1...1
  13:      111.111.....111.....111.111
  14:     1.1...1.1...1.1.1...1.1...1.1
  15:    11.11.11.11.11.1.11.11.11.11.11

Gheorghe Coserea, Table of n, a(n) for n = 0..200
Alan J. Macfarlane, On generating functions of some sequences of integers defined in the evolution of the cellular automaton Rule 150, Preprint 2016.
Eric Weisstein's World of Mathematics, Rule 150
Index entries for sequences related to cellular automata

Cf. A006977, A006978, A038183, A038185 (other cellular automata).
Cf. A048710, A048720, A027907, A001317, A071053.
This sequence, A071036 and A118110 are equivalent descriptions of the Rule 150 automaton.

bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);
sigmagen := proc(n) option remember: if (0 = n) then (1)
else sum('((bit_n(sigmagen(n-1),i)+bit_n(sigmagen(n-1),i-1)+bit_n(sigmagen(n-1),i-2)) mod 2)*(2^i)', 'i'=0..(2*n)) fi: end:

f[n_] := Sum[2^k*Coefficient[ #, x, k], {k, 0, 2n}] & @ Expand[(1 + x + x^2)^n, Modulus -> 2] (* Jacob A. Siehler, Aug 25 2006 *)

a(n) = subst(lift(Pol(Mod([1,1,1],2),'x)^n),'x,2);
vector(23,n,a(n-1))  \\ Gheorghe Coserea, Jun 12 2016

A161903 Convert n into a sequence of binary digits, apply one step of the rule 110 cellular automaton, and interpret the results as a binary integer.

Original entry on oeis.org

0, 3, 6, 7, 12, 15, 14, 13, 24, 27, 30, 31, 28, 31, 26, 25, 48, 51, 54, 55, 60, 63, 62, 61, 56, 59, 62, 63, 52, 55, 50, 49, 96, 99, 102, 103, 108, 111, 110, 109, 120, 123, 126, 127, 124, 127, 122, 121, 112, 115, 118, 119, 124, 127, 126, 125, 104, 107, 110, 111, 100, 103, 98, 97, 192, 195, 198, 199, 204, 207, 206, 205, 216, 219, 222, 223, 220, 223, 218, 217, 240, 243, 246, 247, 252, 255, 254, 253, 248, 251, 254, 255, 244, 247, 242, 241, 224, 227, 230, 231, 236

Offset: 0

Ben Branman, Jan 30 2011

a(a(a(...1))) (n times) gives A006978(n)

			For n=19, the evolution after one step is
0, 1, 0, 0, 1, 1  (n=19)
1, 1, 0, 1, 1, 1  (a(n)=55)
So a(n)=55.

T. D. Noe, Table of n, a(n) for n = 0..1023
Index entries for sequences related to cellular automata
Eric Weisstein's World of Mathematics, Rule 110
Wikipedia, Rule 110

Cf. A006978, A070887, A071049, A180001, A186083, A204371.

Cf. also A269160, A269174, A269175.

a[n_] :=
FromDigits[
  Drop[Part[CellularAutomaton[110, {IntegerDigits[n, 2], 0}], 1], -1],
   2];Table[a[n],{n,0,100}]

a(n) = A057889(A269174(A057889(n))). - Antti Karttunen, Jun 02 2018

A204371 Maximum period of cellular automaton rule 110 in a cyclic universe of width n.

Original entry on oeis.org

1, 1, 1, 2, 1, 9, 14, 16, 7, 25, 110, 18, 351, 91, 295, 32, 578, 81, 285, 240, 630, 462, 1058, 552, 300, 351, 567, 2156, 1044, 1770, 2759, 2368, 1100, 969, 3920, 1584

Offset: 1

Ben Branman, Jan 14 2012

a(n) >= A180001(n), and this sequence agrees with A180001 up to n=11.

			The 12 cell pattern
000100110111
001101111101
011111000111
110001001101
010011011111
110111110001
011100010011
110100110111
011101111100
110111000100
111101001101
000111011111
001101110001
011111010011
110001110111
010011011100
110111110100
111100011101
000100110111
Has period 18, which is the maximum possible, so a(12)=18

Eric Weisstein's World of Mathematics, Rule 110
Index entries for sequences related to cellular automata

Cf. A180001, A161903, A006978, A332717, A332718.

f[list_] := -Subtract @@ Flatten[Map[Position[#, #[[-1]]] &, NestWhileList[CellularAutomaton[110], list, Unequal, All], {0}]]; ma[n_] := Max[Table[f[IntegerDigits[i, 2, n]], {i, 0, 2^n - 1}]]; Table[ma[n], {n, 1, 10}]

a(19)-a(36) from Lars Blomberg, Dec 24 2015

A038185 One-dimensional cellular automaton 'sigma' (Rule 150).

Original entry on oeis.org

1, 3, 5, 13, 17, 59, 81, 219, 257, 899, 1349, 3437, 4353, 15235, 20805, 56173, 65537, 229379, 344069, 876557, 1118225, 3913787, 5313617, 14399195, 16842753, 58949635, 88424453, 225271821, 285282321

Offset: 0

Antti Karttunen, Feb 09 1999

nonn

Generation n (starting from the generation 0: 1) cut after the central 1-column and interpreted as a binary number.

Decimal 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 518", based on the 5-celled von Neumann neighborhood. Initialized with a single black (ON) cell at stage zero. - Robert Price, Feb 22 2017

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 to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata

Cf. A006977, A006978, A038183, a(n) = floor(A038184[ n ]/2^n)

bit_n := (x,n) -> `mod`(floor(x/(2^n)),2);
sigmacut := proc(n): if (0 = n) then (1)
else sum('((bit_n(sigmagen(n-1),i+1+n-1)+bit_n(sigmagen(n-1),i+n-1)+bit_n(sigmagen(n-1),i-1+n-1)) mod 2)*(2^i)', 'i'=0..(n)) fi: end:

A117999 Decimal number generated by the binary bits of the n-th generation of the Rule 110 elementary cellular automaton.

Original entry on oeis.org

1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, 1848320, 6879232, 32706560, 103702528, 485867520, 1799258112, 8569421824, 25897336832, 120686641152, 448682000384, 2137705676800, 6768178495488, 31718320898048, 118691479945216, 558749693509632

Offset: 0

Eric W. Weisstein, Apr 08 2006

			1;  1, 1, 0;  1, 1, 1, 0, 0;  1, 1, 0, 1, 0, 0, 0;  1, 1, 1, 1, 1, 0, 0, 0, 0; ...

Paolo Xausa, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Rule 110

Cf. A006978.

A117999list[nmax_]:=MapIndexed[FromDigits[ArrayPad[#1,#2-nmax-1],2]&,CellularAutomaton[110,{{1},0},{nmax,All}]];A117999list[25] (* Paolo Xausa, Oct 04 2023 *)

a(n) = A006978(n+1)*2^n. - Pontus von Brömssen, Oct 18 2022

cp's OEIS Frontend

A038183 One-dimensional cellular automaton 'sigma-minus' (Rule 90): 000,001,010,011,100,101,110,111 -> 0,1,0,1,1,0,1,0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A038184 State of one-dimensional cellular automaton 'sigma' (Rule 150): 000,001,010,011,100,101,110,111 -> 0,1,1,0,1,0,0,1 at generation n, converted to a decimal number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A161903 Convert n into a sequence of binary digits, apply one step of the rule 110 cellular automaton, and interpret the results as a binary integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A204371 Maximum period of cellular automaton rule 110 in a cyclic universe of width n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A038185 One-dimensional cellular automaton 'sigma' (Rule 150).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A117999 Decimal number generated by the binary bits of the n-th generation of the Rule 110 elementary cellular automaton.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula