Math::PlanePath::ToothpickUpist -- self-similar triangular tree traversal
use Math::PlanePath::ToothpickUpist; my $path = Math::PlanePath::ToothpickUpist->new; my ($x, $y) = $path->n_to_xy (123);
This is toothpick variation where a vertical toothpick may only extend upwards.
66 62 63 67 68 64 65 69 10 58 56 59 60 57 61 9 54 46 47 48 49 50 51 52 53 55 8 38 34 39 40 35 41 42 36 43 44 37 45 7 30 26 27 31 32 28 29 33 6 22 20 23 24 21 25 5 18 14 15 16 17 19 4 10 8 11 12 9 13 3 6 4 5 7 2 2 1 3 1 0 <- Y=0 X= -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ...
This is a 90-degree rotated version of the "leftist" pattern from part 7 "Leftist Toothpicks" of
David Applegate, Omar E. Pol, N.J.A. Sloane, "The Toothpick Sequence and Other Sequences from Cellular Automata", Congressus Numerantium, volume 206 (2010), pages 157-191. http://www.research.att.com/~njas/doc/tooth.pdf
As per ToothpickTree
(Math::PlanePath::ToothpickTree) each point is considered a toothpick of length 2, starting from an initial vertical toothpick at the origin X=0,Y=0. Then the pattern grows by adding a toothpick at each exposed end, so long as it would not cause two toothpicks to overlap (an end can touch, but toothpicks cannot overlap). The variation here is that vertical toothpicks can only grow upwards, so nothing is ever added at the bottom end of a vertical.
... ... ... ... | | | | 10---8--11 12---9---13 | | | | 6---4--- ---5---7 | | | | 2---1---3 | | | 0 |
Points are numbered breadth-first tree traversal and left to right across the row. This means for example N=6 and N=7 are up toothpicks giving N=8 and N=9 in row Y=3, and then those two grow to N=10,11,12,13 respectively left and right.
As described in the paper above, the rule gives a version of the Sierpinski triangle where each row is doubled. (See Math::PlanePath::SierpinskiTriangle.)
Vertical toothpicks are on "even" points X==Y mod 2 and make the Sierpinski triangle pattern. Horizontal toothpicks are on "odd" points X!=Y mod 2 and are a second copy of the triangle, positioned up one at Y+1.
5 h h 4 v v h h h h 3 v v v v h h 2 v v plus h h 1 v v h Y=0 v gives ToothpickUpist 5 ..h.. ..h.. 4 v h h h h v 3 v h v v h v 2 v h h v 1 v h v Y=0 v
A vertical toothpick always has a child at its upwards end. But the horizontal toothpicks may or may not be able to grow at its two ends.
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::ToothpickUpist->new ()
Create and return a new path object.
@n_children = $path->tree_n_children($n)
Return the children of $n
, or an empty list if $n<0
(ie. before the start of the path).
Every vertical toothpick has a single child. The horizontal toothpicks have either 0, 1 or 2 children according to the Sierpinski triangle pattern. (See "N to Number of Children" in Math::PlanePath::SierpinskiTriangle).
$n_parent = $path->tree_n_parent($n)
Return the parent node of $n
, or undef
if $n<=0
(the start of tree).
For a horizontal toothpick the parent is the vertical below it. For a vertical toothpick the parent is the horizontal to its left or its right, according to the Sierpinski triangle pattern.
$depth = $path->tree_n_to_depth($n)
Return the depth of node $n
, or undef
if there's no point $n
.
Each row Y has two depth levels, starting from Y=1 having depth=1 and depth=2, so depth=ceil(Y/2).
$n = $path->tree_depth_to_n($depth)
$n = $path->tree_depth_to_n_end($depth)
Return the first or last N of tree row $depth
. The start of the tree is depth=0 at the origin X=0,Y=0.
For even $depth
this is the N at the left end of each row X=-Y,Y=depth/2. For odd $depth
it's the point above there, one cell in from the left end, so X=-Y+1,Y=ceil(depth/2).
($n_lo, $n_hi) = $path->level_to_n_range($level)
Return (0, 2 * 3**$level - 1)
. There are 3^level pairs of points making up a level, numbered starting from 0.
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include,
http://oeis.org/A151566 (etc)
A151566 total cells at depth=n, tree_depth_to_n() A060632 cells added, 2^count1bits(floor(n/2)) A151565 cells added (duplicate of A060632) A175098 total lattice points touched by length=2 toothpicks A160742 total*2 A160744 total*3 A160745 added*3 A160746 total*4
Math::PlanePath, Math::PlanePath::SierpinskiTriangle, Math::PlanePath::ToothpickTree
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2012, 2013, 2014 Kevin Ryde
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/>.