[seqfan] Re: confused about toothpick sequence A139250!

franktaw at netscape.net franktaw at netscape.net
Tue Apr 14 09:37:38 CEST 2009

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

The same behavior occurs with a simple linear automaton, where
a cell is turned on if it was off and has exactly one neighbor on,
and otherwise is off in the next generation.  (I think this is
A038183.)  This may be the purest exemplar of this phenomenon.

I would suggest looking at A038183 or the simple square grid with
each cell having 4 neighbors first; the "toothpick" grid is more
complex and correspondingly harder to get to grips with.

Franklin T. Adams-Watters

-----Original Message-----
From: Benoît Jubin <benoit.jubin at gmail.com>

There is something curious about this toothpick sequence A139250.  Its
sequence of first differences, A139251, is of course divisible by
four, giving A152978.  It is easy to prove (with a good offset) that
A152978(2^n+k) does not depe
nd on n if k<=2^(n-1), and the latter is
given by A152980, which has a similar property, with "limit sequence"
A153001, which again has a similar property (but this time, the limit
sequence doesn't seem to be in the OEIS).  This hints at a formula for
these sequences where the expression of n in base 2 plays a role
(although it seems that the "limit sequence" appears further and
I'm sorry but I have no time to check this further.  Maybe someone
will find something interesting in this direction.


On Mon, Apr 13, 2009 at 5:42 PM, Maximilian Hasler
<maximilian.hasler at gmail.com> wrote:
> On Mon, Apr 13, 2009 at 5:37 PM, N. J. A. Sloane 
<njas at research.att.com>
> > I was thinking the new toothpicks would have to touch the midpoints
> > of old toothpicks, not their endpoints (otherwise we could add 4
> > at the first step)
> I think this is correct.
> For me the values are reproducible. Below a PARI program which prints
> the following:
> 3807,3919,4059,4267,4523,4715,4783,4799,4827,4863,4903,
> p=Set(0); /* The set of "used" points.
 Points are written as complex
> numbers, c=x+iy.
> To avoid fractions, I take the toothpicks of length 2. */
> ne=[[1,1],[-1,-1]]; /* the [new] list of (exposed) endpoints. Exposed
> endpoints are listed as [c,d] where c=x+iy is the position of the
> endpoint, and d=a+ib is the direction. */
> print1("0,"cnt=1);
> {for(n=1,99,
>  ee=eval(Set(ne)); /* set of exposed endpoints [use set for sorting] 
>  /* remove those which actually are not exposed */
>  forstep( k=#ee, 2, -1, ee[k][1]==ee[k-1][1] | next;
> ee=vecextract(ee,Str("^",k-1,".."k)); k--);
>  print1(","cnt+=#ee);  /* for each exposed endpoint, a toothpick will
> be added in this move */
>  ne=Set(Mat(ee~)[,1]); /* discard directions */
>  p=setunion(p, ne);  /* add endpoints from last move to "used" points 
>  ne=[]; /* new (exposed) endpoints */
>  for( k=1, #ee,  /* add exposed endpoints of new toothpicks */ 
>    !setsearch(p, ep[1]+I*ep[2]) & 
>    !setsearch(p, ep[1]-I*ep[2]) & ne=concat(ne, 
> ) )}
> Maximilian
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/


Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list