# [seqfan] Re: confused about toothpick sequence A139250!

Richard Mathar mathar at strw.leidenuniv.nl
Thu Apr 16 17:54:31 CEST 2009

```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:

```