NAME
Math::PlanePath::SierpinskiTriangle  selfsimilar triangular path traversal
SYNOPSIS
use Math::PlanePath::SierpinskiTriangle;
my $path = Math::PlanePath::SierpinskiTriangle>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This is an integer version of the Sierpinski triangle with cells 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= ... 987654321 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 fourrow shape is replicated twice again in the next fourrow 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 1bits in Y. (This count is sometimes called Gould's sequence.)
rowpoints(Y) = 2^(count of 1 bits in Y)
For example Y=13 is binary 1101 which has three 1bits 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(Y1)
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 selfsimilar nature of the triangle means the same is true of the subtriangles, 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 subtriangles.
Replication Sizes
Counting the N=0,1,2 part 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^21=9. 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 1bits 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 bitand 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 XY,X+Y for "triangular".
Cellular Automaton
The triangle arises in Stephen Wolfram's 1D 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
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 singlecell 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
, orundef
if$n <= n_start
(the top of the triangle). $depth = $path>tree_n_to_depth($n)

Return the depth of node
$n
, orundef
if there's no point$n
. In the "triangular", "right" and "left" alignments this is the same as the Y coordinate fromn_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)
.
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 1bits of the depth into powersof3.
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 powersof3 are the three parts of the triangle replication. The powerof2 doubling is the doubling of the row Y when replicated.
Then the bits of X at the positions of the 1bits 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 1bits, 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 1bits which are a 0bits 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 1bit there, or whether it must be a 0bit.
a = floor(log3(N)) round down to powerof3
pow = 3^a
Nrem = N  pow
depth = high 1bit at bit position "a" (counting from 0)
factor = 2
loop bitpos a1 down to 0
pow /= 3
if pow*factor <= Nrem
then depth 0bit, factor *= 2
else depth 1bit
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 1bits 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*XY, Y so Y <= X < Y
right X, Y unchanged
left XY, Y so Y <= X <= 0
diagonal X, YX 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 all with 2 children each.
At odd depth the number of children is either 1 or 0 according to Noffset masked down by the trailing 1bits 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 1bits "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
The number of siblings of a given node is determined by its 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 point has 1 sibling.
The effect is to conflate the NumChildren=1 and NumChildren=0 cases in the 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 overestimate, 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^41=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 oppositediagonals 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 breadthfirst
A080269 same in binary
A080270 position in list of all balanced binary
A080318 Dyck encoding breadthfirst of branchreduced
(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 branchreduced tree has any singlechild 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 breadthfirst encoding is to duplicate each bit, so A080269 with each bit repeated gives the branchreduced 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/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014 Kevin Ryde
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.