Kevin Ryde > Math-PlanePath-Toothpick-12 > Math::PlanePath::ToothpickUpist
Module Version: 12   Source   Latest Release: Math-PlanePath-Toothpick-13

# 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

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 within a depth level. 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 at tree level `\$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).

# 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()
A151565     cells added (duplicate of A060632)
A175098    total lattice points touched by length=2 toothpicks

A160742    total*2
A160744    total*3
A160746    total*4```

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