/ 
Math-PlanePath-Toothpick-18
River stage zero No dependents
/ Math::PlanePath::ToothpickUpist

NAME

Math::PlanePath::ToothpickUpist -- self-similar triangular tree traversal

SYNOPSIS

use Math::PlanePath::ToothpickUpist;
my $path = Math::PlanePath::ToothpickUpist->new;
my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

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

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.

Sierpinski Triangle

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.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::ToothpickUpist->new ()

Create and return a new path object.

Tree Methods

@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).

Level Methods

($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.

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include,

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

SEE ALSO

Math::PlanePath, Math::PlanePath::SierpinskiTriangle, Math::PlanePath::ToothpickTree

HOME PAGE

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 2012, 2013, 2014, 2015 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/>.