[seqfan] Re: confused about toothpick sequence A139250!

[Richard Mathar]

ftaw> franktaw at netscape.net
ftaw> Tue Apr 14 09:37:38 CEST 2009
ftaw>
ftaw> There is something rather general going on here.  Take almost any --
ftaw> I'm not sure what to call it, the original term I learned was cellular
ftaw> space, but that seems to be used for something else these days;
ftaw> possibly grid; in any event, the kind of infinite graph that one runs
ftaw> a cellular automaton on; it needs to be at least two-dimensional --
ftaw> and start with a single cell in the on position.  At each step, each
ftaw> cell with exactly one neighbor on is turned on, and everything that
ftaw> is already on remains on.  You get this same pattern, where it shuts
ftaw> down to a bounded number of new cells on every 2^n steps.
ftaw> (You get some nice patterns that way, too.)
ftaw> <snibble>

I think this defines a total number of cells "on" as
1,5,9,21,25,37,49,85,89,101,113,149,161,197,233,341,345,357,369,...
if "neighbors" are those 4 cells that share a side (not those 8 that share
at least a point). If we label the generations of cells turned on by 
consecutive numbers we get a rosetta cell pattern

                3
               323
              3 1 3
             3210123
              3 1 3
               323
                3

In the first generation, only the central "0" is on, a(1)=1. In the next
generation, we turn on four "1", leading to a(2)=a(1)+4=5. In the third generation,
four "2" are turned on, a(3)=a(2)+4=9. In the fourth generation, each
of the four wings allows three 3's to be turned on, a(4)=a(3)+4*3=21.

# [x,y] coordinates of cells on
Lse := [[0,0]] ;
# enclosing rectangle of the cells on (that is, minima and maxima in Lse)
xmin := 0 ;
xmax := 0 ;
ymin := 0 ;
ymax := 0 ;

# count neighbors of x,y which are on; return 0 if [x,y] is in L
cntnei := proc(x,y,L)
	local a,p,xpt,ypt;
        a := 0 ;
        if not [x,y] in L then
        for p in Lse do
                xpt := op(1,p) ;
                ypt := op(2,p) ;
                if ( abs(xpt-x) = 1 and ypt=y ) or ( x=xpt and abs(ypt-y) = 1) then
                        a := a+1 ;
                fi;
        od:
        fi:
        RETURN(a) ;
end:

# loop over generations/steps
for stp from 1 to 10 do
        Lnew := [] ;
        for x from xmin-1 to xmax+1 do
        for y from ymin-1 to ymax+1 do
                if cntnei(x,y,Lse) = 1 then
                        Lnew := [op(Lnew),[x,y]] ;
                fi;
        od:
        od:
        for p in Lnew do
                xpt := op(1,p) ;
                ypt := op(2,p) ;
                xmin := min(xmin,xpt) ;
                xmax := max(xmax,xpt) ;
                ymin := min(ymin,ypt) ;
                ymax := max(ymax,ypt) ;
        od:
        Lse := [op(Lse),op(Lnew)] ;
        print(nops(Lse)) ;
od: