Math::PlanePath::ToothpickTree -- toothpick pattern by growth levels
use Math::PlanePath::ToothpickTree; my $path = Math::PlanePath::ToothpickTree->new; my ($x, $y) = $path->n_to_xy (123);
This is the "toothpick" sequence expanding through the plane by non-overlapping line segments, as per
David Applegate, Omar E. Pol, N.J.A. Sloane, "The Toothpick Sequence and Other Sequences from Cellular Automata", Congressus Numerantium, volume 206 (2010), 157-191,
http://www.research.att.com/~njas/doc/tooth.pdf
Points are numbered by growth levels and anti-clockwise around within the level.
--49-- --48-- 5 | | 44--38-- --37-- --36-- --35--43 4 | | | | | | --50- 27--17--26 25--16--24 -47-- 3 | | | | 12---8-- ---7--11 2 | | | | | | 28--18- 4---1---3 -15--23 1 | | | | | 0 <- Y=0 | | | | | 29--19- 5---2---6 -22--34 -1 | | | | | | 13---9-- --10--14 -2 | | | | --51- 30--20--31 32--21--33 -54-- -3 | | | | | | 45--39-- --40-- --41-- --42--46 -4 | | --52-- --53-- -5 ^ -4 -3 -2 -1 X=0 1 2 3 4
Each X,Y point is the centre of a toothpick of length 2. The first toothpick is vertical at the origin X=0,Y=0.
A toothpick is added at each exposed end and perpendicular to that end. So N=1 and N=2=3 are added to the ends of the initial N=0 toothpick. Then points N=4,5,6,7 are added at the four ends of those two.
---8--- ---7--- | | | | ---1--- 4---1---3 4---1---3 | | | | | | | | 0 -> 0 -> 0 -> 0 | | | | | | | | ---2--- 5---2---6 5---2---6 | | | | ---9--- --10---
Toothpicks are not added if they would overlap, which means no toothpick where the ends of N=3,N=6 and N=4,N=5 meet, at X=1,Y=0 and X=-1,Y=0 respectively.
The end of a toothpick can touch an existing toothpick. The first time this happens is N=15 where its left end touches N=3.
The way each toothpick is perpendicular to the previous means that at even depth the toothpicks are vertical and odd depth they're horizontal (treating the initial N=0 as depth=0). It also means that "even" points X==Y mod 2 are vertical and "odd" points X!=Y mod 2 are horizontal.
See Math::PlanePath::ToothpickReplicate for a digit-based replication instead of by growth levels..
Within each quadrant the pattern repeats in blocks of a power-of-2 size, with an extra two toothpicks "A" and "B" in the middle.
| |------------+------------A | | | | block 3 block 2 | in each quadrant | mirror same | | ^ ^ | | \ --B-- / | | \ | / | |---------- A ---+ | | | | block 0 block 1 | | ^ | \ rot +90 | | / | \ | | / | v | +----------------------------
Toothpick "A" is at a power-of-2 X=2^k,Y=2^k and toothpick "B" is above it. The B toothpick leading to blocks 2 and 3 mean that they're one level behind block 1 in the replication.
In the portion shown above the first quadrant N=3,N=7 is block 0 and those two repeat as N=15,N=23 block 1, and N=24,N=35 block 2, and N=25,36 block 3. The rotation for block 1 can be seen. The mirroring for block 3 can be seen at the next level, as for instance in the "One Quadrant" form below.
The initial N=3,N=7 can be thought of as an "A,B" middle pair with empty blocks before and surrounding.
Each "A" toothpick is at a power-of-2 position,
"A" toothpick ------------- X=2^k, Y=2^k depth = 4^k counting from depth=0 at the origin N = (8*4^k + 1)/3 N=3,11,43, etc = base4 222...22
The N=222..223 in base4 arises from the replication described above. Each replication is 4*N+2 of the previous, except for the initial N=0,1,2.
The "A" toothpick coming out of corner of block 2 is the only growth from a depth=4^k level. The sides of blocks 1 and 2 and blocks 2 and 3 have all endpoints meeting and so stop by the no-overlap rule, as can be seen for example N=35,36,37,38 across the top above.
The number of points visited approaches 2/3 of the plane, as can be seen by the "A" points count as a fraction of the area (positive and negative),
N of "A" (8*4^k + 1)/3 8/3 * 4^k -------- = ------------- -> --------- = 2/3 Area X*Y (2*2^k)*(2*2^k) 4 * 4^k
Option parts => 1 confines the pattern to the first quadrant, starting from N=0 at X=1,Y=1 which is the first toothpick wholly within that first quadrant. This is a single copy of the repeating part in each of the four quadrants of the full pattern.
parts => 1
parts => 1 ... ... | | | | 47--44--46 | | | 8 | --41-- --40-- --29-- --38--42 | | | | | | | 7 | 36--28--35 34--27--33 -43--45 | | | | | | 6 | --22--18- -17--21 ... | | | | | | 5 | --37--29- 15--12--14 -26--32 | | | | 4 | ---9--- ---8--10 | | | | | | 3 | 7---4---6 -11--13 -25--31 | | | | | | 2 | ---1---2 19--16--20 | | | | | | | 1 | 0 --3---5 23 --24--30 | | | | Y=0 | +---------------------------------- X=0 1 2 3 4 5 6 7 8
The "A" toothpick at X=2^k,Y=2^k is
N of "A" = (2*4^k - 2)/3 N=2,10,42,etc = 222...222 in base 4
Because the repeating part starts from N=0, so there's no initial centre toothpicks like the full pattern, the repetition is a plain 4*N+2 and hence a 222..222 in base 4.
Option parts => 2 confines the tree to the upper half plane Y>=1, giving two symmetric parts above the X axis. N=0 at X=0,Y=1 is the first toothpick of the full pattern which is wholly within this half plane.
parts => 2
Y>=1
parts => 2 ... ... 5 | | 22--20-- --19-- --18-- --17--21 4 | | | | | | ... 15---9--14 13---8--12 ... 3 | | | | 6---4-- ---3---5 2 | | | | | | 16--10- 2---0---1 --7--11 1 | | | | <- Y=0 ----------------------------------- ^ -4 -3 -2 -1 X=0 1 2 3 4
Option parts => 3 is the three replications which occur from an X=2^k,Y=2^k point, but continued on indefinitely confined to the upper and right three quadrants.
parts => 3
parts => 3 ..--32-- --31-- --30-- --29--.. 4 | | | | 26--18--25 24--17--23 3 | | | | 12---8-- ---7--11 2 | | | | | | 27--19- 5---2---4 -16--22 1 | | | | | 0 <- Y=0 | | | ---1---3 -15--21 -1 | | | 9---6--10 -2 | | | --13-- --14--20 -3 | ..--28--.. -4 ^ -4 -3 -2 -1 X=0 1 2 3 4
Notice that the bottom right quarter is rotated by 90 degrees, as per the "block 1" growth from a power-of-2 corner. This means it's not the same as in parts=4. The two upper parts are the same as parts=2 and parts=4.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::ToothpickTree->new ()
$path = Math::PlanePath::ToothpickTree->new (parts => $integer)
Create and return a new path object. parts can be 1, 2, 3 or 4.
parts
@n_children = $path->tree_n_children($n)
Return the children of $n, or an empty list if $n has no children (including when $n < 0, ie. before the start of the path).
$n
$n < 0
The children are the new toothpicks added at the ends of $n at the next level. This can be 0, 1 or 2 points. For example N=24 has no children, N=8 has a single child N=12, and N=2 has two children N=4,N=5. The way points are numbered means that two children are consecutive N values.
$n_parent = $path->tree_n_parent($n)
Return the parent node of $n, or undef if $n <= 0 (the start of the path).
undef
$n <= 0
$depth = $path->tree_n_to_depth($n)
$n = $path->tree_depth_to_n($depth)
Return the depth of point $n, or the first $n at given $depth.
$depth
The first point N=0 is at depth=0 in all the "parts" forms. The way parts=1 and parts=2 don't start at the origin means their depth at a given X,Y differs by 2 or by 1 from the full pattern at the same point.
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A139250 (etc) parts=4 A139250 total cells at given depth A139251 added cells at given depth A139253 total cells which are primes A147614 grid points covered at given depth (counting toothpick endpoints too) A139252 line segments at given depth coalescing touching ends horiz or vert A139560 added segments, net of any new joins A162795 total cells parallel to initial (at X==Y mod 2) A162793 added parallel to initial A162796 total cells opposite to initial (at X!=Y mod 2) A162794 added opposite to initial A162797 difference total cells parallel - opposite parts=3 A153006 total cells at given depth A152980 added cells at given depth A153007 difference depth*(depth+1)/2 - total cells, which is 0 at depth=2^k-1 parts=2 A152998 total cells at given depth A152968 added cells at given depth parts=1 A153000 total cells at given depth A152978 added cells at given depth
Drawings by Omar Pol
parts=4 http://www.polprimos.com/imagenespub/poltp4d4.jpg http://www.polprimos.com/imagenespub/poltp283.jpg parts=3 http://www.polprimos.com/imagenespub/poltp028.jpg parts=1 http://www.polprimos.com/imagenespub/poltp016.jpg
Math::PlanePath, Math::PlanePath::ToothpickReplicate, Math::PlanePath::UlamWarburton
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2012 Kevin Ryde
This file is part of Math-PlanePath-Toothpick.
Math-PlanePath-Toothpick is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath-Toothpick is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath-Toothpick. If not, see <http://www.gnu.org/licenses/>.
To install Math::PlanePath::LCornerTree, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath::LCornerTree
CPAN shell
perl -MCPAN -e shell install Math::PlanePath::LCornerTree
For more information on module installation, please visit the detailed CPAN module installation guide.