1Math::PlanePath::UlamWaUrsbeurrtCoonn(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::UlamWarburton(3)
2
6 Math::PlanePath::UlamWarburton -- growth of a 2-D cellular automaton
7
9 use Math::PlanePath::UlamWarburton;
10 my $path = Math::PlanePath::UlamWarburton->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
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 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 ^
39 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
40 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 a initial depth=0 cell
46 The next row "b" cells are numbered N=2 to N=5 anti-clockwise from the
48 right,
49 b
51 b a b depth=1
52 b
53 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 c
59 b
60 c b a b c depth=2
61 b
62 c
63 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 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 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 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 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 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 rowwidth(0) = 1
97 then
98 rowwidth(depth) = 4 * 3^((count_1_bits(depth) - 1)
99 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 Ndepth(depth) = 1 + (rowwidth(0) + ... + rowwidth(depth-1))
106 Nend(depth) = rowwidth(0) + ... + rowwidth(depth)
108 For example depth 3 ends at N=(1+4+4)=9.
110 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 For a power-of-2 depth the Ndepth is
124 Ndepth(2^a) = 2 + 4*(4^a-1)/3
126 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 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 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 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 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 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 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 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 Half Plane
166 Option "parts => '2'" confines the pattern to the upper half plane
167 "Y>=0",
168 parts => "2"
170 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 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 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 One Quadrant
195 Option "parts => '1'" confines the pattern to the first quadrant,
196 parts => "1" to depth=14
198 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 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 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 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 |\ 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 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 Octant
249 Option "parts => 'octant'" confines the pattern to the first eighth of
250 the plane 0<=Y<=X.
251 parts => "octant"
253 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 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 Upper Octant
269 Option "parts => 'octant_up'" confines the pattern to the upper octant
270 0<=X<=Y of the first quadrant.
271 parts => "octant_up"
273 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 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 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 n_start => 0
295 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 ^
309 -5 -4 -3 -2 -1 X=0 1 2 3 4 5
310
312 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
313 classes.
314 "$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 "4" the default
322 "2"
323 "1"
324 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 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 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 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 parts=4 has 4 children at the origin N=0 and thereafter either 0, 1
348 or 3.
349 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 "$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 Level Methods
358 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
359 Return "$n_lo = $n_start" and
360 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 $n_hi is "tree_depth_to_n_end(2**($level+1) - 1".
368
370 This cellular automaton is in Sloane's Online Encyclopedia of Integer
371 Sequences as
372 <http://oeis.org/A147562> (etc)
374 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 parts=2
384 A183060 total cells to depth=n in half plane
385 A183061 added cells at depth=n
386 parts=1
388 A151922 total cells to depth=n in quadrant
389 A079314 added cells at depth=n
390 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 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
400 Math::PlanePath, Math::PlanePath::UlamWarburtonQuarter,
401 Math::PlanePath::LCornerTree, Math::PlanePath::CellularRule
402 Math::PlanePath::SierpinskiTriangle (a similar binary 1s-count related
404 calculation)
405
407 <http://user42.tuxfamily.org/math-planepath/index.html>
408
410 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
411 Kevin Ryde
412 This file is part of Math-PlanePath.
414 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 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 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/>.
427perl v5.34.0 2021-07-22 Math::PlanePath::UlamWarburton(3)