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

Author

Robert Price, Mar 12 2017

Keywords

• nonn
• easy

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).

Crossrefs

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

Programs

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}]

Python

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

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