1Math::PlanePath::UlamWaUrsbeurrtCoonn(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::UlamWarburton(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

14       This is the pattern of a cellular automaton studied by Ulam and
15       Warburton, numbering cells by growth tree row and anti-clockwise within
16       the rows.
17
18                                      94                                  9
19                                   95 87 93                               8
20                                      63                                  7
21                                   64 42 62                               6
22                                65    30    61                            5
23                             66 43 31 23 29 41 60                         4
24                          69    67    14    59    57                      3
25                       70 44 68    15  7 13    58 40 56                   2
26              96    71    32    16     3    12    28    55    92          1
27           97 88 72 45 33 24 17  8  4  1  2  6 11 22 27 39 54 86 91   <- Y=0
28              98    73    34    18     5    10    26    53    90         -1
29                       74 46 76    19  9 21    50 38 52       ...        -2
30                          75    77    20    85    51                     -3
31                             78 47 35 25 37 49 84                        -4
32                                79    36    83                           -5
33                                   80 48 82                              -6
34                                      81                                 -7
35                                   99 89 101                             -8
36                                     100                                 -9
37
38                                      ^
39           -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6  7  8  9
40
41       The growth rule is that a given cell grows up, down, left and right,
42       but only if the new cell has no neighbours (up, down, left or right).
43       So the initial cell "a" is N=1,
44
45                       a                  initial depth=0 cell
46
47       The next row "b" cells are numbered N=2 to N=5 anti-clockwise from the
48       right,
49
50                       b
51                    b  a  b               depth=1
52                       b
53
54       Likewise the next row "c" cells N=6 to N=9.  The "b" cells only grow
55       outwards as 4 "c"s since the other positions would have neighbours in
56       the existing "b"s.
57
58                       c
59                       b
60                 c  b  a  b  c            depth=2
61                       b
62                       c
63
64       The "d" cells are then N=10 to N=21, numbered following the previous
65       row "c" cell order and then anti-clockwise around each.
66
67                       d
68                    d  c  d
69                 d     b     d
70              d  c  b  a  b  c  d         depth=3
71                 d     b     d
72                    d  c  d
73                       d
74
75       There's only 4 "e" cells since among the "d"s only the X,Y axes won't
76       have existing neighbours (the "b"s and "d"s).
77
78                       e
79                       d
80                    d  c  d
81                 d     b     d
82           e  d  c  b  a  b  c  d  e      depth=4
83                 d     b     d
84                    d  c  d
85                       d
86                       e
87
88       In general the pattern always grows by 1 outward along the X and Y axes
89       and travels into the quarter planes between with a diamond shaped tree
90       pattern which fills 11 of 16 cells in each 4x4 square block.
91
92   Tree Row Ranges
93       Counting depth=0 as the N=1 at the origin and depth=1 as the next
94       N=2,3,4,5 generation, the number of cells in a row is
95
96           rowwidth(0) = 1
97             then
98           rowwidth(depth) = 4 * 3^((count_1_bits(depth) - 1)
99
100       So depth=1 has 4*3^0=4 cells, as does depth=2 at N=6,7,8,9.  Then
101       depth=3 has 4*3^1=12 cells N=10 to N=21 because depth=3=0b11 has two
102       1-bits in binary.  The N start and end for a row is the cumulative
103       total of those before it,
104
105           Ndepth(depth) = 1 + (rowwidth(0) + ... + rowwidth(depth-1))
106
107           Nend(depth) = rowwidth(0) + ... + rowwidth(depth)
108
109       For example depth 3 ends at N=(1+4+4)=9.
110
111           depth    Ndepth   rowwidth     Nend
112             0          1         1           1
113             1          2         4           5
114             2          6         4           9
115             3         10        12          21
116             4         22         4          25
117             5         26        12          37
118             6         38        12          49
119             7         50        36          85
120             8         86         4          89
121             9         90        12         101
122
123       For a power-of-2 depth the Ndepth is
124
125           Ndepth(2^a) = 2 + 4*(4^a-1)/3
126
127       For example depth=4=2^2 starts at N=2+4*(4^2-1)/3=22, or depth=8=2^3
128       starts N=2+4*(4^3-1)/3=86.
129
130       Further bits in the depth value contribute powers-of-4 with a tripling
131       for each bit above.  So if the depth number has bits a,b,c,d,etc in
132       descending order,
133
134           depth = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...
135           Ndepth = 2 + 4*(-1
136                           +       4^a
137                           +   3 * 4^b
138                           + 3^2 * 4^c
139                           + 3^3 * 4^d + ... ) / 3
140
141       For example depth=6 = 2^2+2^1 is Ndepth = 2 + (1+4*(4^2-1)/3) + 4^(1+1)
142       = 38.  Or depth=7 = 2^2+2^1+2^0 is Ndepth = 1 + (1+4*(4^2-1)/3) +
143       4^(1+1) + 3*4^(0+1) = 50.
144
145   Self-Similar Replication
146       The diamond shape depth=1 to depth=2^level-1 repeats three times.  For
147       example an "a" part going to the right of the origin "O",
148
149                   d
150                 d d d
151           |   a   d   c
152         --O a a a * c c c ...
153           |   a   b   c
154                 b b b
155                   b
156
157       The 2x2 diamond shaped "a" repeats pointing up, down and right as "b",
158       "c" and "d".  This resulting 4x4 diamond then likewise repeats up, down
159       and right.  The same happens in the other quarters of the plane.
160
161       The points in the path here are numbered by tree rows rather than in
162       this sort of replication, but the replication helps to see the
163       structure of the pattern.
164
165   Half Plane
166       Option "parts => '2'" confines the pattern to the upper half plane
167       "Y>=0",
168
169           parts => "2"
170
171                             28                           6
172                             21                           5
173                       29 22 16 20 27                     4
174                             11                           3
175                 30       12  6 10       26               2
176                 23    13     3     9    19               1
177           31 24 17 14  7  4  1  2  5  8 15 18 25     <- Y=0
178           --------------------------------------
179           -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6
180
181       Points are still numbered anti-clockwise around so X axis
182       N=1,2,5,8,15,etc is the first of row depth=X.  X negative axis
183       N=1,4,7,14,etc is the last of row depth=-X.  For depth=0 point N=1 is
184       both the first and last of that row.
185
186       Within a row a line from point N to N+1 is always a 45-degree angle.
187       This is true of each 3 direct children, but also across groups of
188       children by symmetry.  For this parts=2 the lines from the last of one
189       row to the first of the next are horizontal, making an attractive
190       pattern of diagonals and then across to the next row horizontally.  For
191       parts=4 or parts=1 the last to first lines are at various different
192       slopes and so upsets the pattern.
193
194   One Quadrant
195       Option "parts => '1'" confines the pattern to the first quadrant,
196
197           parts => "1"  to depth=14
198
199           14  |  73
200           13  |  63
201           12  |  53 62 72
202           11  |  49
203           10  |  39 48       71
204            9  |  35    47    61
205            8  |  31 34 38 46 52 60 70
206            7  |  29    45    59
207            6  |  19 28       69          67
208            5  |  15    27                57
209            4  |  11 14 18 26       68 58 51 56 66
210            3  |   9    25    23          43
211            2  |   5  8    24 17 22    44 37 42       65
212            1  |   3     7    13    21    33    41    55
213           Y=0 |   1  2  4  6 10 12 16 20 30 32 36 40 50 54 64
214               +-----------------------------------------------
215                 X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
216
217       X axis N=1,2,4,6,10,etc is the first of each row X=depth.  Y axis
218       N=1,3,5,9,11,etc is the last similarly Y=depth.
219
220       In this arrangement, horizontal arms have even, N and vertical arms
221       have odd N.  For example the vertical at X=8 N=30,33,37,etc has N odd
222       from N=33 up and when it turns to horizontal at N=42 or N=56 it
223       switches to N even.  The children of N=66 are not shown but the
224       verticals from there are N=79 below and N=81 above and so switch to odd
225       again.
226
227       This odd/even pattern is true of N=2 horizontal and N=3 vertical and
228       thereafter is true due to each row having an even number of points and
229       the self-similar replications in the pattern,
230
231           |\          replication
232           | \            block 0 to 1 and 3
233           |3 \           and block 0 block 2 less sides
234           |----
235           |\ 2|\
236           | \ | \
237           |0 \|1 \
238           ---------
239
240       Block 0 is the base and is replicated as block 1 and in reverse as
241       block 3.  Block 2 is a further copy of block 0, but the two halves of
242       block 0 rotated inward 90 degrees, so the X axis of block 0 becomes the
243       vertical of block 2, and the Y axis of block 0 the horizontal of block
244       2.  Those axis parts are dropped since they're already covered by block
245       1 and 3 and dropping them flips the odd/even parity to match the
246       vertical/horizontal flip due to the 90-degree rotation.
247
248   Octant
249       Option "parts => 'octant'" confines the pattern to the first eighth of
250       the plane 0<=Y<=X.
251
252           parts => "octant"
253
254             7 |                         47     ...
255             6 |                      48 36 46
256             5 |                   49    31    45
257             4 |                50 37 32 27 30 35 44
258             3 |             14    51    24    43    41
259             2 |          15 10 13    25 20 23    42 34 40
260             1 |        5     8    12    18    22    29    39
261           Y=0 |  1  2  3  4  6  7  9 11 16 17 19 21 26 28 33 38
262               +-------------------------------------------------
263                X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
264
265       In this arrangement, N=1,2,3,4,6,7,etc on the X axis is the first N of
266       each row ("tree_depth_to_n()").
267
268   Upper Octant
269       Option "parts => 'octant_up'" confines the pattern to the upper octant
270       0<=X<=Y of the first quadrant.
271
272           parts => "octant_up"
273
274             8 | 16 17 19 22 26 29 34 42
275             7 | 15    21    28    41
276             6 | 10 14    38 33 40
277             5 |  8    13    39
278             4 |  6  7  9 12
279             3 |  5    11
280             2 |  3  4
281             1 |  2
282           Y=0 |  1
283               +--------------------------
284                 X=0 1  2  3  4  5  6  7
285
286       In this arrangement, N=1,2,3,5,6,8,etc on the Y axis the last N of each
287       row ("tree_depth_to_n_end()").
288
289   N Start
290       The default is to number points starting N=1 as shown above.  Option
291       "n_start" can give a different start, in the same pattern.  For example
292       to start at 0,
293
294           n_start => 0
295
296                          29                       5
297                       30 22 28                    4
298                          13                       3
299                       14  6 12                    2
300              31    15     2    11    27           1
301           32 23 16  7  3  0  1  5 10 21 26    <- Y=0
302              33    17     4     9    25          -1
303                       18  8 20       37          -2
304                          19                      -3
305                       34 24 36                   -4
306                          35                      -5
307
308                           ^
309           -5 -4 -3 -2 -1 X=0 1  2  3  4  5
310

FUNCTIONS

312       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
313       classes.
314
315       "$path = Math::PlanePath::UlamWarburton->new ()"
316       "$path = Math::PlanePath::UlamWarburton->new (parts => $str, n_start =>
317       $n)"
318           Create and return a new path object.  The "parts" option (a string)
319           can be
320
321               "4"     the default
322               "2"
323               "1"
324
325   Tree Methods
326       "@n_children = $path->tree_n_children($n)"
327           Return the children of $n, or an empty list if $n has no children
328           (including when "$n < 1", ie. before the start of the path).
329
330           The children are the cells turned on adjacent to $n at the next
331           row.  The way points are numbered means that when there's multiple
332           children they're consecutive N values, for example at N=6 the
333           children are 10,11,12.
334
335   Tree Descriptive Methods
336       "@nums = $path->tree_num_children_list()"
337           Return a list of the possible number of children in $path.  This is
338           the set of possible return values from "tree_n_num_children()".
339           The possible children varies with the "parts",
340
341               parts     tree_num_children_list()
342               -----     ------------------------
343                 4             0, 1,    3, 4        (the default)
344                 2             0, 1, 2, 3
345                 1             0, 1, 2, 3
346
347           parts=4 has 4 children at the origin N=0 and thereafter either 0, 1
348           or 3.
349
350           parts=2 and parts=1 can have 2 children on the boundaries where the
351           3rd child is chopped off, otherwise 0, 1 or 3.
352
353       "$n_parent = $path->tree_n_parent($n)"
354           Return the parent node of $n, or "undef" if "$n <= 1" (the start of
355           the path).
356
357   Level Methods
358       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
359           Return "$n_lo = $n_start" and
360
361               parts    $n_hi
362               -----    -----
363                 4      $n_start + (16*4**$level - 4) / 3
364                 2      $n_start + ( 8*4**$level - 5) / 3  +  2*2**$level
365                 1      $n_start + ( 4*4**$level - 4) / 3  +  2*2**$level
366
367           $n_hi is "tree_depth_to_n_end(2**($level+1) - 1".
368

OEIS

370       This cellular automaton is in Sloane's Online Encyclopedia of Integer
371       Sequences as
372
373           <http://oeis.org/A147562> (etc)
374
375           parts=4
376             A147562   total cells to depth, being tree_depth_to_n() n_start=0
377             A147582   added cells at depth
378             A264039   off cells >=2 neighbours ("poisoned")
379             A260490     increment
380             A264768   off cells, 4 neighbours ("surrounded")
381             A264769     increment
382
383           parts=2
384             A183060   total cells to depth=n in half plane
385             A183061   added cells at depth=n
386
387           parts=1
388             A151922   total cells to depth=n in quadrant
389             A079314   added cells at depth=n
390
391       The A147582 new cells sequence starts from n=1, so takes the innermost
392       N=1 single cell as row n=1, then N=2,3,4,5 as row n=2 with 5 cells,
393       etc.  This makes the formula a binary 1-bits count on n-1 rather than
394       on N the way rowwidth() above is expressed.
395
396       The 1-bits-count power 3^(count_1_bits(depth)) part of the rowwidth()
397       is also separately in A048883, and as n-1 in A147610.
398

SEE ALSO

400       Math::PlanePath, Math::PlanePath::UlamWarburtonQuarter,
401       Math::PlanePath::LCornerTree, Math::PlanePath::CellularRule
402
403       Math::PlanePath::SierpinskiTriangle (a similar binary 1s-count related
404       calculation)
405

HOME PAGE

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

LICENSE

410       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
411       Kevin Ryde
412
413       This file is part of Math-PlanePath.
414
415       Math-PlanePath is free software; you can redistribute it and/or modify
416       it under the terms of the GNU General Public License as published by
417       the Free Software Foundation; either version 3, or (at your option) any
418       later version.
419
420       Math-PlanePath is distributed in the hope that it will be useful, but
421       WITHOUT ANY WARRANTY; without even the implied warranty of
422       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
423       General Public License for more details.
424
425       You should have received a copy of the GNU General Public License along
426       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
427
428
429
430perl v5.32.1                      2021-01-27 Math::PlanePath::UlamWarburton(3)
Impressum