A363345 a(n) is the eventual period of the n-th diagonal from the left of rule-30 1-D cellular automaton, when started from a single ON cell.

1, 1, 1, 2, 1, 2, 2, 1, 4, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 1, 8, 1, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 4, 8, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 4, 8, 8, 8, 8, 8

Offset

1,4

Comments

Diagonals from the left of rule-30 cellular automaton are eventually periodic, after an initial transient phase (A363346).

As noted by Wolfram (2002), "Each period doubling turns out to occur exactly when a diagonal in the pattern eventually becomes a white stripe, and the diagonal to its left has an odd number of black cells in each repeating block." See Rowland (2006), p. 256 for a proof of this observation.

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Michael Brunnbauer, Diagonals in elementary cellular automaton 30, 2019 (local PDF copy, with author's permission).

Eric S. Rowland, Local Nested Structure in Rule 30, Complex Systems 16 (2006), pp. 239-258.

Eric Weisstein's World of Mathematics, Rule 30.

Stephen Wolfram, Notes on Chapter 2, Rule 30, from A New Kind of Science Online, Wolfram Media, 2002.

Index entries for sequences related to cellular automata

Example

In the following diagram, showing the first 22 evolution steps of the CA, three diagonals are highlighted, along with their transient and periodic parts (the rest of the CA is represented by hyphens, for better visualization).
.
                              3rd diagonal
                           __ Transient = 1
                        - /   Repeat    = 0
                       --1    a(3)      = 1
                      --0--
                     --0----      12th diagonal
                    --0------  __ Transient = 01
                   --0--------/   Repeat    = 0010
                  --0--------0-   a(12)     = 4
                 --0--------1---
                --0--------0-----  __ 20th diagonal
               --0--------0-------/   Transient = 01000101
              --0--------1-------0-   Repeat    = 1100
             --0--------0-------1---  a(20)     = 4
            --0--------0-------0-----
           --0--------0-------0-------
          --0--------1-------0---------
         --0--------0-------1-----------
        --0--------0-------0-------------
       --0--------0-------1---------------
      --0--------1-------1-----------------
     --0--------0-------1-------------------
    --0--------0-------0---------------------
   --0--------0-------0-----------------------
  --0--------1-------1-------------------------
.

Mathematica

A363345list[nmax_]:=With[{ca=CellularAutomaton[86, {{1}, 0}, {{2nmax, 3nmax-1}, {nmax+1, 2nmax}}]}, Array[Length[FindRepeat[Diagonal[ca, nmax-#]]]&, nmax]]; A363345list[200] (* Modified by Paolo Xausa, Aug 15 2023 *)

Prog

(Python) # See Brunnbauer link, Appendix 3.

Crossrefs

Cf. A070950, A094605 (periods of diagonals from the right).

Cf. A363344 (diagonals), A363346 (lengths of transients), A364239 (indices of records), A364240.

Sequence in context: A337312 A077053 A373127 * A344651 A308558 A105272

Adjacent sequences: A363342 A363343 A363344 * A363346 A363347 A363348

Keyword

nonn

Author

Paolo Xausa, May 28 2023

Status

approved