Provided by: libmath-planepath-perl_125-1_all bug

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 tree row and
       anti-clockwise within the row.

           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 growth 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 row "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 the pattern always always grows by 1 along the X=Y leading diagonal.  The point
       on that diagonal is the middle of row depth=X.  The pattern expands into the sides with a
       self-similar diamond shaped pattern filling 6 of 16 cells in any 4x4 square block.

   Tree Row Ranges
       Counting depth=0 as the N=1 at the origin, depth=1 as the next N=2, etc, the number of new
       cells added in the tree row is

           rowwidth(depth) = 3^(count_1_bits(depth+1) - 1)

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

           Ndepth(depth) = 1 + rowwidth(0) + ... + rowwidth(depth-1)

           Nend(depth) = rowwidth(0) + ... + rowwidth(depth)

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

           depth    Ndepth    rowwidth      Nend
             0          1         1           1
             1          2         1           2
             2          3         3           5
             3          6         1           6
             4          7         3           9
             5         10         3          12
             6         13         9          21
             7         22         1          22
             8         23         3          25

       At row depth+1 = power-of-2 the Ndepth sum is

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

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

       Further bits in the depth+1 contribute powers-of-4 with a tripling for each bit above it.
       So if depth+1 has bits a,b,c,d,etc from high to low then

           depth+1 = 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 depth=5 is depth+1=6 = 2^2+2^1 is Ndepth = 1+(4^2-1)/3 + 4^1 = 10.  Or depth=6
       is depth+1=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 to depth=2^level-2 repeats the pattern to the preceding
       depth=2^(level-1)-2 three times.  For example,

           |  d   d   c   c             depth=6 = 2^3-2
           |    d       c               triplicates
           |  d   d   c   c             depth=2 = 2^2-2
           |        *
           |  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 tree rows
       rather than by this sort of replication, but the replication helps to see the structure of
       the pattern.

   Octant
       Option "parts => 'octant'" confines the pattern to the first eighth of the plane 0<=Y<=X.

           parts => "octant"

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

       In this arrangement N=1,2,4,5,7,etc on the leading diagonal is the last N of each row
       ("tree_depth_to_n_end()").

   Upper Octant
       Option "parts => 'octant_up'" confines the pattern to the upper octant 0<=X<=Y of the
       first quadrant.

           parts => "octant_up"

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

       In this arrangement N=1,2,3,5,6,etc on the leading diagonal is the first N of each row
       ("tree_depth_to_n()").

   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 (parts => $str, n_start => $n)"
           Create and return a new path object.  "parts" can be

               1              first quadrant, the default
               "octant"       first eighth
               "octant_up"    upper eighth

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

       "$n_parent = $path->tree_n_parent($n)"
           Return the parent node of $n, or "undef" if "$n <= 1" (the start of the path).

   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()".

               parts        tree_num_children_list()
               -----        ------------------------
                 1              0, 1,    3
               octant           0, 1, 2, 3
               octant_up        0, 1, 2, 3

           The octant forms have 2 children when branching from the leading diagonal, otherwise
           0,1,3.

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "($n_start, tree_depth_to_n_end(2**($level+1) - 2))".

OEIS

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

           <http://oeis.org/A151920> (etc)

           parts=1  (the default)
             A147610   num cells in row, tree_depth_to_width()
             A151920   total cells to depth, tree_depth_to_n_end()

           parts=octant,octant_up
             A079318   num cells in row, tree_depth_to_width()

SEE ALSO

       Math::PlanePath, Math::PlanePath::UlamWarburton, Math::PlanePath::LCornerTree,
       Math::PlanePath::CellularRule

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

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde

       This file is part of Math-PlanePath.

       Math-PlanePath 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 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.  If not, see <http://www.gnu.org/licenses/>.