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 tree row and anti-clockwise within the rows.
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 growth 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 depth=0 cell
The next row "b" cells are numbered N=2 to N=5 anti-clockwise from the
right,
b
b a b depth=1
b
Likewise the next row "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 depth=2
b
c
The "d" cells are then N=10 to N=21, numbered following the previous
row "c" cell order and then anti-clockwise around each.
d
d c d
d b d
d c b a b c d depth=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 depth=4
d b d
d c d
d
e
In general the pattern always grows by 1 outward along the X and Y axes and
travels into the quarter planes between with a diamond shaped tree pattern
which fills 11 of 16 cells in each 4x4 square block.
Tree Row Ranges¶
Counting depth=0 as the N=1 at the origin and depth=1 as the next N=2,3,4,5
generation, the number of cells in a row is
rowwidth(0) = 1
then
rowwidth(depth) = 4 * 3^((count_1_bits(depth) - 1)
So depth=1 has 4*3^0=4 cells, as does depth=2 at N=6,7,8,9. Then depth=3 has
4*3^1=12 cells N=10 to N=21 because depth=3=0b11 has two 1-bits in binary. The
N start and end for a row 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 3 ends at N=(1+4+4)=9.
depth Ndepth rowwidth 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 depth the Ndepth is
Ndepth(2^a) = 2 + 4*(4^a-1)/3
For example depth=4=2^2 starts at N=2+4*(4^2-1)/3=22, or depth=8=2^3 starts
N=2+4*(4^3-1)/3=86.
Further bits in the depth value contribute powers-of-4 with a tripling for each
bit above. So if the depth number has bits a,b,c,d,etc in descending order,
depth = 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 depth=6 = 2^2+2^1 is Ndepth = 2 + (1+4*(4^2-1)/3) + 4^(1+1) = 38. Or
depth=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 depth=1 to depth=2^level-1 repeats three times. For example an
"a" part going to the right of the origin "O",
d
d d d
| a d c
--O 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 same happens in the other
quarters of the plane.
The points in the path here are numbered by tree rows 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 row depth=X. X negative axis N=1,4,7,14,etc is the last of row
depth=-X. For depth=0 point N=1 is both the first and last of that row.
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" to depth=14
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 row X=depth. Y axis
N=1,3,5,9,11,etc is the last similarly Y=depth.
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 from N=33 up and when
it turns to horizontal at N=42 or N=56 it switches to 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 switch to 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.
Octant¶
Option "parts => 'octant'" confines the pattern to the first eighth
of the plane 0<=Y<=X.
parts => "octant"
7 | 47 ...
6 | 48 36 46
5 | 49 31 45
4 | 50 37 32 27 30 35 44
3 | 14 51 24 43 41
2 | 15 10 13 25 20 23 42 34 40
1 | 5 8 12 18 22 29 39
Y=0 | 1 2 3 4 6 7 9 11 16 17 19 21 26 28 33 38
+-------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
In this arrangement N=1,2,3,4,6,7,etc on the X axis is the first N of each row
("tree_depth_to_n()").
Upper Octant¶
Option "parts => 'octant_up'" confines the pattern to the upper
octant 0<=X<=Y of the first quadrant.
parts => "octant_up"
8 | 16 17 19 22 26 29 34 42
7 | 15 21 28 41
6 | 10 14 38 33 40
5 | 8 13 39
4 | 6 7 9 12
3 | 5 11
2 | 3 4
1 | 2
Y=0 | 1
+--------------------------
X=0 1 2 3 4 5 6 7
In this arrangement N=1,2,3,5,6,8,etc on the Y axis the last N of each row
("tree_depth_to_n_end()").
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 row. 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 in $path. This is the set
of possible return values from "tree_n_num_children()". The
possible children varies with the "parts",
parts tree_num_children_list()
----- ------------------------
4 0, 1, 3, 4 (the default)
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 and parts=1 can have 2 children on the boundaries where the 3rd
child is chopped off, otherwise 0, 1 or 3.
- "$n_parent = $path->tree_n_parent($n)"
- Return the parent node of $n, or "undef" if "$n <=
1" (the start of the path).
Level Methods¶
- "($n_lo, $n_hi) = $path->level_to_n_range($level)"
- Return "$n_lo = $n_start" and
parts $n_hi
----- -----
4 $n_start + (16*4**$level - 4) / 3
2 $n_start + ( 8*4**$level - 5) / 3 + 2*2**$level
1 $n_start + ( 4*4**$level - 4) / 3 + 2*2**$level
$n_hi is "tree_depth_to_n_end(2**($level+1) - 1".
OEIS¶
This cellular automaton is in Sloane's Online Encyclopedia of Integer Sequences
as
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 row n=1, then N=2,3,4,5 as row n=2 with 5 cells, etc. This
makes the formula a binary 1-bits count on n-1 rather than on N the way
rowwidth() above is expressed.
The 1-bits-count power 3^(count_1_bits(depth)) part of the
rowwidth() 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
calculation)
HOME PAGE¶
<
http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE¶
Copyright 2011, 2012, 2013, 2014 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/>.