1Math::PlanePath::SierpiUnssekriTCroinatnrgilbeu(t3e)d PeMralthD:o:cPulmaennetPaattiho:n:SierpinskiTriangle(3)
2
6 Math::PlanePath::SierpinskiTriangle -- self-similar triangular path
7 traversal
8
10 use Math::PlanePath::SierpinskiTriangle;
11 my $path = Math::PlanePath::SierpinskiTriangle->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This path is an integer version of Sierpinski's triangle from
16 Waclaw Sierpinski, "Sur une Courbe Dont Tout Point est un Point de
18 Ramification", Comptes Rendus Hebdomadaires des Séances de
19 l'Académie des Sciences, volume 160, January-June 1915, pages
20 302-305.
21 <http://gallica.bnf.fr/ark:/12148/bpt6k31131/f302.image.langEN>
22 Unit triangles are numbered numbered horizontally across each row.
24 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 15
26 57 58 59 60 61 62 63 64 14
27 49 50 51 52 53 54 55 56 13
28 45 46 47 48 12
29 37 38 39 40 41 42 43 44 11
30 33 34 35 36 10
31 29 30 31 32 9
32 27 28 8
33 19 20 21 22 23 24 25 26 7
34 15 16 17 18 6
35 11 12 13 14 5
36 9 10 4
37 5 6 7 8 3
38 3 4 2
39 1 2 1
40 0 <- Y=0
41 X= ... -9-8-7-6-5-4-3-2-1 0 1 2 3 4 5 6 7 8 9 ...
43 The base figure is the first two rows shape N=0 to N=2. Notice the
45 middle "." position X=0,Y=1 is skipped
46 1 . 2
48 0
49 This is replicated twice in the next row pair as N=3 to N=8. Then the
51 resulting four-row shape is replicated twice again in the next four-row
52 group as N=9 to N=26, etc.
53 See the "SierpinskiArrowheadCentres" path to traverse by a connected
55 sequence rather than rows jumping across gaps.
56 Row Ranges
58 The number of points in each row is always a power of 2. The power is
59 the count of 1-bits in Y. (This count is sometimes called Gould's
60 sequence.)
61 rowpoints(Y) = 2^count_1_bits(Y)
63 For example Y=13 is binary 1101 which has three 1-bits so in row Y=13
65 there are 2^3=8 points.
66 Because the first point is N=0, the N at the left of each row is the
68 cumulative count of preceding points,
69 Ndepth(Y) = rowpoints(0) + ... + rowpoints(Y-1)
71 Since the powers of 2 are always even except for 2^0=1 in row Y=0, this
73 Ndepth(Y) total is always odd. The self-similar nature of the triangle
74 means the same is true of the sub-triangles, for example odd
75 N=31,35,41,47,etc on the left of the triangle at X=8,Y=8. This means
76 in particular the primes (being odd) fall predominately on the left
77 side of the triangles and sub-triangles.
78 Replication Sizes
80 Counting the single point N=0 as level=0, then N=0,1,2 as level 1, each
81 replication level goes from
82 Nstart = 0
84 Nlevel = 3^level - 1 inclusive
85 For example level 2 is from N=0 to N=3^2-1=8. Each level doubles in
87 size,
88 0 <= Y <= 2^level - 1
90 - 2^level + 1 <= X <= 2^level - 1
91 Align Right
93 Optional "align=>"right"" puts points to the right of the Y axis,
94 packed next to each other and so using an eighth of the plane.
95 align => "right"
97 7 | 19 20 21 22 23 24 25 26
99 6 | 15 16 17 18
100 5 | 11 12 13 14
101 4 | 9 10
102 3 | 5 6 7 8
103 2 | 3 4
104 1 | 1 2
105 Y=0 | 0
106 +-------------------------
107 X=0 1 2 3 4 5 6 7
108 Align Left
110 Optional "align=>"left"" puts points to the left of the Y axis, ie.
111 into negative X. The rows are still numbered starting from the left,
112 so it's a shift across, not a negate of X.
113 align => "left"
115 19 20 21 22 23 24 25 26 | 7
117 15 16 17 18 | 6
118 11 12 13 14 | 5
119 9 10 | 4
120 5 6 7 8 | 3
121 3 4 | 2
122 1 2 | 1
123 0 | <- Y=0
124 -------------------------+
125 -7 -6 -5 -4 -3 -2 -1 X=0
126 Align Diagonal
128 Optional "align=>"diagonal"" puts rows on diagonals down from the Y
129 axis to the X axis. This uses the whole of the first quadrant, with
130 gaps according to the pattern.
131 align => "diagonal"
133 15 | 65 ...
135 14 | 57 66
136 13 | 49 67
137 12 | 45 50 58 68
138 11 | 37 69
139 10 | 33 38 59 70
140 9 | 29 39 51 71
141 8 | 27 30 34 40 46 52 60 72
142 7 | 19 73
143 6 | 15 20 61 74
144 5 | 11 21 53 75
145 4 | 9 12 16 22 47 54 62 76
146 3 | 5 23 41 77 ...
147 2 | 3 6 17 24 35 42 63 78
148 1 | 1 7 13 25 31 43 55 79
149 Y=0 | 0 2 4 8 10 14 18 26 28 32 36 44 48 56 64 80
150 +-------------------------------------------------
151 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
152 This form visits all points X,Y where X and Y written in binary have no
154 1-bits in the same bit positions, ie. where X bitand Y == 0. For
155 example X=13,Y=3 is not visited because 13="1011" and 6="0110" both
156 have bit "0010" set.
157 This bit-and rule is an easy way to test for visited or not visited
159 cells of the pattern. The visited cells can be calculated by this
160 diagonal X,Y bitand, but then plotted X,X+Y for the "right" align or
161 X-Y,X+Y for "triangular".
162 Cellular Automaton
164 The triangle arises in Stephen Wolfram's 1-D cellular automatons (per
165 Math::PlanePath::CellularRule and Cellular::Automata::Wolfram).
166 align rule
168 ----- ----
169 "triangular" 18,26,82,90,146,154,210,218
170 "right" 60
171 "left" 102
172 <http://mathworld.wolfram.com/Rule90.html>
174 <http://mathworld.wolfram.com/Rule60.html>
176 <http://mathworld.wolfram.com/Rule102.html>
178 In each row the rule 18 etc pattern turns a cell "on" in the next row
180 if one but not both its diagonal predecessors are "on". This is a mod
181 2 sum giving Pascal's triangle mod 2.
182 Some other cellular rules are variations on the triangle,
184 · Rule 22 is "triangular" but filling the gap between leaf points
186 such as N=5 and N=6.
187 · Rule 126 adds an extra point on the inward side of each visited.
189 · Rule 182 fills in the big gaps leaving just a single-cell empty
191 border delimiting them.
192 N Start
194 The default is to number points starting N=0 as shown above. An
195 optional "n_start" parameter can give a different start, with the same
196 shape. For example starting at 1, which is the numbering of
197 "CellularRule" rule=60,
198 n_start => 1
200 20 21 22 23 24 25 26 27
202 16 17 18 19
203 12 13 14 15
204 10 11
205 6 7 8 9
206 4 5
207 2 3
208 1
209
211 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
212 classes.
213 "$path = Math::PlanePath::SierpinskiTriangle->new ()"
215 "$path = Math::PlanePath::SierpinskiTriangle->new (align => $str,
216 n_start => $n)"
217 Create and return a new path object. "align" is a string, one of
218 the following as described above.
219 "triangular" (the default)
221 "right"
222 "left"
223 "diagonal"
224 Descriptive Methods
226 "$n = $path->n_start()"
227 Return the first N in the path. This is 0 by default, or the given
228 "n_start" parameter.
229 Tree Methods
231 "@n_children = $path->tree_n_children($n)"
232 Return the children of $n, or an empty list if "$n < n_start" (ie.
233 before the start of the path).
234 The children are the points diagonally up left and right on the
236 next row (Y+1). There can be 0, 1 or 2 such points. At even depth
237 there's 2, on depth=1mod4 there's 1. On depth=3mod4 there's some
238 0s and some 1s. See "N to Number of Children" below.
239 For example N=3 has two children N=5,N=6. Then in turn N=5 has
241 just one child N=9 and N=6 has no children. The way points are
242 numbered across a row means that when there's two children they're
243 consecutive N values.
244 "$n_parent = $path->tree_n_parent($n)"
246 Return the parent node of $n, or "undef" if "$n <= n_start" (the
247 top of the triangle).
248 "$depth = $path->tree_n_to_depth($n)"
250 Return the depth of node $n, or "undef" if there's no point $n. In
251 the "triangular", "right" and "left" alignments this is the same as
252 the Y coordinate from "n_to_xy()". In the "diagonal" alignment
253 it's X+Y.
254 "$n = $path->tree_depth_to_n($depth)"
256 "$n = $path->tree_depth_to_n_end($depth)"
257 Return the first or last N at tree level $depth. The start of the
258 tree is depth=0 at the origin X=0,Y=0.
259 This is the N at the left end of each row. So in the default
261 triangular alignment it's the same as "xy_to_n(-$depth,$depth)".
262 Level Methods
264 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
265 Return "(0, 3**$level - 1)".
266
268 X,Y to N
269 For calculation it's convenient to turn the X,Y coordinates into the
270 "right" alignment style, so that Y is the depth and X is in the range
271 0<=X<=Y.
272 The starting position of each row of the triangle is given by turning
274 1-bits of the depth into powers-of-3.
275 Y = depth = 2^a + 2^b + 2^c + 2^d ... a>b>c>d...
277 Ndepth = first N at this depth
279 = 3^a
280 + 2 * 3^b
281 + 2^2 * 3^c
282 + 2^3 * 3^d
283 + ...
284 For example depth=6=2^2+2^1 starts at Ndepth=3^2+2*3^1=15. The
286 powers-of-3 are the three parts of the triangle replication. The
287 power-of-2 doubling is the doubling of the row Y when replicated.
288 Then the bits of X at the positions of the 1-bits of the depth become
290 an N offset into the row.
291 a b c d
293 depth = 10010010010 binary
294 X = m00n00p00q0
295 Noffset = mnpq binary
296 N = Ndepth + Noffset
298 For example in depth=6 binary "110" then at X=4="100" take the bits of
300 X where depth has 1-bits, which is X="10_" so Noffset="10" binary and
301 N=15+2=17, as per the "right" table above at X=4,Y=6.
302 If X has any 1-bits which are a 0-bits in the depth depth then that X,Y
304 is not visited. For example if depth=6="110" then X=3="11" is not
305 visited because the low bit X="__1" has depth="__0" at that position.
306 N to Depth
308 The row containing N can be found by working down the Ndepth formula
309 shown above. The "a" term is the highest 3^a <= N, thus giving a bit
310 2^a for the depth. Then for the remaining Nrem = N - 3^a find the
311 highest "b" where 2*3^b <= Nrem. And so on until reaching an Nrem
312 which is too small to subtract any more terms.
313 It's convenient to go by bits high to low of the prospective depth,
315 deciding at each bit whether Nrem is big enough to give the depth a
316 1-bit there, or whether it must be a 0-bit.
317 a = floor(log3(N)) round down to power-of-3
319 pow = 3^a
320 Nrem = N - pow
321 depth = high 1-bit at bit position "a" (counting from 0)
323 factor = 2
325 loop bitpos a-1 down to 0
326 pow /= 3
327 if pow*factor <= Nrem
328 then depth 0-bit, factor *= 2
329 else depth 1-bit
330 factor is 2^count1bits(depth)
332 Noffset = Nrem offset into row
333 0 <= Noffset < factor
334 N to X,Y
336 N is turned into depth and Noffset as per above. X in "right"
337 alignment style is formed by spreading the bits of Noffset out
338 according to the 1-bits of the depth.
339 depth = 100110 binary
341 Noffset = abc binary
342 Xright = a00bc0
343 For example in depth=5 this spreads an Noffset=0to3 to make X=000, 001,
345 100, 101 in binary and in "right" alignment style.
346 From an X,Y in "right" alignment the other alignments are formed
348 alignment from "right" X,Y
350 --------- ----------------
351 triangular 2*X-Y, Y so -Y <= X < Y
352 right X, Y unchanged
353 left X-Y, Y so -Y <= X <= 0
354 diagonal X, Y-X downwards sloping
355 N to Number of Children
357 The number of children follows a pattern based on the depth.
358 depth number of children
360 ----- ------------------
361 12 2 2 2 2
363 11 1 0 0 1 1 0 0 1
364 10 2 2 2 2
365 9 1 1 1 1
366 8 2 2
367 7 1 0 0 0 0 0 0 1
368 6 2 2 2 2
369 5 1 1 1 1
370 4 2 2
371 3 1 0 0 1
372 2 2 2
373 1 1 1
374 0 2
375 If depth is even then all points have 2 children. For example row
377 depth=6 has 4 points and all have 2 children each.
378 At odd depth the number of children is either 1 or 0 according to the
380 Noffset position in the row masked down by the trailing 1-bits of the
381 depth.
382 depth = ...011111 in binary, its trailing 1s
384 Noffset = ...00000 \ num children = 1
386 = ...11111 /
387 = ...other num children = 0
388 For example depth=11 is binary "1011" which has low 1-bits "11". If
390 those two low bits of Noffset are "00" or "11" then 1 child. Any other
391 bit pattern in Noffset ("01" or "10" in this case) is 0 children.
392 Hence the pattern 1,0,0,1,1,0,0,1 reading across the depth=11 row.
393 In general when the depth doubles the triangle is replicated twice and
395 the number of children is carried with the replications, except the
396 middle two points are 0 children. For example the triangle of
397 depth=0to3 is repeated twice to make depth=4to7, but the depth=7 row is
398 not children 10011001 of a plain doubling from the depth=3 row, but
399 instead 10000001 which is the middle two points becoming 0.
400 N to Number of Siblings
402 Each node N has either 0 or 1 siblings. This is determined by depth,
403 depth number of siblings
405 ----- ------------------
406 4 0 0
408 3 1 1 1 1
409 2 0 0
410 1 1 1
411 0 0
412 depth number of siblings
414 ----- ------------------
415 odd 1
416 even 0
417 In an even row the points are all spread apart so there are no
419 siblings. The points in such a row are cousins or second cousins, etc,
420 but none share a parent.
421 In an odd row each parent node (an even row) has 2 children and so each
423 of those points has 1 sibling.
424 The effect is to conflate the NumChildren=1 and NumChildren=0 cases in
426 the children picture above, those two becoming a single sibling.
427 num children of N num siblings of N
429 ----------------- -----------------
430 0 or 1 1
431 2 0
432 Rectangle to N Range
434 An easy range can be had just from the Y range by noting the diagonals
435 X=Y and X=-Y are always visited, so just take the Ndepth of Ymin and
436 Nend of Ymax,
437 # align="triangular"
439 Nmin = N at X=-Ymin,Y=Ymin
440 Nmax = N at X=Ymax,Y=Ymax
441 Or in "right" style the left end is at X=0 instead,
443 # align="right"
445 Nmin = N at X=0,Ymin
446 Nmax = N at Ymax,Ymax
447 For less work but a bigger over-estimate, invert the Nlevel formulas
449 given in "Row Ranges" above to round up to the end of a depth=2^k
450 replication,
451 level = floor(log2(Ymax)) + 1
453 Nmax = 3^level - 1
454 For example Y=11, level=floor(log2(11))+1=4, so Nmax=3^4-1=80, which is
456 the end of the Y=15 row, ie. rounded up to the top of the replication
457 block Y=8 to Y=15.
458
460 The Sierpinski triangle is in Sloane's Online Encyclopedia of Integer
461 Sequences in various forms,
462 <http://oeis.org/A001316> (etc)
464 A001316 number of cells in each row (Gould's sequence)
466 A001317 rows encoded as numbers with bits 0,1
467 A006046 total cells to depth, being tree_depth_to_n(),
468 A074330 Nend, right hand end of each row (starting Y=1)
469 A001316 is the "rowpoints" described above. A006046 is the cumulative
471 total of that sequence which is the "Ndepth", and A074330 is 1 less for
472 "Nend".
473 align="triangular" (the default)
475 A047999 0,1 cells by rows
476 A106344 0,1 cells by upwards sloping dX=3,dY=1
477 A130047 0,1 cells of half X<=0 by rows
478 A047999 etc is every second point in the default triangular lattice, or
480 all points in align="right" or "left".
481 align="triangular" (the default)
483 A002487 count points along dX=3,dY=1 slopes
484 is the Stern diatomic sequence
485 A106345 count points along dX=5,dY=1 slopes
486 dX=3,dY=1 sloping lines are equivalent to opposite-diagonals dX=-1,dY=1
488 in align="right".
489 align="right"
491 A075438 0,1 cells by rows including 0 blanks at left of pyramid
492 align="right", n_start=0
494 A006046 N on Y axis, being Ndepth
495 A074330 N on Diagonal starting from Y=1, being Nend
496 align="left", n_start=0
497 A006046 N on NW diagonal, being Ndepth
498 A074330 N on Y axis starting from Y=1, being Nend
499 A080263 Dyck encoding of the tree structure
501 A080264 same in binary
502 A080265 position in list of all balanced binary
503 A080268 Dyck encoding breadth-first
505 A080269 same in binary
506 A080270 position in list of all balanced binary
507 A080318 Dyck encoding breadth-first of branch-reduced
509 (duplicate each bit)
510 A080319 same in binary
511 A080320 position in list of all balanced binary
512 For the Dyck encoding see for example "Binary Trees" in
514 Math::NumSeq::BalancedBinary. The position in all balanced binary
515 which is A080265 etc corresponds to "value_to_i()" in that "NumSeq".
516 A branch-reduced tree has any single-child node collapsed out, so that
518 all remaining nodes are either a leaf node or have 2 (or more)
519 children. The effect of this on the Sierpinski triangle in breadth-
520 first encoding is to duplicate each bit, so A080269 with each bit
521 repeated gives the branch-reduced A080319.
522
524 Math::PlanePath, Math::PlanePath::SierpinskiArrowhead,
525 Math::PlanePath::SierpinskiArrowheadCentres,
526 Math::PlanePath::CellularRule, Math::PlanePath::ToothpickUpist
527 Math::NumSeq::SternDiatomic, Math::NumSeq::BalancedBinary
529
531 <http://user42.tuxfamily.org/math-planepath/index.html>
532
534 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
535 Math-PlanePath is free software; you can redistribute it and/or modify
537 it under the terms of the GNU General Public License as published by
538 the Free Software Foundation; either version 3, or (at your option) any
539 later version.
540 Math-PlanePath is distributed in the hope that it will be useful, but
542 WITHOUT ANY WARRANTY; without even the implied warranty of
543 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
544 General Public License for more details.
545 You should have received a copy of the GNU General Public License along
547 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
548perl v5.30.0 2019-08M-a1t7h::PlanePath::SierpinskiTriangle(3)