[seqfan] Re: confused about toothpick sequence A139250!

[Maximilian Hasler]

On Wed, Apr 15, 2009 at 4:05 PM, N. J. A. Sloane wrote:
> There were several responses to my request for a precise definition
> of A139520, but none of them really satisfied me.

Two days ago I sent you the message included below which contains
among others the comment: (essentially the same as Rob Pratt's
interpretation, except for placing not only one toothpick per step).


%C A139250 General rule: An ending point of a toothpick is said
"exposed" if it does not touch any other toothpick. At each step, a
new toothpick is added to each exposed ending point, as to form (the
bar of) a T with the "old" toothpick (which will be the stem of the
T).


I don't think that this leaves any ambiguity. I think there is no
doubt that "[the endpoint] does not touch any other..." gives exactly
4 exposed points after the 3rd step. This is confirmed by the
following:


%C A139250 After 2^k-1 steps, there are 2^k exposed endpoints, all
located on two lines perpendicular to the [direction of the] initial
toothpick. During the following step the 2^k toothpicks are laid on
these lines, and only 4 exposed endpoints remain, located at the
corners of a square with side length 2^(k-1) times the length of a
toothpick.


By the way, one can show that

 a(2^k) = (2^(2k+1)+1)/3
 a(2^k+4) = (2^(2k+1)+13)/3

and if I had a little more time I could give a formula for efficient
calculation of a(n) in log2(n) steps.
(I think the sequence is what Jeffrey Shallit and Jean-Paul Allouche
called k-regular.)

Maximilian


---------- Forwarded message ----------
From: The On-Line Encyclopedia of Integer Sequences <oeis at research.att.com>
Date: Tue, Apr 14, 2009 at 2:29 AM
Subject: COMMENT FROM submitA M. F. Hasler A139250
To: njas at research.att.com
Cc: MHasler at univ-ag.fr


The following is a copy of the email message that was sent to njas
containing the comment you submitted.

All greater than and less than signs have been replaced by their html
equivalents.  They will be changed back when the message is processed.

This copy is just for your records.  No reply is expected.

%S A139250 0,1,3,7,11,15,23,35,43,47,55,67,79,95,123,155,171,175,183,195,207,223,
%T A139250 251,283,303,319,347,383,423,483,571,651,683,687,695,707,719,735,763,
%U A139250 795,815,831,859,895,935,995,1083,1163,1199,1215,1243,1279,1319,1379
%E A139250 Verified and extended using the given PARI code by M. F.
Hasler (MHasler(AT)univ-ag.fr), Apr 14 2009
%C A139250 Contribution from M. F. Hasler (MHasler(AT)univ-ag.fr), Apr
14 2009: (Start)
%C A139250 General rule: An ending point of a toothpick is said
"exposed" if it does not touch any other toothpick. At each step, a
new toothpick is added to each exposed ending point, as to form (the
bar of) a T with the "old" toothpick (which will be the stem of the
T).
%C A139250 Since the value of a(1) cannot be produced from the initial
value a(0)=0 (using the general rule), the sequence might as well be
defined to start with a(1).
%C A139250 After 2^k-1 steps, there are 2^k exposed endpoints, all
located on two lines perpendicular to the initial toothpick. During
the following step the 2^k toothpicks are laid on these lines, and
only 4 exposed endpoints remain, located at the corners of a square
with side length 2^(k-1) times the length of a toothpick. (End)
%o A139250 Contribution from M. F. Hasler (MHasler(AT)univ-ag.fr), Apr
14 2009: (Start)
%o A139250 (PARI) A139250(n,print_all=0)={my(p=[] /* set of "used"
points. Points are written as complex numbers, c=x+iy. Toothpicks are
of length 2 */,
%o A139250 ee=[[0,1]] /* list of (exposed) endpoints. Exposed
endpoints are listed as [c,d] where c=x+iy is the position of the
endpoint, and d (unimodular) is the direction */
%o A139250 c,d,ne, cnt=1); print_all & print1("0,1"); n<2 & return(n);
%o A139250 for(i=2,n, p=setunion(p, Set(Mat(ee~)[,1])); /* add
endpoints (discard directions) from last move to "used" points */
%o A139250 ne=[]; /* new (exposed) endpoints */
%o A139250 for( k=1, #ee, /* add endpoints of new toothpicks if not
among the used points */
%o A139250 setsearch(p, c=ee[k][1]+d=ee[k][2]*I) |
ne=setunion(ne,Set([[c,d]]));\\
%o A139250 setsearch(p, c-2*d) | ne=setunion(ne,Set([[c-2*d,-d]]));
%o A139250 ); /* useing Set() we have the points sorted, so it's easy
to remove those which finally are not exposed because they touch a new
toothpick */
%o A139250 forstep( k=#ee=eval(ne), 2, -1, ee[k][1]==ee[k-1][1] & k--
& ee=vecextract(ee,Str("^"k"..",k+1)));
%o A139250 cnt+=#ee; /* each exposed endpoint will give a new
toothpick */ print_all & print1(","cnt));cnt} (End)