/ 
Math-PlanePath-49
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::UlamWarburtonQuarter

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 done on the diagonal. 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. So the initial cell "a" is N=1,

|
| a                    initial level 1 cell
+----

The next level "b" cell can only go NE,

|   b
| a                    level 2
+------

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

| c   c
|   b
| a   c                level 3
+---------

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

|       d
| c   c                level 4
|   b
| a   c
+---------

|     e   e
|       d
| c   c   e            level 5
|   b
| a   c
+-----------

|   f       f
|     e   e
|       d
| c   c   e            level 6
|   b       f
| a   c
+-------------

| g   g   g   g
|   f       f
|     e   e   g
|       d
| c   c   e   g        level 7
|   b       f
| a   c   g   g
+-------------

In general each level always grows by 1 along the leading diagonal X=Y and travels into the sides with a sort of diamond shaped tree pattern filling 6 cells of each 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,

Nstart(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    Nstart   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 Nstart sum is

Nstart(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...
Nstart = 1 + (4^a-1)/3
           +       4^b
           +   3 * 4^c
           + 3^2 * 4^d + ...

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

Self-Similar Replication

The square shape growth up to a level 2^a repeats three times. For example a 5-cell "a" part,

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

The 2x2 square "a" repeats, pointing SE, NE and NW as "b", "c" and "d". This resulting 4x4 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.

FUNCTIONS

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

$path = Math::PlanePath::UlamWarburtonQuarter->new ()

Create and return a new path object.

($x,$y) = $path->n_to_xy ($n)

Return the X,Y coordinates of point number $n on the path. Points begin at 1 and if $n < 0 then the return is an empty list.

SEE ALSO

Math::PlanePath, Math::PlanePath::UlamWarburton, Math::PlanePath::CellularRule54

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

HOME PAGE

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

LICENSE

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