login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Middle column of the "Rule 37" elementary cellular automaton starting with a single ON (black) cell.
4

%I #31 Jul 01 2023 15:13:29

%S 1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,

%T 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,

%U 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0

%N Middle column of the "Rule 37" elementary cellular automaton starting with a single ON (black) cell.

%C Also the number of excursions of length n with Motzkin-steps forbidding all consecutive steps of length 2 except UD and DU. The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending on the x-axis and never crossing the x-axis, i.e., staying at nonnegative altitude. This sequence is periodic with a pre-period of length 2 (namely 1, 1) and a period of length 2 (namely 1, 0). It can be shown (via induction) that the middle column of rule 37 is eventually periodic, too. - _Valerie Roitner_, Apr 02 2020

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

%H Robert Price, <a href="/A266591/b266591.txt">Table of n, a(n) for n = 0..1000</a>

%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, preprint, 2019.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>

%H S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%H <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (0, 1).

%F G.f.: (1+t-t^3)/((1-t)*(1+t)). - _Valerie Roitner_, Jan 13 2020

%F A signed form of the sequence, starting 1, 1, 1, 0, -1, 0, 1, ..., is s(n) = signum([x^n] B(x)), where B(x) = x/(1 - exp(-x)) is the e.g.f. of the Bernoulli numbers with B(1) = 1/2. - _Peter Luschny_, Jan 23 2023

%e For n=2k we only have one allowed excursion, namely (UD)^k. For n=1, however, the excursion H is allowed (since we have not attained length two or more, no forbidden consecutive step sequence has appeared yet). - _Valerie Roitner_, Jan 13 2020

%t rule=37; rows=20; ca=CellularAutomaton[rule,{{1},0},rows-1,{All,All}]; (* Start with single black cell *) catri=Table[Take[ca[[k]],{rows-k+1,rows+k-1}],{k,1,rows}]; (* Truncated list of each row *) Table[catri[[k]][[k]],{k,1,rows}] (* Keep only middle cell from each row *)

%Y Cf. A059841, A266588.

%K nonn,easy,walk

%O 0

%A _Robert Price_, Jan 01 2016