1Math::PlanePath::UlamWaUrsbeurrtCoonnQturairbtuetre(d3M)Paetrhl::DPolcaunmeePnattaht:i:oUnlamWarburtonQuarter(3)
2
6 Math::PlanePath::UlamWarburtonQuarter -- growth of a 2-D cellular
7 automaton
8
10 use Math::PlanePath::UlamWarburtonQuarter;
11 my $path = Math::PlanePath::UlamWarburtonQuarter->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
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 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 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 |
43 | a initial cell, depth=0
44 +----
45 It's confined to the first quadrant so can only grow NE as "b",
47 | b
49 | a "b" depth=1
50 +------
51 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 | c c
57 | b
58 | a c "c" depth=2
59 +---------
60 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 | d
65 | c c depth=3
66 | b
67 | a c
68 +---------
69 | e e
71 | d
72 | c c e depth=4
73 | b
74 | a c
75 +-----------
76 | f f
78 | e e
79 | d
80 | c c e depth=5
81 | b f
82 | a c
83 +-------------
84 | 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 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 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 rowwidth(depth) = 3^(count_1_bits(depth+1) - 1)
104 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 Ndepth(depth) = 1 + rowwidth(0) + ... + rowwidth(depth-1)
111 Nend(depth) = rowwidth(0) + ... + rowwidth(depth)
113 For example depth=2 ends at N=(1+1+3)=5.
115 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 At row depth+1 = power-of-2 the Ndepth sum is
128 Ndepth(depth) = 1 + (4^a-1)/3 for depth+1 = 2^a
130 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 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 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 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 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 | 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 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 Octant
169 Option "parts => 'octant'" confines the pattern to the first eighth of
170 the plane 0<=Y<=X.
171 parts => "octant"
173 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 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 Upper Octant
196 Option "parts => 'octant_up'" confines the pattern to the upper octant
197 0<=X<=Y of the first quadrant.
198 parts => "octant_up"
200 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 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 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 n_start => 0
228 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
241 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
242 classes.
243 "$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 1 first quadrant, the default
250 "octant" first eighth
251 "octant_up" upper eighth
252 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 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 "$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 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 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 The octant forms have 2 children when branching from the leading
280 diagonal, otherwise 0,1,3.
281 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
287 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
288 this path includes
289 <http://oeis.org/A151920> (etc)
291 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 parts=octant,octant_up
297 A079318 num cells in row, tree_depth_to_width()
298
300 Math::PlanePath, Math::PlanePath::UlamWarburton,
301 Math::PlanePath::LCornerTree, Math::PlanePath::CellularRule
302 Math::PlanePath::SierpinskiTriangle (a similar binary ones-count
304 related calculation)
305
307 <http://user42.tuxfamily.org/math-planepath/index.html>
308
310 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
311 Kevin Ryde
312 This file is part of Math-PlanePath.
314 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 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 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/>.
327perl v5.34.0 2022-M0a1t-h2:1:PlanePath::UlamWarburtonQuarter(3)