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

A189007 Number of ON cells after n generations of the 2D cellular automaton described in the comments.

Original entry on oeis.org

1, 4, 8, 16, 16, 32, 32, 64, 32, 64, 64, 128, 64, 128, 128, 256, 64, 128, 128, 256, 128, 256, 256, 512, 128, 256, 256, 512, 256, 512, 512, 1024, 128, 256, 256, 512, 256, 512, 512, 1024, 256, 512, 512, 1024, 512, 1024, 1024, 2048, 256, 512, 512, 1024, 512, 1024, 1024, 2048, 512, 1024, 1024, 2048, 1024, 2048, 2048, 4096, 256, 512, 512, 1024, 512

Offset: 1

John W. Layman, Apr 15 2011

nonn

The cells are the squares of the standard infinite square grid. All cells are initially OFF and a single cell is turned ON at generation 1. At subsequent generations a cell is ON if and only if exactly one East/West neighbor was ON or exactly one North/South neighbor was ON (or BOTH of those conditions) in the previous generation.
The equivalent Mathematica cellular automaton is obtained with neighborhood weights {{0,1,0},{3,0,3},{0,1,0}}, rule number 186, and initial configuration {{1}}.
Also sequence generated by Rule 84 with neighborhood weights {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}. - Robert Price, Mar 11 2016
Conjecture: a(1) = 1; a(n) = 2^A056791(n-1) for n > 1. - Michael De Vlieger, Nov 02 2022

Michael De Vlieger, Table of n, a(n) for n = 1..512
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. 32.
John W. Layman, Graphs of the automaton for generations 1-15

Cf. A164982, A165345, A245191.

ca = CellularAutomaton[{186, {2, {{0, 1, 0}, {3, 0, 3}, {0, 1, 0}}}, {1, 1}}, {{{1}}, 0}, 50-1, -50]; Table[Total[ca[[n]], 2], {n, 1, 50}]

It appears that this sequence is the limit of the following process.  Start with {1,4} and repeatedly perform this set of operations: (1) select the second half H of the sequence; (2) append twice the terms of H, then (3) append four times the terms of H.  This gives {1,4} -> {1,4,8,16} -> {1,4,8,16,16,32,32,64} -> {1,4,8,16,16,32,32,64,32,64,64,128,64,128,128,256} -> ...  This has been verified for the first 150 terms.
Comment from N. J. A. Sloane, Jul 21 2014: (Start)
It is not difficult to show that the preceding conjecture is correct. In fact one can give an explicit formula for the n-th term. At generation n >= 2, the configuration of ON cells consists of a set of concentric diamonds (see the illustration). The sizes of the diamonds are given by the (n-2)nd term of A245191. Let N = A245191(n-2) = Sum_{i>=0} b_i*2^i. Then the ON cells form a set of diamonds with edge-lengths i+2 for each b_i = 1. The i-th diamond contains 4*(i+1) ON cells, and the total number of ON cells is therefore a(n) = 4*Sum_i (i+1)*b_i. The b_i are given explicitly in A245191.
For example, if n=11, N = A245191(9) = 544 = 2^5 + 2^9, so b_5 = b_9 = 1, there are two diamonds, of side lengths 7 and 11, containing a total of 4*(6+10) = 64 = a(11) ON cells. (End)

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