NAME

Math::PlanePath::ToothpickUpist -- self-similar triangular path 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 ...

It's 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 a 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 they cannot overlap). The variation here is that vertical toothpicks can only grow up, so nothing is 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 by growth depth and then left to right across the row within that depth. This means for example N=6,N=7 are up toothpicks giving N=8,N=9 in row Y=3, and then those two grow to N=10,N=11 and N=12,N=13 respectively left and right.

Sierpinski Triangle

As described in the paper the pattern is a version of the Sierpinski triangle with each row doubled. The vertical toothpicks, which are on "even" points X==Ymod2 are the Sierpinski triangle pattern, and the horizontal toothpicks on "odd" points X!=Ymod2 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

      5   ..h..           ..h..
      4     v h   h   h   h v         ToothpickUpist
      3       v h v   v h v
      2         v h   h v
      1           v h v
    Y=0             v

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 above it. 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 at tree level $depth. The start of the tree is depth=0 at the origin X=0,Y=0.

For $depth even this is the N at the left end of each row X=-Y,Y=depth/2. For $depth odd it's the point above there, 1 in from the left end, so X=-Y+1,Y=ceil(depth/2).

OEIS

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 at depth=n (A151565 same)

    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 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/>.

cpanm Math::PlanePath::LCornerTree

perl -MCPAN -e shell
install Math::PlanePath::LCornerTree