1Math::PlanePath::SierpiUnssekriTCroinatnrgilbeu(t3e)d PeMralthD:o:cPulmaennetPaattiho:n:SierpinskiTriangle(3)
2
3
4

NAME

6       Math::PlanePath::SierpinskiTriangle -- self-similar triangular path
7       traversal
8

SYNOPSIS

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

DESCRIPTION

15       This path is an integer version of Sierpinski's triangle from
16
17           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
23       Unit triangles are numbered numbered horizontally across each row.
24
25           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
42                X= ... -9-8-7-6-5-4-3-2-1 0 1 2 3 4 5 6 7 8 9 ...
43
44       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
47           1  .  2
48              0
49
50       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
54       See the "SierpinskiArrowheadCentres" path to traverse by a connected
55       sequence rather than rows jumping across gaps.
56
57   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
62           rowpoints(Y) = 2^count_1_bits(Y)
63
64       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
67       Because the first point is N=0, the N at the left of each row is the
68       cumulative count of preceding points,
69
70           Ndepth(Y) = rowpoints(0) + ... + rowpoints(Y-1)
71
72       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
79   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
83           Nstart = 0
84           Nlevel = 3^level - 1     inclusive
85
86       For example level 2 is from N=0 to N=3^2-1=8.  Each level doubles in
87       size,
88
89                      0  <= Y <= 2^level - 1
90           - 2^level + 1 <= X <= 2^level - 1
91
92   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
96           align => "right"
97
98             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
109   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
114           align => "left"
115
116           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
127   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
132           align => "diagonal"
133
134            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
153       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
158       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
163   Cellular Automaton
164       The triangle arises in Stephen Wolfram's 1-D cellular automatons (per
165       Math::PlanePath::CellularRule and Cellular::Automata::Wolfram).
166
167           align           rule
168           -----           ----
169           "triangular"    18,26,82,90,146,154,210,218
170           "right"         60
171           "left"          102
172
173           <http://mathworld.wolfram.com/Rule90.html>
174
175           <http://mathworld.wolfram.com/Rule60.html>
176
177           <http://mathworld.wolfram.com/Rule102.html>
178
179       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
183       Some other cellular rules are variations on the triangle,
184
185       ·   Rule 22 is "triangular" but filling the gap between leaf points
186           such as N=5 and N=6.
187
188       ·   Rule 126 adds an extra point on the inward side of each visited.
189
190       ·   Rule 182 fills in the big gaps leaving just a single-cell empty
191           border delimiting them.
192
193   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
199           n_start => 1
200
201           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

FUNCTIONS

211       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
212       classes.
213
214       "$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
220               "triangular"    (the default)
221               "right"
222               "left"
223               "diagonal"
224
225   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
230   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
235           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
240           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
245       "$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
249       "$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
255       "$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
260           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
263   Level Methods
264       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
265           Return "(0, 3**$level - 1)".
266

FORMULAS

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
273       The starting position of each row of the triangle is given by turning
274       1-bits of the depth into powers-of-3.
275
276           Y = depth = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...
277
278           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
285       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
289       Then the bits of X at the positions of the 1-bits of the depth become
290       an N offset into the row.
291
292                      a  b  c  d
293           depth    = 10010010010     binary
294           X        = m00n00p00q0
295           Noffset  =        mnpq     binary
296
297           N = Ndepth + Noffset
298
299       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
303       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
307   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
314       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
318           a = floor(log3(N))     round down to power-of-3
319           pow = 3^a
320           Nrem = N - pow
321
322           depth = high 1-bit at bit position "a" (counting from 0)
323
324           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
331           factor is 2^count1bits(depth)
332           Noffset = Nrem     offset into row
333           0 <= Noffset < factor
334
335   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
340           depth   = 100110  binary
341           Noffset =    abc  binary
342           Xright  = a00bc0
343
344       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
347       From an X,Y in "right" alignment the other alignments are formed
348
349           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
356   N to Number of Children
357       The number of children follows a pattern based on the depth.
358
359           depth      number of children
360           -----      ------------------
361
362            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
376       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
379       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
383           depth  = ...011111 in binary, its trailing 1s
384
385           Noffset = ...00000   \ num children = 1
386                   = ...11111   /
387                   = ...other   num children = 0
388
389       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
394       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
401   N to Number of Siblings
402       Each node N has either 0 or 1 siblings.  This is determined by depth,
403
404           depth      number of siblings
405           -----      ------------------
406
407             4            0       0
408             3             1 1 1 1
409             2              0   0
410             1               1 1
411             0                0
412
413           depth     number of siblings
414           -----     ------------------
415            odd             1
416            even            0
417
418       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
422       In an odd row each parent node (an even row) has 2 children and so each
423       of those points has 1 sibling.
424
425       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
428           num children of N      num siblings of N
429           -----------------      -----------------
430                 0 or 1                   1
431                   2                      0
432
433   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
438           # align="triangular"
439           Nmin = N at X=-Ymin,Y=Ymin
440           Nmax = N at X=Ymax,Y=Ymax
441
442       Or in "right" style the left end is at X=0 instead,
443
444           # align="right"
445           Nmin = N at X=0,Ymin
446           Nmax = N at Ymax,Ymax
447
448       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
452           level = floor(log2(Ymax)) + 1
453           Nmax = 3^level - 1
454
455       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

OEIS

460       The Sierpinski triangle is in Sloane's Online Encyclopedia of Integer
461       Sequences in various forms,
462
463           <http://oeis.org/A001316> (etc)
464
465           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
470       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
474           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
479       A047999 etc is every second point in the default triangular lattice, or
480       all points in align="right" or "left".
481
482           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
487       dX=3,dY=1 sloping lines are equivalent to opposite-diagonals dX=-1,dY=1
488       in align="right".
489
490           align="right"
491             A075438   0,1 cells by rows including 0 blanks at left of pyramid
492
493           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
500           A080263   Dyck encoding of the tree structure
501           A080264     same in binary
502           A080265     position in list of all balanced binary
503
504           A080268   Dyck encoding breadth-first
505           A080269     same in binary
506           A080270     position in list of all balanced binary
507
508           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
513       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
517       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

SEE ALSO

524       Math::PlanePath, Math::PlanePath::SierpinskiArrowhead,
525       Math::PlanePath::SierpinskiArrowheadCentres,
526       Math::PlanePath::CellularRule, Math::PlanePath::ToothpickUpist
527
528       Math::NumSeq::SternDiatomic, Math::NumSeq::BalancedBinary
529

HOME PAGE

531       <http://user42.tuxfamily.org/math-planepath/index.html>
532

LICENSE

534       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
535
536       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
541       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
546       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/>.
548
549
550
551perl v5.32.0                      2020-07M-a2t8h::PlanePath::SierpinskiTriangle(3)
Impressum