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

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:

A292682 Rule 230: (000, ..., 111) -> (0, 1, 1, 0, 0, 1, 1, 1), without extending to the right of input bit 0.

Original entry on oeis.org

0, 3, 6, 5, 12, 15, 10, 11, 24, 27, 30, 29, 20, 23, 22, 23, 48, 51, 54, 53, 60, 63, 58, 59, 40, 43, 46, 45, 44, 47, 46, 47, 96, 99, 102, 101, 108, 111, 106, 107, 120, 123, 126, 125, 116, 119, 118, 119, 80, 83, 86, 85, 92, 95, 90, 91, 88, 91, 94, 93, 92, 95, 94, 95, 192, 195, 198, 197, 204, 207

Offset: 0

M. F. Hasler, Oct 09 2017

The orbit of 1 under this rule is A006977.

The substitution rules 000 -> 0 and 100 -> 0 ensure that no (even or odd) input value can ever extend / "propagate" to the right, therefore it is not required to consider the additional digit to the right of input bit 0 (i.e., the cell which would have this bit 0 as left neighbor), as one would usually do in the context of elementary cellular automata (cf., e.g., A292680 vs. A292681).

			     n        |         a(n)
   0 =   0[2] |      0[2] =  0
   1 =   1[2] |     11[2] =  3  (bits below 001 and 01(0) are on)
   2 =  10[2] |    110[2] =  6  (1 below 001 and 010, 0 below 10(0))
   3 =  11[2] |    101[2] =  5  (1 below 001 and 11(0), 0 below 011.)
   4 = 100[2] |   1100[2] = 12  (as n = 1 and n = 2, shifted left once more)
   5 = 101[2] |   1111[2] = 15  (1 below 001, 010 (twice) and 101)
   6 = 110[2] |   1010[2] = 10  (as n = 3, shifted left once)
   7 = 111[2] |   1011[2] = 11  (1 below 001, 111 and 11(0), 0 below 011).

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A006977, A292680, A292681, A266178, A266179, A266180, A019590.

apply( A292682(n,r=230)=sum(i=0,logint(!n+n<<=1,2)+1,bittest(r,bitand(n>>i,7))<

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A292682 Rule 230: (000, ..., 111) -> (0, 1, 1, 0, 0, 1, 1, 1), without extending to the right of input bit 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI