NAME
Math::PlanePath::ToothpickTree -- toothpick pattern by growth levels
SYNOPSIS
use Math::PlanePath::ToothpickTree;
my $path = Math::PlanePath::ToothpickTree->new;
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
This is the "toothpick" sequence which expands 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 4Each 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 are added to the two ends of the initial N=0 toothpick. Then points N=3,4,5,6 are added at the four ends of those.
---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 at X=1,Y=0 where the ends of N=3 and N=6 meet , and likewise not at X=-1,Y=0 where N=4 and N=5 meet.
The end of a new toothpick is allowed to 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. The initial N=0 is depth=0. It also means that "even" points X==Y mod 2 are vertical and "odd" points X!=Y mod 2 are horizontal.
Cellular Automaton
The toothpick rule can also be expressed as growing into a cell which has just one of two vertical or horizontal neighbours.
Point Grow
------------------ ------------------------------------------
X==Y mod 2, "even" turn ON if 1 of 2 horizontal neighbours ON
X!=Y mod 2, "odd" turn ON if 1 of 2 vertical neighbours ONFor example X=0,Y=1 which is N=1 turns ON because it has a single vertical neighbour (the origin X=0,Y=0). But the cell X=1,Y=0 never turns ON because initially its two vertical are OFF and then later at depth=3 they're both ON. Only when there's exactly one of the two neighbours (in the relevant direction) does the cell turn ON.
Replication
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 an X=2^k,Y=2^k power-of-2 and toothpick "B" is above it. The B toothpick leading to blocks 2 and 3 means block 1 is one growth level ahead of blocks 2 and 3 in the replication.
In the diagram above, in 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 (the diagram of the "One Quadrant" form below extends to there).
The initial N=3,N=7 can be thought of as an "A,B" middle pair with empty blocks before and surrounding.
See Math::PlanePath::ToothpickReplicate for a digit-based replication instead of by growth levels.
Level Ranges
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...22The 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 to "A" (8*4^k + 1)/3 8/3 * 4^k
-------- = ------------- -> --------- = 2/3
Area X*Y (2*2^k)*(2*2^k) 4 * 4^kOne Quadrant
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
... ...
| | |
| 47--44--46
| | |
8 | --41-- --40-- --39-- --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 8The "A" toothpick at X=2^k,Y=2^k is
N of "A" = (2*4^k - 2)/3 = 2,10,42,etc
= "222...222" in base 4The repeating part starts from N=0 here so there's no initial centre toothpicks like the full pattern. This means the repetition is a plain 4*N+2 and hence a N="222..222" in base 4.
Half Plane
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
... ... 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 4Three Parts
Option parts => 3 is the three replications which occur from an X=2^k,Y=2^k point, continued on indefinitely confined to the upper and right three quadrants.
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 4The 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 the bottom right of parts=4. The two upper parts are the same as in parts=4 and parts=2.
As noted by David Applegate and Omar Pol in OEIS A153006, the three parts replication means that N at the last level of a power-of-2 level is a triangular number, ie.
depth=2^k-1
N(depth) = (2^k-1)*2^k/2 = triangular number depth*(depth+1)/2
at X=(depth-1)/2, Y=-(depth+1)/2For depth=2^3-1=7 begins at N=7*8/2=28 and is at the lower right corner X=(7-1)/2=3, Y=-(7+1)/2=-4. If the depth is not such a 2^k-1 then the Ndepth start of the level is less than the triangular depth*(depth+1)/2.
FUNCTIONS
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.
partscan be 1, 2, 3 or 4.
Tree Methods
@n_children = $path->tree_n_children($n)-
Return the children of
$n, or an empty list if$nhas no children (including when$n < 0, ie. before the start of the path).The children are the new toothpicks added at the ends of
$nat 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, orundefif no parent due to$n <= 0(the start of the path). $depth = $path->tree_n_to_depth($n)$n = $path->tree_depth_to_n($depth)-
Return the depth of point
$n, or first$nat given$depth, respectively.The first point N=0 is 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 1 respectively from the full pattern at the same point.
FORMULAS
Depth to N
The first N at given depth is given by the formulas in the paper by Applegate, Pol and Sloane above. The first N is the total count of toothpicks in the preceding levels.
depth = pow + rem
where pow=2^k and 0 <= rem < 2^k
Mquad(depth) = (4^k-4)/6 # 4^k = pow*pow
/ 0 if rem=0 # for depth=pow
+ | 1 if rem=1 # the "A" toothpick
\ Ndepth(rem+1) + 2*Ndepth(rem) + 2 if rem>=2
parts=1 Ndepth = Nquad(depth+2)
parts=2 Ndepth = 2*Nquad(depth+1) + 1
parts=3 Ndepth = 3*Nquad(depth+1) + 2
parts=4 Ndepth = 4*Nquad(depth) + 3Nquad is the total points of a single quadrant with depth numbered in the style of parts=4. For example depth=8 gives Nquad=(4^3-4)/6=10 which is the N at X=4,Y=4.
Ndepth is then the Nquad with depth adjusted for whether the respective parts=1,2,3,4 begin with depth=0 at the origin or 1 or 2, plus the initial 1, 2 or 3 points not in the Nquad replications.
The (4^k-4)/6 part is the total points in a 2*depth x 2*depth block, similar to "Level Ranges" above but a single quadrant. It's a value "222..22" in base-4, with k-1 many "2"s. For example depth=8=2^3 has k=3 so k-1=2 many "2"s for value "22" base-4 is 10.
The breakdown of depth to Ndepth(rem+1) + 2*Ndepth(rem) is the important part of the formula. It knocks out the high bit of depth and spreads to an adjacent pair rem+1,rem. This can be handled by keeping a list of pending depth values desired and knocking them down with the biggest necessary pow=2^k, then reduce to pow=2^(k-1), etc.
Because rem+1,rem are adjacent successive reductions make a list like d+2,d+1,d then d+3,d+2,d+1,d etc. But when the list crosses a 2^k then some are reduced and others remain. When that happens the list is no longer successive values, only mostly so. When breaking to rem+1,rem it's enough to check whether rem+1 is equal to the "rem" from the previous breakdown and if so coalesce with that pending entry.
The factor of 2 in 2*Ndepth(rem) can be handled by keeping a desired multiplier with each pending depth. Ndepth(rem+1) copies the current multiplier, and 2*Ndepth(rem) doubles the current. When coalescing with a previous entry then add to its multiplier.
If the pending list is a list of successive integers then the rem+1,rem breakdown and coalesce increases that list by just one value, keeping the list to log2(depth) many entries (the number of bits in depth). But as noted above that's not so when the list crosses a 2^k boundary. It's then behaves like two lists and each grow by one entry. But in any case the list doesn't become huge.
N to Depth
The current tree_n_to_depth() does a binary search for depth by calling tree_depth_to_n() on a successively narrower range. Is there a better approach?
Some intermediate values in the depth-to-N might be re-used by such repeated calls, but it's not clear how many would be re-used and how many would be needed only once. The current code doesn't retain any such intermediates, so large N can be handled without using a lot of memory.
OEIS
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 depthDrawings 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.jpgSEE ALSO
Math::PlanePath, Math::PlanePath::ToothpickReplicate, Math::PlanePath::UlamWarburton
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2012, 2013 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/>.