++ed by:
Kevin Ryde
and 1 contributors

# NAME

Math::PlanePath::UlamWarburtonQuarter -- growth of a 2-D cellular automaton

# SYNOPSIS

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

# DESCRIPTION

This is the pattern of a cellular automaton studied by Ulam and Warburton, confined to a quarter of the plane and oriented diagonally. Cells are numbered by growth level and anti-clockwise within the level.

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

The rule is a given cell grows diagonally NE, NW, SE and SW, but only if the new cell has no neighbours and is within the first quadrant. So the initial cell "a" is N=1,

``````    |
| a                    initial cell, depth=0
+----``````

It's confined to the first quadrant so can only grow NE as "b",

``````    |   b
| a                    "b" depth=1
+------``````

Then the next level "c" cells can go in three directions SE, NE, NW. These cells are numbered anti-clockwise around from the SE as N=3,N=4,N=5.

``````    | c   c
|   b
| a   c                "c" depth=2
+---------``````

The "d" cell is then only a single on the leading diagonal, since the other diagonals all already have neighbours (the existing "c" cells).

``````    |       d
| c   c                depth=3
|   b
| a   c
+---------

|     e   e
|       d
| c   c   e            depth=4
|   b
| a   c
+-----------

|   f       f
|     e   e
|       d
| c   c   e            depth=5
|   b       f
| a   c
+-------------

| g   g   g   g
|   f       f
| g   e   e   g
|       d
| c   c   e   g        depth=6
|   b       f
| a   c   g   g
+-------------``````

In general each level always grows by 1 along the X=Y leading diagonal, and travels into the sides with a self-similar diamond shaped pattern filling 6 of 16 cells any 4x4 square block.

## Level Ranges

Counting level 1 as the N=1 at the origin, level 2 as the next N=2, etc, the number of new cells added in a growth level is

``    levelcells(level) = 3^((count 1 bits in level) - 1)``

So level 1 has 3^(1-1)=1 cell, as does level 2 N=2. Then level 3 has 3^(2-1)=3 cells N=3,N=4,N=5 because 3=0b11 has two 1 bits in binary. The N start and end for a level is the cumulative total of those before it,

``````    Ndepth(level) = 1 + (levelcells(0) + ... + levelcells(level-1))

Nend(level) = levelcells(0) + ... + levelcells(level)``````

For example level 3 ends at N=(1+1+3)=5.

``````    level    Ndepth   levelcells     Nend
1          1         1           1
2          2         1           2
3          3         3           5
4          6         1           6
5          7         3           9
6         10         3          12
7         13         9          21
8         22         1          22
9         23         3          25``````

For a power-of-2 level the Ndepth sum is

``    Ndepth(2^a) = 1 + (4^a-1)/3``

For example level=4=2^2 starts at N=1+(4^2-1)/3=6, or level=8=2^3 starts N=1+(4^3-1)/3=22.

Further bits in the level value contribute powers-of-4 with a tripling for each bit above. So if the level number has bits a,b,c,d,etc in descending order,

``````    level = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...
Ndepth = 1 + (-1
+       4^a
+   3 * 4^b
+ 3^2 * 4^c
+ 3^3 * 4^d + ...) / 3``````

For example level=6 = 2^2+2^1 is Ndepth = 1+(4^2-1)/3 + 4^1 = 10. Or level=7 = 2^2+2^1+2^0 is Ndepth = 1+(4^2-1)/3 + 4^1 + 3*4^0 = 13.

## Self-Similar Replication

The square shape growth up to a level 2^ repeats three times. For example,

``````    |  d   d   c   c
|    d       c
|  d   d   c   c
|        *
|  a   a   b   b
|    a       b
|  a   a   b   b
+--------------------``````

The 3x3 square "a" repeats, pointing SE, NE and NW as "b", "c" and "d". This resulting 7x7 square then likewise repeats. The points in the path here are numbered by growth level rather than by this sort of replication, but the replication helps to see the structure of the pattern.

## N Start

The default is to number points starting N=1 as shown above. An optional `n_start` can give a different start, in the same pattern. For example to start at 0,

``````    n_start => 0

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

# FUNCTIONS

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

`\$path = Math::PlanePath::UlamWarburtonQuarter->new ()`
`\$path = Math::PlanePath::UlamWarburtonQuarter->new (n_start => \$n)`

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` has no children (including when `\$n < 1`, ie. before the start of the path).

The children are the cells turned on adjacent to `\$n` at the next level. This can be 0, 1 or 3 points. The way points are numbered means that when there's multiple children they're consecutive N values, for example at N=12 the children 19,20,21.

`\$num = \$path->tree_n_num_children(\$n)`

Return the number of children of `\$n`, or return `undef` if `\$n<1` (ie. before the start of the path).

`\$n_parent = \$path->tree_n_parent(\$n)`

Return the parent node of `\$n`, or `undef` if `\$n <= 1` (the start of the path).

# OEIS

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

``````    A147610     num cells in level, being 3^count1bits(depth)

n_start=1 (the default)
A151920   total cells to depth, being cumulative 3^(count 1-bits)
tree_depth_to_n_end()``````

Math::PlanePath::SierpinskiTriangle (a similar binary ones-count related level calculation)

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