Provided by: libmath-planepath-perl_113-1_all 
NAME
Math::PlanePath::UlamWarburton -- growth of a 2-D cellular automaton
SYNOPSIS
use Math::PlanePath::UlamWarburton;
my $path = Math::PlanePath::UlamWarburton->new;
my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION
This is the pattern of a cellular automaton studied by Ulam and Warburton, numbering cells
by growth level and anti-clockwise within their level.
94 9
95 87 93 8
63 7
64 42 62 6
65 30 61 5
66 43 31 23 29 41 60 4
69 67 14 59 57 3
70 44 68 15 7 13 58 40 56 2
96 71 32 16 3 12 28 55 92 1
97 88 72 45 33 24 17 8 4 1 2 6 11 22 27 39 54 86 91 <- Y=0
98 73 34 18 5 10 26 53 90 -1
74 46 76 19 9 21 50 38 52 ... -2
75 77 20 85 51 -3
78 47 35 25 37 49 84 -4
79 36 83 -5
80 48 82 -6
81 -7
99 89 101 -8
100 -9
^
-9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
The rule is that a given cell grows up, down, left and right, but only if the new cell has
no neighbours (up, down, left or right). So the initial cell "a" is N=1,
a initial level 0 cell
The next level "b" cells are numbered N=2 to N=5 anti-clockwise from the right,
b
b a b level 1
b
Likewise the next level "c" cells N=6 to N=9. The "b" cells only grow outwards as 4 "c"s
since the other positions would have neighbours in the existing "b"s.
c
b
c b a b c level 2
b
c
The "d" cells are then N=10 to N=21, numbered following the previous level "c" cell order
and then anti-clockwise around each.
d
d c d
d b d
d c b a b c d level 3
d b d
d c d
d
There's only 4 "e" cells since among the "d"s only the X,Y axes won't have existing
neighbours (the "b"s and "d"s).
e
d
d c d
d b d
e d c b a b c d e level 4
d b d
d c d
d
e
In general each level always grows by 1 along the X and Y axes and travels into the
quarter planes between with a sort of diamond shaped tree pattern which fills 11 cells of
each 4x4 square block.
Level Ranges
Counting level 0 as the N=1 at the origin and level 1 as the next N=2,3,4,5 generation,
the number of new cells added in a growth level is
levelcells(0) = 1
then
levelcells(level) = 4 * 3^((count 1 bits in level) - 1)
So level 1 has 4*3^0=4 cells, as does level 2 N=6,7,8,9. Then level 3 has 4*3^1=12 cells
N=10 to N=21 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+4+4)=9.
level Ndepth levelcells Nend
0 1 1 1
1 2 4 5
2 6 4 9
3 10 12 21
4 22 4 25
5 26 12 37
6 38 12 49
7 50 36 85
8 86 4 89
9 90 12 101
For a power-of-2 level the Ndepth is
Ndepth(2^a) = 2 + 4*(4^a-1)/3
For example level=4=2^2 starts at N=2+4*(4^2-1)/3=22, or level=8=2^3 starts
N=2+4*(4^3-1)/3=86.
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 = 2 + 4*(-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 = 2 + (1+4*(4^2-1)/3) + 4^(1+1) = 38. Or level=7
= 2^2+2^1+2^0 is Ndepth = 1 + (1+4*(4^2-1)/3) + 4^(1+1) + 3*4^(0+1) = 50.
Self-Similar Replication
The diamond shape growth up to a level 2^a repeats three times. For example an "a" part
going to the right,
d
d d d
a d c
a a a * c c c ...
a b c
b b b
b
The 2x2 diamond shaped "a" repeats pointing up, down and right as "b", "c" and "d". This
resulting 4x4 diamond then likewise repeats up, down and right. The points in the path
here are numbered by growth level rather than in this sort of replication, but the
replication helps to see the structure of the pattern.
Half Plane
Option "parts => '2'" confines the pattern to the upper half plane "Y>=0",
parts => "2"
28 6
21 5
29 22 16 20 27 4
11 3
30 12 6 10 26 2
23 13 3 9 19 1
31 24 17 14 7 4 1 2 5 8 15 18 25 <- Y=0
--------------------------------------
-6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6
Points are still numbered anti-clockwise around so X axis N=1,2,5,8,15,etc is the first of
each level and X negative axis N=1,4,7,14,etc is the last.
Within a row a line from point N to N+1 is always a 45-degree angle. This is true of each
3 direct children, but also across groups of children by symmetry. For this parts=2 the
lines from the last of one row to the first of the next are horizontal, making an
attractive pattern of diagonals and then across to the next row horizontally. For parts=4
or parts=1 the last to first lines are at various different slopes and so upsets the
pattern.
One Quadrant
Option "parts => '1'" confines the pattern to the first quadrant,
parts => "1"
14 | 73
13 | 63
12 | 53 62 72
11 | 49
10 | 39 48 71
9 | 35 47 61
8 | 31 34 38 46 52 60 70
7 | 29 45 59
6 | 19 28 69 67
5 | 15 27 57
4 | 11 14 18 26 68 58 51 56 66
3 | 9 25 23 43
2 | 5 8 24 17 22 44 37 42 65
1 | 3 7 13 21 33 41 55
Y=0 | 1 2 4 6 10 12 16 20 30 32 36 40 50 54 64
+-----------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
X axis N=1,2,4,6,10,etc is the first of each depth level and Y axis N=1,3,5,9,11,etc is
the last.
In this arrangement horizontal arms have even N and vertical arms have odd N. For example
the vertical at X=8 N=30,33,37,etc has N odd and when it turns to horizontal at N=42 or
N=56 it becomes N even. The children of N=66 are not shown but the verticals from there
are N=79 below and N=81 above and so are odd again.
This odd/even pattern is true of N=2 horizontal and N=3 vertical and thereafter is true
due to each row having an even number of points and the self-similar replications in the
pattern,
|\ replication
| \ block 0 to 1 and 3
|3 \ and block 0 block 2 less sides
|----
|\ 2|\
| \ | \
|0 \|1 \
---------
Block 0 is the base and is replicated as block 1 and in reverse as block 3. Block 2 is a
further copy of block 0, but the two halves of block 0 rotated inward 90 degrees, so the X
axis of block 0 becomes the vertical of block 2, and the Y axis of block 0 the horizontal
of block 2. Those axis parts are dropped since they're already covered by block 1 and 3
and dropping them flips the odd/even parity to match the vertical/horizontal flip due to
the 90-degree rotation.
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
29 5
30 22 28 4
13 3
14 6 12 2
31 15 2 11 27 1
32 23 16 7 3 0 1 5 10 21 26 <- Y=0
33 17 4 9 25 -1
18 8 20 37 -2
19 -3
34 24 36 -4
35 -5
^
-5 -4 -3 -2 -1 X=0 1 2 3 4 5
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
"$path = Math::PlanePath::UlamWarburton->new ()"
"$path = Math::PlanePath::UlamWarburton->new (parts => $str, n_start => $n)"
Create and return a new path object. The "parts" option (a string) can be
"4" the default
"2"
"1"
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. The way points
are numbered means that when there's multiple children they're consecutive N values,
for example at N=6 the children are 10,11,12.
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 list varies with the
pattern parts,
parts tree_num_children_list()
----- ------------------------
4 0, 1, 3, 4
2 0, 1, 2, 3
1 0, 1, 2, 3
parts=4 has 4 children at the origin N=0 and thereafter either 0, 1 or 3. parts=2 or
parts=1 can have 2 children on the boundaries where the 3rd child is chopped off.
"$n_parent = $path->tree_n_parent($n)"
Return the parent node of $n, or "undef" if "$n <= 1" (the start of the path).
OEIS
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences as
<http://oeis.org/A147582> (etc)
parts=4
A147562 total cells to depth, being tree_depth_to_n() n_start=0
A147582 added cells at depth
parts=2
A183060 total cells to depth=n in half plane
A183061 added cells at depth=n
parts=1
A151922 total cells to depth=n in quadrant
A079314 added cells at depth=n
The A147582 new cells sequence starts from n=1, so takes the innermost N=1 single cell as
level n=1, then N=2,3,4,5 as level n=2 with 5 cells, etc. This makes the formula a binary
1-bits count on n-1 rather than on N the way levelcells() above is expressed.
The 1-bits-count power 3^(count 1-bits in level) part of the levelcells() is also
separately in A048883, and as n-1 in A147610.
SEE ALSO
Math::PlanePath, Math::PlanePath::UlamWarburtonQuarter, Math::PlanePath::LCornerTree,
Math::PlanePath::CellularRule
Math::PlanePath::SierpinskiTriangle (a similar binary 1s-count related level calculation)
HOME PAGE
<http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE
Copyright 2011, 2012, 2013 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/>.