1Math::PlanePath::UlamWaUrsbeurrtCoonnQturairbtuetre(d3M)Paetrhl::DPolcaunmeePnattaht:i:oUnlamWarburtonQuarter(3)
2
3
4

NAME

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

SYNOPSIS

10        use Math::PlanePath::UlamWarburtonQuarter;
11        my $path = Math::PlanePath::UlamWarburtonQuarter->new;
12        my ($x, $y) = $path->n_to_xy (123);
13

DESCRIPTION

15       This is the pattern of a cellular automaton studied by Ulam and
16       Warburton, confined to a quarter of the plane and oriented diagonally.
17       Cells are numbered by growth tree row and anti-clockwise within the
18       row.
19
20           14 |  81    80    79    78    75    74    73    72
21           13 |     57          56          55          54
22           12 |  82    48    47    77    76    46    45    71
23           11 |           40                      39
24           10 |  83    49    36    35    34    33    44    70
25            9 |     58          28          27          53
26            8 |  84    85    37    25    24    32    68    69
27            7 |                       22
28            6 |  20    19    18    17    23    31    67    66
29            5 |     12          11          26          52
30            4 |  21     9     8    16    29    30    43    65
31            3 |            6                      38
32            2 |   5     4     7    15    59    41    42    64
33            1 |      2          10          50          51
34           Y=0|   1     3    13    14    60    61    62    63
35              +----------------------------------------------
36                X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
37
38       The growth rule is a given cell grows diagonally NE, NW, SE and SW, but
39       only if the new cell has no neighbours and is within the first
40       quadrant.  So the initial cell "a" is N=1,
41
42           |
43           | a                    initial cell, depth=0
44           +----
45
46       It's confined to the first quadrant so can only grow NE as "b",
47
48           |   b
49           | a                    "b" depth=1
50           +------
51
52       Then the next row "c" cells can go in three directions SE, NE, NW.
53       These cells are numbered anti-clockwise around from the SE as
54       N=3,N=4,N=5.
55
56           | c   c
57           |   b
58           | a   c                "c" depth=2
59           +---------
60
61       The "d" cell is then only a single on the leading diagonal, since the
62       other diagonals all already have neighbours (the existing "c" cells).
63
64           |       d
65           | c   c                depth=3
66           |   b
67           | a   c
68           +---------
69
70           |     e   e
71           |       d
72           | c   c   e            depth=4
73           |   b
74           | a   c
75           +-----------
76
77           |   f       f
78           |     e   e
79           |       d
80           | c   c   e            depth=5
81           |   b       f
82           | a   c
83           +-------------
84
85           | g   g   g   g
86           |   f       f
87           | g   e   e   g
88           |       d
89           | c   c   e   g        depth=6
90           |   b       f
91           | a   c   g   g
92           +-------------
93
94       In general the pattern always always grows by 1 along the X=Y leading
95       diagonal.  The point on that diagonal is the middle of row depth=X.
96       The pattern expands into the sides with a self-similar diamond shaped
97       pattern filling 6 of 16 cells in any 4x4 square block.
98
99   Tree Row Ranges
100       Counting depth=0 as the N=1 at the origin, depth=1 as the next N=2,
101       etc, the number of new cells added in the tree row is
102
103           rowwidth(depth) = 3^(count_1_bits(depth+1) - 1)
104
105       So depth=0 has 3^(1-1)=1 cells, as does depth=1 which is N=2.  Then
106       depth=2 has 3^(2-1)=3 cells N=3,N=4,N=5 because depth+1=3=0b11 has two
107       1 bits in binary.  The N row start and end is the cumulative total of
108       those before it,
109
110           Ndepth(depth) = 1 + rowwidth(0) + ... + rowwidth(depth-1)
111
112           Nend(depth) = rowwidth(0) + ... + rowwidth(depth)
113
114       For example depth=2 ends at N=(1+1+3)=5.
115
116           depth    Ndepth    rowwidth      Nend
117             0          1         1           1
118             1          2         1           2
119             2          3         3           5
120             3          6         1           6
121             4          7         3           9
122             5         10         3          12
123             6         13         9          21
124             7         22         1          22
125             8         23         3          25
126
127       At row depth+1 = power-of-2 the Ndepth sum is
128
129           Ndepth(depth) = 1 + (4^a-1)/3       for depth+1 = 2^a
130
131       For example depth=3 is depth+1=2^2 starts at N=1+(4^2-1)/3=6, or
132       depth=7 is depth+1=2^3 starts N=1+(4^3-1)/3=22.
133
134       Further bits in the depth+1 contribute powers-of-4 with a tripling for
135       each bit above it.  So if depth+1 has bits a,b,c,d,etc from high to low
136       then
137
138           depth+1 = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...
139           Ndepth = 1 + (-1
140                         +       4^a
141                         +   3 * 4^b
142                         + 3^2 * 4^c
143                         + 3^3 * 4^d + ...) / 3
144
145       For example depth=5 is depth+1=6 = 2^2+2^1 is Ndepth = 1+(4^2-1)/3 +
146       4^1 = 10.  Or depth=6 is depth+1=7 = 2^2+2^1+2^0 is Ndepth =
147       1+(4^2-1)/3 + 4^1 + 3*4^0 = 13.
148
149   Self-Similar Replication
150       The square shape growth to depth=2^level-2 repeats the pattern to the
151       preceding depth=2^(level-1)-2 three times.  For example,
152
153           |  d   d   c   c             depth=6 = 2^3-2
154           |    d       c               triplicates
155           |  d   d   c   c             depth=2 = 2^2-2
156           |        *
157           |  a   a   b   b
158           |    a       b
159           |  a   a   b   b
160           +--------------------
161
162       The 3x3 square "a" repeats, pointing SE, NE and NW as "b", "c" and "d".
163       This resulting 7x7 square then likewise repeats.  The points in the
164       path here are numbered by tree rows rather than by this sort of
165       replication, but the replication helps to see the structure of the
166       pattern.
167
168   Octant
169       Option "parts => 'octant'" confines the pattern to the first eighth of
170       the plane 0<=Y<=X.
171
172           parts => "octant"
173
174            14 |                                           50
175            13 |                                        36
176            12 |                                     31    49
177            11 |                                  26
178            10 |                               24    30    48
179             9 |                            19          35
180             8 |                         17    23    46    47
181             7 |                      15
182             6 |                   14    16    22    45    44
183             5 |                 9          18          34
184             4 |              7    13    20    21    29    43
185             3 |           5                      25
186             2 |        4     6    12    37    27    28    42
187             1 |     2           8          32          33
188           Y=0 |  1     3    10    11    38    39    40    41
189               +-------------------------------------------------
190                X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
191
192       In this arrangement N=1,2,4,5,7,etc on the leading diagonal is the last
193       N of each row ("tree_depth_to_n_end()").
194
195   Upper Octant
196       Option "parts => 'octant_up'" confines the pattern to the upper octant
197       0<=X<=Y of the first quadrant.
198
199           parts => "octant_up"
200
201            14 | 46    45    44    43    40    39    38    37
202            13 |    35          34          33          32
203            12 | 47    30    29    42    41    28    27
204            11 |          26                      25
205            10 | 48    31    23    22    21    20
206             9 |    36          19          18
207             8 | 49    50    24    17    16
208             7 |                      15
209             6 | 13    12    11    10
210             5 |     9           8
211             4 | 14     7     6
212             3 |           5
213             2 |  4     3
214             1 |     2
215           Y=0 |  1
216               +----------------------------------------------
217                 X=0 1  2  3  4  5  6  7  8  9 10 11 12 13 14
218
219       In this arrangement N=1,2,3,5,6,etc on the leading diagonal is the
220       first N of each row ("tree_depth_to_n()").
221
222   N Start
223       The default is to number points starting N=1 as shown above.  An
224       optional "n_start" can give a different start, in the same pattern.
225       For example to start at 0,
226
227           n_start => 0
228
229            7 |                      21
230            6 | 19    18    17    16
231            5 |    11          10
232            4 | 20     8     7    15
233            3 |           5
234            2 |  4     3     6    14
235            1 |     1           9
236           Y=0|  0     2    12    13
237              +-------------------------
238               X=0  1  2  3  4  5  6  7
239

FUNCTIONS

241       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
242       classes.
243
244       "$path = Math::PlanePath::UlamWarburtonQuarter->new ()"
245       "$path = Math::PlanePath::UlamWarburtonQuarter->new (parts => $str,
246       n_start => $n)"
247           Create and return a new path object.  "parts" can be
248
249               1              first quadrant, the default
250               "octant"       first eighth
251               "octant_up"    upper eighth
252
253   Tree Methods
254       "@n_children = $path->tree_n_children($n)"
255           Return the children of $n, or an empty list if $n has no children
256           (including when "$n < 1", ie. before the start of the path).
257
258           The children are the cells turned on adjacent to $n at the next
259           row.  The way points are numbered means that when there's multiple
260           children they're consecutive N values, for example at N=12 the
261           children 19,20,21.
262
263       "$n_parent = $path->tree_n_parent($n)"
264           Return the parent node of $n, or "undef" if "$n <= 1" (the start of
265           the path).
266
267   Tree Descriptive Methods
268       "@nums = $path->tree_num_children_list()"
269           Return a list of the possible number of children at the nodes of
270           $path.  This is the set of possible return values from
271           "tree_n_num_children()".
272
273               parts        tree_num_children_list()
274               -----        ------------------------
275                 1              0, 1,    3
276               octant           0, 1, 2, 3
277               octant_up        0, 1, 2, 3
278
279           The octant forms have 2 children when branching from the leading
280           diagonal, otherwise 0,1,3.
281
282   Level Methods
283       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
284           Return "($n_start, tree_depth_to_n_end(2**($level+1) - 2))".
285

OEIS

287       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
288       this path includes
289
290           <http://oeis.org/A151920> (etc)
291
292           parts=1  (the default)
293             A147610   num cells in row, tree_depth_to_width()
294             A151920   total cells to depth, tree_depth_to_n_end()
295
296           parts=octant,octant_up
297             A079318   num cells in row, tree_depth_to_width()
298

SEE ALSO

300       Math::PlanePath, Math::PlanePath::UlamWarburton,
301       Math::PlanePath::LCornerTree, Math::PlanePath::CellularRule
302
303       Math::PlanePath::SierpinskiTriangle (a similar binary ones-count
304       related calculation)
305

HOME PAGE

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

LICENSE

310       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
311       Kevin Ryde
312
313       This file is part of Math-PlanePath.
314
315       Math-PlanePath is free software; you can redistribute it and/or modify
316       it under the terms of the GNU General Public License as published by
317       the Free Software Foundation; either version 3, or (at your option) any
318       later version.
319
320       Math-PlanePath is distributed in the hope that it will be useful, but
321       WITHOUT ANY WARRANTY; without even the implied warranty of
322       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
323       General Public License for more details.
324
325       You should have received a copy of the GNU General Public License along
326       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
327
328
329
330perl v5.34.0                      2021-M0a7t-h2:2:PlanePath::UlamWarburtonQuarter(3)
Impressum