Toothpick sequence from cellular automaton on square grid
=========================================================

From: Eric Rowland <erowland(AT)tulane.edu>
Date: Mon, 15 Mar 2010 16:12:36 -0500 (CDT)

Dear Neil,

I have been playing with the toothpick sequence a little, and I was 
interested in rendering the situation as an explicit cellular automaton, 
since I thought this might be a more natural representation in some ways. 
I don't know if anyone has already done this, but I didn't see one in the 
A139250 entry or in your paper with David Applegate and Omar Pol.  I came 
up with a 5-state cellular automaton where a cell depends on its 9 
neighbors on the previous step.

The states are 0, "-", "|", H, and V.  The symbols H and V represent 
midpoints of horizontal and vertical toothpicks, and "-" and "|" represent 
endpoinds of horizontal and vertical toothpicks (that can be overwritten 
by midpoints).

Unfortunately the update rule is a little large; I'll paste it below. 
But once you have the rule defined, the Mathematica code to count the 
total number of toothpicks in the first few rows is small:

Count[Flatten[#], V | H] & /@
  CellularAutomaton[toothpickrules, {{{"|"}, {V}, {"|"}}, 0}, 60]

This generates the following.

{1, 3, 7, 11, 15, 23, 35, 43, 47, 55, 67, 79, 95, 123, 155, \
171, 175, 183, 195, 207, 223, 251, 283, 303, 319, 347, 383, 423, 483, \
571, 651, 683, 687, 695, 707, 719, 735, 763, 795, 815, 831, 859, 895, \
935, 995, 1083, 1163, 1199, 1215, 1243, 1279, 1319, 1379, 1467, 1551, \
1607, 1667, 1759, 1871, 2011, 2219}


Unforunately I didn't find anything new with this representation.  I was 
surprised to find that the total number of nonzero cells on the nth step 
is already in the EIS as A147614:

Count[Flatten[#], Except[0]] & /@
  CellularAutomaton[toothpickrules, {{{"|"}, {V}, {"|"}}, 0}, 60]

{3, 7, 13, 19, 27, 39, 53, 63, 71, 83, 99, 119, 147, 183, 217, 235, \
243, 255, 271, 291, 319, 355, 391, 419, 447, 487, 539, 607, 699, 803, \
885, 919, 927, 939, 955, 975, 1003, 1039, 1075, 1103, 1131, 1171, \
1223, 1291, 1383, 1487, 1571, 1615, 1643, 1683, 1735, 1803, 1895, \
2003, 2103, 2187, 2283, 2415, 2587, 2815, 3103}


So maybe David has already looked at this cellular automaton.  I'd be 
interested to know if he was able to find one with fewer than 5 states. 
Either way, if you think it's interesting to add the Mathematica code to 
these entries, please do.  Maybe you have some standard place to upload 
files where you can put the definition of toothpickrules.

Eric


Here is the update rule:

Hpattern = 0 | "-" | H;
Vpattern = 0 | "|" | V;

toothpickrules = {
    {
      {_, _, Hpattern},
      {_, 0 | "|", "|"},
      {_, _, V}
    } -> "-",
    {
      {_, Hpattern, _},
      {Vpattern, "|", Vpattern},
      {_, V, _}
    } -> H,
    {
      {Hpattern, _, _},
      {"|", 0 | "|", _},
      {V, _, _}
    } -> "-",

    {
      {_, _, _},
      {_, 0 | "-", _},
      {Vpattern, "-", H}
    } -> "|",
    {
      {_, Hpattern, _},
      {Vpattern, "-", H},
      {_, Hpattern, _}
    } -> V,
    {
      {Vpattern, "-", H},
      {_, 0 | "-", _},
      {_, _, _}
    } -> "|",

    {
      {_, _, V},
      {_, 0 | "|", "|"},
      {_, _, Hpattern}
    } -> "-",
    {
      {_, V, _},
      {Vpattern, "|", Vpattern},
      {_, Hpattern, _}
    } -> H,
    {
      {V, _, _},
      {"|", 0 | "|", _},
      {Hpattern, _, _}
    } -> "-",

    {
      {_, _, _},
      {_, 0 | "-", _},
      {H, "-", Vpattern}
    } -> "|",
    {
      {_, Hpattern, _},
      {H, "-", Vpattern},
      {_, Hpattern, _}
    } -> V,
    {
      {H, "-", Vpattern},
      {_, 0 | "-", _},
      {_, _, _}
    } -> "|",

    {
      {_, _, _},
      {_, c_, _},
      {_, _, _}
    } :> c
    };


Partial reply from Neil Sloane:  As we describe in Section 10 of our paper,
it seems to us that the most natural way to construct the toothpick sequence
is as a cellular automaton on a directed graph, rather than
on the (undirected) square grid graph.
Then the rule is very simple: a cell turns ON iff exactly one
of its parent cells in ON.