A283642 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 678", based on the 5-celled von Neumann neighborhood.

1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, 178956971, 357913941, 715827883, 1431655765, 2863311531, 5726623061, 11453246123

Offset

0,2

Comments

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

Similar to A001045.

It is not difficult to prove that one has indeed a(n) = round(4*2^n/3) = A001045(n+2) for all n. The proof as well as the growth of the pattern is nearly identical to that of the toothpick sequence A139250. - M. F. Hasler, Feb 13 2020

The decimal representations of the n-th interval of elementary cellular automata rules 28 and 156 (see A266502 and A266508) generate this sequence. - Karl V. Keller, Jr., Sep 03 2021

Links

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

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

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

Index entries for linear recurrences with constant coefficients, signature (1,2).

Formula

From Colin Barker, Mar 14 2017: (Start)

G.f.: (1 + 2*x) / ((1 + x)*(1 - 2*x)).

a(n) = (2^(n+2) - 1) / 3 for n even.

a(n) = (2^(n+2) + 1) / 3 for n odd.

a(n) = a(n-1) + 2*a(n-2) for n>1.

(End)

I.e., a(n) = A001045(n+2) = A154917(n+2) = A167167(n+2) = |A077925(n+1)| = A328284(n+5) = round(4*2^n/3), cf. comments. - M. F. Hasler, Feb 13 2020

E.g.f.: (4*exp(2*x) - exp(-x))/3. - Stefano Spezia, Feb 13 2020

a(n) = floor((4*2^n + 1)/3). - Karl V. Keller, Jr., Sep 03 2021

Mathematica

CAStep[rule_, a_] := Map[rule[[10 - #]] &, ListConvolve[{{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}, a, 2], {2}];
code = 678; 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}]

Prog

(Python) print([(4*2**n + 1)//3 for n in range(50)]) # Karl V. Keller, Jr., Sep 03 2021

Crossrefs

Cf. A283641, A266502, A266508, A086893, A001045.

Sequence in context: A077925 A001045 A152046 * A284426 A284547 A084230

Adjacent sequences: A283639 A283640 A283641 * A283643 A283644 A283645

Keyword

nonn,easy

Author

Robert Price, Mar 12 2017

Status

approved