Provided by: libmath-planepath-perl_129-1_all bug

NAME

       Math::PlanePath::SierpinskiTriangle -- self-similar triangular path traversal

SYNOPSIS

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

DESCRIPTION

       This path is an integer version of Sierpinski's triangle from

           Waclaw Sierpinski, "Sur une Courbe Dont Tout Point est un Point de Ramification",
           Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, volume 160,
           January-June 1915, pages 302-305.
           <http://gallica.bnf.fr/ark:/12148/bpt6k31131/f302.image.langEN>

       Unit triangles are numbered numbered horizontally across each row.

           65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80   15
             57      58      59      60      61      62      63      64     14
               49  50          51  52          53  54          55  56       13
                 45              46              47              48         12
                   37  38  39  40                  41  42  43  44           11
                     33      34                      35      36             10
                       29  30                          31  32                9
                         27                              28                  8
                           19  20  21  22  23  24  25  26                    7
                             15      16      17      18                      6
                               11  12          13  14                        5
                                  9              10                          4
                                    5   6   7   8                            3
                                      3       4                              2
                                        1   2                                1
                                          0                             <- Y=0

                X= ... -9-8-7-6-5-4-3-2-1 0 1 2 3 4 5 6 7 8 9 ...

       The base figure is the first two rows shape N=0 to N=2.  Notice the middle "." position
       X=0,Y=1 is skipped

           1  .  2
              0

       This is replicated twice in the next row pair as N=3 to N=8.  Then the resulting four-row
       shape is replicated twice again in the next four-row group as N=9 to N=26, etc.

       See the "SierpinskiArrowheadCentres" path to traverse by a connected sequence rather than
       rows jumping across gaps.

   Row Ranges
       The number of points in each row is always a power of 2.  The power is the count of 1-bits
       in Y.  (This count is sometimes called Gould's sequence.)

           rowpoints(Y) = 2^count_1_bits(Y)

       For example Y=13 is binary 1101 which has three 1-bits so in row Y=13 there are 2^3=8
       points.

       Because the first point is N=0, the N at the left of each row is the cumulative count of
       preceding points,

           Ndepth(Y) = rowpoints(0) + ... + rowpoints(Y-1)

       Since the powers of 2 are always even except for 2^0=1 in row Y=0, this Ndepth(Y) total is
       always odd.  The self-similar nature of the triangle means the same is true of the sub-
       triangles, for example odd N=31,35,41,47,etc on the left of the triangle at X=8,Y=8.  This
       means in particular the primes (being odd) fall predominately on the left side of the
       triangles and sub-triangles.

   Replication Sizes
       Counting the single point N=0 as level=0, then N=0,1,2 as level 1, each replication level
       goes from

           Nstart = 0
           Nlevel = 3^level - 1     inclusive

       For example level 2 is from N=0 to N=3^2-1=8.  Each level doubles in size,

                      0  <= Y <= 2^level - 1
           - 2^level + 1 <= X <= 2^level - 1

   Align Right
       Optional "align=>"right"" puts points to the right of the Y axis, packed next to each
       other and so using an eighth of the plane.

           align => "right"

             7  | 19 20 21 22 23 24 25 26
             6  | 15    16    17    18
             5  | 11 12       13 14
             4  |  9          10
             3  |  5  6  7  8
             2  |  3     4
             1  |  1  2
           Y=0  |  0
                +-------------------------
                 X=0  1  2  3  4  5  6  7

   Align Left
       Optional "align=>"left"" puts points to the left of the Y axis, ie. into negative X.  The
       rows are still numbered starting from the left, so it's a shift across, not a negate of X.

           align => "left"

           19 20 21 22 23 24 25 26  |     7
              15    16    17    18  |     6
                 11 12       13 14  |     5
                     9          10  |     4
                        5  6  7  8  |     3
                           3     4  |     2
                              1  2  |     1
                                 0  | <- Y=0
           -------------------------+
           -7 -6 -5 -4 -3 -2 -1 X=0

   Align Diagonal
       Optional "align=>"diagonal"" puts rows on diagonals down from the Y axis to the X axis.
       This uses the whole of the first quadrant, with gaps according to the pattern.

           align => "diagonal"

            15 | 65       ...
            14 | 57 66
            13 | 49    67
            12 | 45 50 58 68
            11 | 37          69
            10 | 33 38       59 70
             9 | 29    39    51    71
             8 | 27 30 34 40 46 52 60 72
             7 | 19                      73
             6 | 15 20                   61 74
             5 | 11    21                53    75
             4 |  9 12 16 22             47 54 62 76
             3 |  5          23          41          77       ...
             2 |  3  6       17 24       35 42       63 78
             1 |  1     7    13    25    31    43    55    79
           Y=0 |  0  2  4  8 10 14 18 26 28 32 36 44 48 56 64 80
               +-------------------------------------------------
                X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

       This form visits all points X,Y where X and Y written in binary have no 1-bits in the same
       bit positions, ie. where X bitand Y == 0.  For example X=13,Y=3 is not visited because
       13="1011" and 6="0110" both have bit "0010" set.

       This bit-and rule is an easy way to test for visited or not visited cells of the pattern.
       The visited cells can be calculated by this diagonal X,Y bitand, but then plotted X,X+Y
       for the "right" align or X-Y,X+Y for "triangular".

   Cellular Automaton
       The triangle arises in Stephen Wolfram's 1-D cellular automatons (per
       Math::PlanePath::CellularRule and Cellular::Automata::Wolfram).

           align           rule
           -----           ----
           "triangular"    18,26,82,90,146,154,210,218
           "right"         60
           "left"          102

           <http://mathworld.wolfram.com/Rule90.html>

           <http://mathworld.wolfram.com/Rule60.html>

           <http://mathworld.wolfram.com/Rule102.html>

       In each row the rule 18 etc pattern turns a cell "on" in the next row if one but not both
       its diagonal predecessors are "on".  This is a mod 2 sum giving Pascal's triangle mod 2.

       Some other cellular rules are variations on the triangle,

       •   Rule 22 is "triangular" but filling the gap between leaf points such as N=5 and N=6.

       •   Rule 126 adds an extra point on the inward side of each visited.

       •   Rule 182 fills in the big gaps leaving just a single-cell empty border delimiting
           them.

   N Start
       The default is to number points starting N=0 as shown above.  An optional "n_start"
       parameter can give a different start, with the same shape.  For example starting at 1,
       which is the numbering of "CellularRule" rule=60,

           n_start => 1

           20    21    22    23    24    25    26    27
              16          17          18          19
                 12    13                14    15
                    10                      11
                        6     7     8     9
                           4           5
                              2     3
                                 1

FUNCTIONS

       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

       "$path = Math::PlanePath::SierpinskiTriangle->new ()"
       "$path = Math::PlanePath::SierpinskiTriangle->new (align => $str, n_start => $n)"
           Create and return a new path object.  "align" is a string, one of the following as
           described above.

               "triangular"    (the default)
               "right"
               "left"
               "diagonal"

   Descriptive Methods
       "$n = $path->n_start()"
           Return the first N in the path.  This is 0 by default, or the given "n_start"
           parameter.

   Tree Methods
       "@n_children = $path->tree_n_children($n)"
           Return the children of $n, or an empty list if "$n < n_start" (ie. before the start of
           the path).

           The children are the points diagonally up left and right on the next row (Y+1).  There
           can be 0, 1 or 2 such points.  At even depth there's 2, on depth=1mod4 there's 1.  On
           depth=3mod4 there's some 0s and some 1s.  See "N to Number of Children" below.

           For example N=3 has two children N=5,N=6.  Then in turn N=5 has just one child N=9 and
           N=6 has no children.  The way points are numbered across a row means that when there's
           two children they're consecutive N values.

       "$n_parent = $path->tree_n_parent($n)"
           Return the parent node of $n, or "undef" if "$n <= n_start" (the top of the triangle).

       "$depth = $path->tree_n_to_depth($n)"
           Return the depth of node $n, or "undef" if there's no point $n.  In the "triangular",
           "right" and "left" alignments this is the same as the Y coordinate from "n_to_xy()".
           In the "diagonal" alignment it's X+Y.

       "$n = $path->tree_depth_to_n($depth)"
       "$n = $path->tree_depth_to_n_end($depth)"
           Return the first or last N at tree level $depth.  The start of the tree is depth=0 at
           the origin X=0,Y=0.

           This is the N at the left end of each row.  So in the default triangular alignment
           it's the same as "xy_to_n(-$depth,$depth)".

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "(0, 3**$level - 1)".

FORMULAS

   X,Y to N
       For calculation it's convenient to turn the X,Y coordinates into the "right" alignment
       style, so that Y is the depth and X is in the range 0<=X<=Y.

       The starting position of each row of the triangle is given by turning 1-bits of the depth
       into powers-of-3.

           Y = depth = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...

           Ndepth = first N at this depth
                  =         3^a
                    +   2 * 3^b
                    + 2^2 * 3^c
                    + 2^3 * 3^d
                    + ...

       For example depth=6=2^2+2^1 starts at Ndepth=3^2+2*3^1=15.  The powers-of-3 are the three
       parts of the triangle replication.  The power-of-2 doubling is the doubling of the row Y
       when replicated.

       Then the bits of X at the positions of the 1-bits of the depth become an N offset into the
       row.

                      a  b  c  d
           depth    = 10010010010     binary
           X        = m00n00p00q0
           Noffset  =        mnpq     binary

           N = Ndepth + Noffset

       For example in depth=6 binary "110" then at X=4="100" take the bits of X where depth has
       1-bits, which is X="10_" so Noffset="10" binary and N=15+2=17, as per the "right" table
       above at X=4,Y=6.

       If X has any 1-bits which are a 0-bits in the depth depth then that X,Y is not visited.
       For example if depth=6="110" then X=3="11" is not visited because the low bit X="__1" has
       depth="__0" at that position.

   N to Depth
       The row containing N can be found by working down the Ndepth formula shown above.  The "a"
       term is the highest 3^a <= N, thus giving a bit 2^a for the depth.  Then for the remaining
       Nrem = N - 3^a find the highest "b" where 2*3^b <= Nrem.  And so on until reaching an Nrem
       which is too small to subtract any more terms.

       It's convenient to go by bits high to low of the prospective depth, deciding at each bit
       whether Nrem is big enough to give the depth a 1-bit there, or whether it must be a 0-bit.

           a = floor(log3(N))     round down to power-of-3
           pow = 3^a
           Nrem = N - pow

           depth = high 1-bit at bit position "a" (counting from 0)

           factor = 2
           loop bitpos a-1 down to 0
             pow /= 3
             if pow*factor <= Nrem
             then depth 0-bit, factor *= 2
             else depth 1-bit

           factor is 2^count1bits(depth)
           Noffset = Nrem     offset into row
           0 <= Noffset < factor

   N to X,Y
       N is turned into depth and Noffset as per above.  X in "right" alignment style is formed
       by spreading the bits of Noffset out according to the 1-bits of the depth.

           depth   = 100110  binary
           Noffset =    abc  binary
           Xright  = a00bc0

       For example in depth=5 this spreads an Noffset=0to3 to make X=000, 001, 100, 101 in binary
       and in "right" alignment style.

       From an X,Y in "right" alignment the other alignments are formed

           alignment   from "right" X,Y
           ---------   ----------------
           triangular     2*X-Y, Y       so -Y <= X < Y
           right          X,     Y       unchanged
           left           X-Y,   Y       so -Y <= X <= 0
           diagonal       X,   Y-X       downwards sloping

   N to Number of Children
       The number of children follows a pattern based on the depth.

           depth      number of children
           -----      ------------------

            12    2       2       2       2
            11     1 0 0 1         1 0 0 1
            10      2   2           2   2
             9       1 1             1 1
             8        2               2
             7         1 0 0 0 0 0 0 1
             6          2   2   2   2
             5           1 1     1 1
             4            2       2
             3             1 0 0 1
             2              2   2
             1               1 1
             0                2

       If depth is even then all points have 2 children.  For example row depth=6 has 4 points
       and all have 2 children each.

       At odd depth the number of children is either 1 or 0 according to the Noffset position in
       the row masked down by the trailing 1-bits of the depth.

           depth  = ...011111 in binary, its trailing 1s

           Noffset = ...00000   \ num children = 1
                   = ...11111   /
                   = ...other   num children = 0

       For example depth=11 is binary "1011" which has low 1-bits "11".  If those two low bits of
       Noffset are "00" or "11" then 1 child.  Any other bit pattern in Noffset ("01" or "10" in
       this case) is 0 children.  Hence the pattern 1,0,0,1,1,0,0,1 reading across the depth=11
       row.

       In general when the depth doubles the triangle is replicated twice and the number of
       children is carried with the replications, except the middle two points are 0 children.
       For example the triangle of depth=0to3 is repeated twice to make depth=4to7, but the
       depth=7 row is not children 10011001 of a plain doubling from the depth=3 row, but instead
       10000001 which is the middle two points becoming 0.

   N to Number of Siblings
       Each node N has either 0 or 1 siblings.  This is determined by depth,

           depth      number of siblings
           -----      ------------------

             4            0       0
             3             1 1 1 1
             2              0   0
             1               1 1
             0                0

           depth     number of siblings
           -----     ------------------
            odd             1
            even            0

       In an even row the points are all spread apart so there are no siblings.  The points in
       such a row are cousins or second cousins, etc, but none share a parent.

       In an odd row each parent node (an even row) has 2 children and so each of those points
       has 1 sibling.

       The effect is to conflate the NumChildren=1 and NumChildren=0 cases in the children
       picture above, those two becoming a single sibling.

           num children of N      num siblings of N
           -----------------      -----------------
                 0 or 1                   1
                   2                      0

   Rectangle to N Range
       An easy range can be had just from the Y range by noting the diagonals X=Y and X=-Y are
       always visited, so just take the Ndepth of Ymin and Nend of Ymax,

           # align="triangular"
           Nmin = N at X=-Ymin,Y=Ymin
           Nmax = N at X=Ymax,Y=Ymax

       Or in "right" style the left end is at X=0 instead,

           # align="right"
           Nmin = N at X=0,Ymin
           Nmax = N at Ymax,Ymax

       For less work but a bigger over-estimate, invert the Nlevel formulas given in "Row Ranges"
       above to round up to the end of a depth=2^k replication,

           level = floor(log2(Ymax)) + 1
           Nmax = 3^level - 1

       For example Y=11, level=floor(log2(11))+1=4, so Nmax=3^4-1=80, which is the end of the
       Y=15 row, ie. rounded up to the top of the replication block Y=8 to Y=15.

OEIS

       The Sierpinski triangle is in Sloane's Online Encyclopedia of Integer Sequences in various
       forms,

           <http://oeis.org/A001316> (etc)

           A001316   number of cells in each row (Gould's sequence)
           A001317   rows encoded as numbers with bits 0,1
           A006046   total cells to depth, being tree_depth_to_n(),
           A074330   Nend, right hand end of each row (starting Y=1)

       A001316 is the "rowpoints" described above.  A006046 is the cumulative total of that
       sequence which is the "Ndepth", and A074330 is 1 less for "Nend".

           align="triangular" (the default)
             A047999   0,1 cells by rows
             A106344   0,1 cells by upwards sloping dX=3,dY=1
             A130047   0,1 cells of half X<=0 by rows

       A047999 etc is every second point in the default triangular lattice, or all points in
       align="right" or "left".

           align="triangular" (the default)
             A002487   count points along dX=3,dY=1 slopes
                         is the Stern diatomic sequence
             A106345   count points along dX=5,dY=1 slopes

       dX=3,dY=1 sloping lines are equivalent to opposite-diagonals dX=-1,dY=1 in align="right".

           align="right"
             A075438   0,1 cells by rows including 0 blanks at left of pyramid

           align="right", n_start=0
             A006046   N on Y axis, being Ndepth
             A074330   N on Diagonal starting from Y=1, being Nend
           align="left", n_start=0
             A006046   N on NW diagonal, being Ndepth
             A074330   N on Y axis starting from Y=1, being Nend

           A080263   Dyck encoding of the tree structure
           A080264     same in binary
           A080265     position in list of all balanced binary

           A080268   Dyck encoding breadth-first
           A080269     same in binary
           A080270     position in list of all balanced binary

           A080318   Dyck encoding breadth-first of branch-reduced
                       (duplicate each bit)
           A080319     same in binary
           A080320     position in list of all balanced binary

       For the Dyck encoding see for example "Binary Trees" in Math::NumSeq::BalancedBinary.  The
       position in all balanced binary which is A080265 etc corresponds to "value_to_i()" in that
       "NumSeq".

       A branch-reduced tree has any single-child node collapsed out, so that all remaining nodes
       are either a leaf node or have 2 (or more) children.  The effect of this on the Sierpinski
       triangle in breadth-first encoding is to duplicate each bit, so A080269 with each bit
       repeated gives the branch-reduced A080319.

SEE ALSO

       Math::PlanePath, Math::PlanePath::SierpinskiArrowhead,
       Math::PlanePath::SierpinskiArrowheadCentres, Math::PlanePath::CellularRule,
       Math::PlanePath::ToothpickUpist

       Math::NumSeq::SternDiatomic, Math::NumSeq::BalancedBinary

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

       Math-PlanePath is free software; you can redistribute it and/or modify it under the terms
       of the GNU General Public License as published by the Free Software Foundation; either
       version 3, or (at your option) any later version.

       Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY
       WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
       PURPOSE.  See the GNU General Public License for more details.

       You should have received a copy of the GNU General Public License along with Math-
       PlanePath.  If not, see <http://www.gnu.org/licenses/>.