Kevin Ryde
and 1 contributors

# NAME

Math::PlanePath::LCornerTree -- cellular automaton growing at exposed corners

# SYNOPSIS

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

# DESCRIPTION

This is the pattern of a cellular automaton growing by 3 cells at exposed corners. Points are numbered by a breadth-first tree traversal and anti-clockwise at each node. The default is four quadrants starting from four initial cells N=0 to N=3,

``````    68  67                          66  65      4
69  41  40  39  38  35  34  33  32  64      3
42  20  19  37  36  18  17  31  ...     2
43  21   8   7   6   5  16  30          1
44  45   9   1   0   4  28  29     <- Y=0
47  46  10   2   3  15  63  62         -1
48  22  11  12  13  14  27  61         -2
49  23  24  54  55  25  26  60         -3
70  50  51  52  53  56  57  58  59  75     -4
71  72                          73  74     -5
^
-5  -4  -3  -2  -1  X=0  1   2   3   4``````

The growth rule is a cell which is an exposed corner grows by the three cells surrounding that corner. So

``````    depth=0   depth=1         depth=2             depth=3

d d d d d d d d
\| |/   \| |/
c c     c c       d-c c-d d-c c-d
\|     |/           \|     |/
b b b b       c-b b b b-c       d-c-b b b b-c-d
\| |/           \| |/           /|  \| |/  |\
a a       b-a a-b         b-a a-b         d d b-a a-b d d
->             ->               ->
a a       b-a a-b         b-a a-b         d d b-a a-b d d
/| |\           /| |\               /| |\  |/
b b b b       c-b b b b-c       d c-b b b b-c-d
/|     |\           /|     |\
c c       c       d-c c-d d-c c-d
/| |\   /| |\
d d d d d d d d``````

"a" is the first cell in each quadrant and grows into the three "b" around each. Then for the "b" cells only the corner ones are exposed corners and they grow to the "c" cells. Those "c" cells are then all exposed corners and give a set of 36 "d" cells. Of those "d"s only the corners are exposed corners for the next "e" row.

Grouping the three children of each corner shows the pattern

``````    +-----------------------+
|     |     |     |     |
|  +-----+  |  +-----+  |
|  |     |  |  |     |  |
|--|  +-----+-----+  |--|
|  |  |     |     |  |  |
|  +--|  +--+--+  |--+  |
|     |  |  |  |  |     |
|-----+--+--+--+--+-----|
|     |  |  |  |  |     |
|  +--|  +--+--+  |--+  |
|  |  |     |     |  |  |
|--|  +-----+-----+  |--|
|  |     |  |  |     |  |
|  +-----+  |  +-----+  |
|     |     |     |     |
+-----------------------+``````

In general the number of cells gained in each row is

``    Nwidth = 4 * 3^count1bits(depth)``

So for example depth=3 binary "11" has 2 1-bits so cells=4*3^2=36. Adding such powers-of-3 up to a depth=2^k gives a power-of-4 total square area.

Each side part turns by 90 degrees at its corner, so the plane is filled in a self-similar style turning into each side quarter. This is an attractive way to fill the plane by a tree structure.

``````    +----------------+
|       |        |
|  ^    |    ^   |
|   \   |   /    |
|    \  |  /     |
|       |        |
|-------+--------|
|       |        |
|    ^  |  \     |
|   /   |   \    |
|  /    |    v   |
| /     |        |
+----------------+``````

## Toothpicks

The points can be regarded as the centres of toothpicks oriented diagonally and growing at exposed endpoints.

``````            ..       ..
|     \     /
2 |      6   5         parts=1 (per below) as toothpicks
|       \ /
|        .
| \     / \
1 |  3   2   4
|   \ /     \
|    .       ..
|   / \
Y=0 |  0   1
| /     \
+-------------
X=0   1   2``````

Point N=0 is reckoned as a diagonal toothpick and the three N=1,2,3 grow from its exposed end. At the next row another three grow from the exposed end of N=2. Only an exposed end grows. If two toothpick ends touch then they don't grow.

The toothpicks are oriented on the leading diagonal for "even" X=Y mod 2 and on the opposite diagonal for "odd" points X!=Y mod 2. A rotation by 45 degrees can be applied to make them horizontal and vertical instead.

Option `parts => '1'` confines the pattern to the first quadrant. This is a single copy of the repeating part which is in each of the four quadrants of the full pattern.

``````    parts => "1"

4  |              18  17
3  |  14  13  12  11  16
2  |  15   6   5  10
1  |   3   2   4   9
Y=0 |   0   1   7   8
+---------------------
X=0   1   2   3   4``````

## Half Plane

Option `parts => '2'` confines the tree to the upper half plane `Y>=0`, giving two symmetric parts above the X axis.

``````    parts => "2"

36  35                          34  33        4
37  27  26  25  24  21  20  19  18  32        3
28  12  11  23  22  10   9  17            2
29  13   6   5   4   3   8  16            1
30  31   7   1   0   2  14  15        <- Y=0
--------------------------------------
-5  -4  -3  -2  -1  X=0  1   2   3   4``````

## Three Parts

Option `parts => '3'` is three replications arranged in a corner down and left.

``````    parts => "3"

55  54                          50  49        4
56  43  42  41  40  28  27  26  25  48        3
44  19  18  39  29  14  13  24            2
45  20  10   9   5   4  12  23            1
46  47  11   2   0   3  21  22        <- Y=0
------------------+  1   8  38  37           -1
|  6   7  17  36           -2
| 30  15  16  35
| 31  32  33  34  53
|             51  52
^
-5  -4  -3  -2  -1  X=0  1   2   3   4``````

This is similar to the way the tree grows from a power-of-2 corner X=2^k,Y=2^k, but here the numbering is the centre quadrant first, then the lower, then the left. (Whereas at a corner it would be clockwise around.)

## One Octant

Option `parts => 'octant'` confines the pattern to the first eighth of the plane. This is a single side of the eight-way symmetry in the full pattern.

``````    parts => "octant"

7  |                       35
6  |                    21 34
5  |                 16 20 33
4  |              11 15 31 32
3  |            9 10 14 30 29
2  |         4  8 12 13 19 28
1  |      2  3  7 22 17 18 27
Y=0 |   0  1  5  6 23 24 25 26
+--------------------------
X=0  1  2  3  4  5  6  7``````

The points are numbered in the same sequence as the parts=1 quadrant, but with those above the X=Y diagonal omitted. This means each N on the X=Y diagonal is the last of the row.

## One Octant Plus One

Option `parts => 'octant+1'` confines the pattern to the first eighth plus an additional diagonal above the eighth. This means each point on the diagonal has 3 children but the children above the diagonal don't grow any further.

``````    parts => "octant+1"

7  |                    42 41
6  |                 27 26 40
5  |              21 20 25 39
4  |           15 14 19 37 38
3  |        12 11 13 18 36 35
2  |      6  5 10 16 17 24 34
1  |   3  2  4  9 28 22 23 33
Y=0 |   0  1  7  8 29 30 31 32
+--------------------------
X=0  1  2  3  4  5  6  7``````

## Upper Octant

Option `parts => 'octant_up'` confines the pattern to the upper eighth of the first quadrant.

``````    parts => "octant_up"

7  |  31 30 29 28 25 24 23 22
6  |  32 20 19 27 26 18 17
5  |  33 21 15 14 13 12
4  |  34 35 16 11 10
3  |   8  7  6  5
2  |   9  4  3
1  |   2  1
Y=0 |   0
+--------------------------
X=0  1  2  3  4  5  6  7``````

The points are numbered in the same sequence as the parts=1 quadrant, but with those below the X=Y diagonal omitted. This means each N on the X=Y diagonal is the first of the row.

## Upper Octant Plus One

Option `parts => 'octant_up+1'` confines the pattern to the upper eighth of the first quadrant, plus an extra diagonal below.

``````    parts => "octant_up+1"

7  |  38 37 36 35 32 31 30 29
6  |  39 26 25 34 33 24 23 28
5  |  40 27 20 19 18 17 22
4  |  41 42 21 15 14 16
3  |  11 10  9  8 13
2  |  12  6  5  7
1  |   3  2  4
Y=0 |   0  1
+--------------------------
X=0  1  2  3  4  5  6  7``````

This corresponds to the parts=octant+1 above, but the numbering is still clockwise so goes from the diagonal to the axis whereas parts=octant+1 goes from the axis to the diagonal.

## Wedge

Option `parts => 'wedge'` confines the pattern to a wedge -Y-1 <= X <= Y and Y>=0.

``````    parts => "wedge"

71 70 69 68 65 64 63 62 53 52 51 50 47 46 45 44       7
43 42 67 66 41 40 61 54 37 36 49 48 35 34          6
33 32 31 30 39 60 55 38 27 26 25 24             5
23 22 29 58 59 56 57 28 21 20                4
19 18 17 16 13 12 11 10                   3
9  8 15 14  7  6                      2
5  4  3  2                         1
1  0                           Y=0
-----------------------------------------------
-8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7``````

The points are numbered in the same sequence as the full parts=4 pattern, but restricted to the wedge portion. This means each N on the right-hand X=Y diagonal is the first of the row and each N on the X=-1-Y left-hand diagonal is the last of the row.

In this arrangement even N falls on "even" points X=Y mod 2. Odd N falls on "odd" points X!=Y mod 2.

``````     O  E  O  E  O  E  O  E           3
O  E  O  E  O  E              2
O  E  O  E                 1
O  E               <-  Y=0

^
-4 -3 -2 -1 X=0 1  2  3``````

The odd/even is true of N=0 and N=1 and then for further points it's true due to the way the pattern repeats in 2^k rows.

``````    --------------   \  Y=2*2^k-1
\ 3 /  \ 1 /    |
\ /  2 \ /     /  Y=2^k
--------      \  Y=2^k-1
\base/       |
\  /        /  Y=0``````

The base part Y=0 to Y=2^k-1 repeats in block 1 and block 3. The middle block 2 is also a repeat, less 2 points on the diagonals, but the right half of the base is rotated +90 degrees and the left half of the base rotated -90 degrees to make the upside-down wedge.

parts=2 and parts=4 forms also have an even number of points in each row but they don't have N even on X,Y even the way the wedge does. That's because the numbering of parts=2 and parts=4 means each row begins on the "ragged" edge of the pattern which may be X,Y odd or even, whereas each wedge row begins on the X=Y diagonal which is always X,Y even.

In terms of toothpick triplets described above ("Toothpicks"), the wedge corresponds to an initial two toothpicks at right angles then growing into a single quadrant, when rotated -45 degrees to have the toothpicks vertical and horizontal. Toothpicks on the edges of the quadrant are restricted to 2 children and all other open ends have 3.

``````    |              parts => "wedge"
5              as toothpicks
|
.--4--
|     |
1     3
|     |
+--0--.--2--``````

## Wedge Plus One

Option `parts => 'wedge+1'` confines the pattern to a wedge -Y-2 <= X <= Y+1 and Y>=0. This is the parts=wedge above with an extra diagonal on each side.

``````    parts => "wedge"

84 83 82 81 78 77 76 75 66 65 64 63 60 59 58 57        7
85 54 53 80 79 52 51 74 67 48 47 62 61 46 45 56        6
55 42 41 40 39 50 73 68 49 36 35 34 33 44           5
43 30 29 38 71 72 69 70 37 28 27 32              4
31 24 23 22 21 18 17 16 15 26                 3
25 12 11 20 19 10  9 14                    2
13  6  5  4  3  8                       1
7  1  0  2                         Y=0
-----------------------------------------------
-8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7``````

As per parts=wedge each tree row has an even number of points and like that form odd/even N falls on even/odd X,Y. Here the first N of each tree row is an "odd" point X=Y+1 so it's even N on odd X,Y and odd N on even X,Y. The initial N=0 and N=1 are exceptions to this rule.

## Diagonal

Option `parts => 'diagonal'` confines the pattern to a diagonal half-plane X>=Y-1,

``````    parts => "diagonal"

35  34  33  32  29  28  27  26         3
\  |   | /      \  |   | /
16  15--31  30--14  13--25         2
\  |           | /
9   8   7   6--12--24         1
\ |   | /     | \
2   1---5  22  23        Y=0

0 - 4  21  20        -1
\     | /
3--11--19        -2
\
10--18        -3
\
17        -4
^
-4  -3  -2  -1  X=0  1  2  3  4  5  6  7``````

## Diagonal One

Option `parts => 'diagonal-1'` starts from a single point and is confined to a diagonal half-plane X>=Y,

``````    parts => "diagonal"

41  40  39  38  35  34  33  32         4
\  |   | /      \  |   | /
42--20  19--37  36--18  17--31         3
\  |           | /
21--11  10   9   8--16--30         2
\ |   | /    | \
12---3   2---7  28  29         1
| /
0---1---6  27  26     <- Y=0
|  \     | /
4   5--15--25        -1
| \
13  14--24        -2
| \
22  23        -3
^
-3  -2  -1  X=0  1   2   3   4``````

In this pattern the edge points such as N=1,5,14 all have 3 children, so there's always 0 or 3 children as per the full pattern. The square section beginning N=2 corresponds to the origin in the full pattern, so the initial single point here makes it one row later.

As toothpicks this pattern is OEIS A183148 half-plane of toothpick triplets by Omar Pol.

Turning the pattern +45 degrees and drawing toothpicks per "Toothpicks" above gives

``````                   |
8
|
---8---.---7---
|       |       |
9       3       6
|       |       |
--10---.---2---.---1---.---5---
|       |       |
11       0       4
|       |       |

--------------------------------``````

## Ulam Warburton

Taking just the non-leaf nodes gives the pattern of the Ulam-Warburton cellular automaton oriented at 45-degrees as per Math::PlanePath::UlamWarburtonQuarter and using 2x2 blocks for each cell.

``````    |  **  **  **  **        parts=>1  non-leaf cells
|  **  **  **  **
|    **      **
|    **      **
|  **  **  **  **
|  **  **  **  **
|        **
|        **
|  **  **  **  **
|  **  **  **  **
|    **      **
|    **      **
|  **  **  **  **
|  **  **  **  **
| *
+----------------``````

parts=4 gives the pattern of Math::PlanePath::UlamWarburton but again turned 45 degrees and in 2x2 blocks.

# FUNCTIONS

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

`\$path = Math::PlanePath::LCornerTree->new ()`
`\$path = Math::PlanePath::LCornerTree->new (parts => \$str)`

Create and return a new path object. The `parts` option (a string) can be

``````    "4"         the default
"3"
"2"
"1"
"octant"
"octant+1"
"octant_up"
"octant_up+1"
"wedge"
"wedge+1"
"diagonal"
"diagonal-1"``````

## Tree Descriptive Methods

`@nums = \$path->tree_num_children_list()`

Return a list of the possible number of children at the nodes of `\$path`. This is the set of possible return values from `tree_n_num_children()`. This varies with the `parts` option,

``````           parts               tree_num_children_list()
-----               ------------------------
4, 3, 2, 1             \
octant+1, octant_up+1,  |         0,    3
wedge+1, diagonal-1    /

octant, octant_up      \          0, 2, 3
wedge, diagonal        /``````

For parts=4,3,2,etc each point has either 0 or 3 children. Such a tree is sometimes called a "3-tree". For a corner cell the children are the three cells adjacent to it turned "on" at the next depth. A non-corner has no children.

For parts=octant etc the points on the X=Y diagonal have only 2 children since the pattern is confined to on or below that diagonal. All other points have either 0 or 3 as per the full patterns.

`\$num = \$path->tree_num_roots ()`

Return the number of root nodes in `\$path`. This varies with the `parts` option,

``````    parts                                     num_roots()
-----                                     -----------
4                                           4
3                                           3
2                                           2
1                                           1
octant, octant+1, octant_up, octant_up+1      1
wedge, wedge+1                                2
diagonal                                      3
diagonal-1                                    1``````

## Level Methods

`(\$n_lo, \$n_hi) = \$path->level_to_n_range(\$level)`

Return `(0, tree_depth_to_n_end(2**\$level - 1)`.

# OEIS

This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as follows, and drawings by Omar Pol.

``````    parts=4 (the default)
A160410   total cells at given depth, tree_depth_to_n()
A161411   added cells at given depth, 4*3^count1bits(n)

http://www.polprimos.com/imagenespub/polca023.jpg
http://www.polprimos.com/imagenespub/polca024.jpg

parts=3
A160412   total cells at given depth, tree_depth_to_n()
A162349   added cells at given depth, 3*3^count1bits(n)

http://www.polprimos.com/imagenespub/polca013.jpg
http://www.polprimos.com/imagenespub/polca027.jpg
http://www.polprimos.com/imagenespub/polca029.jpg

parts=1
A130665   total cells at given depth, from depth=1 onwards
cumulative 3^count1bits, tree_depth_to_n(d+1)
A048883   added cells at given depth, 3^count1bits(n)

http://www.polprimos.com/imagenespub/polca011.jpg
http://www.polprimos.com/imagenespub/polca012.jpg
http://www.polprimos.com/imagenespub/polca014.jpg

parts=octant,octant_up
A162784   added cells at given depth, (3^count1bits(n) + 1)/2

parts=wedge
A151712   added cells at given depth, 3^count1bits(n) + 1

http://www.polprimos.com/imagenespub/polca032.jpg

parts=diagonal-1
A183148   total cells at given depth, tree_depth_to_n()
A183149   added cells at given depth``````

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