Math::PlanePath::SierpinskiTriangle -- self-similar triangular path traversal
use Math::PlanePath::SierpinskiTriangle; my $path = Math::PlanePath::SierpinskiTriangle->new; my ($x, $y) = $path->n_to_xy (123);
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= ... -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 path, rather than rows jumping across gaps.
The number of points in each row is always a power of 2. The power is the count of 1-bits in Y. For example Y=13 is binary 1101 which has three 1-bits so in row Y=13 there are 2^3=8 points. (This count is sometimes called Gould's sequence.)
rowpoints(Y) = 2^(count of 1 bits in Y)
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 N=31,35,41,47,etc on the left of the triangle at X=8,Y=8. This means in particular the primes fall predominately on the left side of the triangles and sub-triangles.
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^2-1=9. Each level doubles in size,
0 <= Y <= 2^level - 1 - 2^level + 1 <= X <= 2^level - 1
The optional align parameter controls how points are arranged relative to the Y axis. The default shown above is "triangular".
align
align=>"right" means points to the right of the axis, packed next to each other and so using an eighth of the plane.
align=>"right"
align => "right" 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=0 1 2 3 4 5 6 7
align=>"left" is similar but 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"
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
"diagonal" put 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
These diagonals visit all points X,Y where X and Y written in binary don't have any 1-bits in the same bit positions, ie. where X bitand Y == 0. For example X=13,Y=3 is not visited because 13=0b1011 and 6=0b0110 both have bit 0b0010 set.
This bit rule is an easy way to test for visited or not visited cells of the pattern. It can be calculated by this diagonal X,Y but then plotted X,X+Y for the "right" align or X-Y,X+Y for "triangular", as desired.
The triangle arises in Stephen Wolfram's CellularRule style 1-D cellular automaton (per Math::PlanePath::CellularRule).
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 make variations on the triangle. Rule 22 is "triangular" but filling the gap between leaf points such as N=5 and N=6. Or rule 126 adds an extra point on the inward side of each visited. And rule 182 fills in the big gaps leaving just a single-cell empty border delimiting them.
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
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
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"
$n = $path->n_start()
Return the first N in the path. This is 0 by default, or the given n_start parameter.
@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).
$n
$n < n_start
The children are the points diagonally up left and right on the next row. There can be 0, 1 or 2 such points. At even depth there's 2, on depth=1mod4 there's 1. On other depths 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.
$num = $path->tree_n_num_children($n)
Return the number of children of $n, or return undef if $n<n_start (ie. before the start of the path).
undef
$n<n_start
$n_parent = $path->tree_n_parent($n)
Return the parent node of $n, or undef if $n <= n_start (the top of the triangle).
$n <= n_start
$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_to_xy()
$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.
$depth
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).
xy_to_n(-$depth,$depth)
For calculation it's convenient to turn the X,Y coordinates into the "right" alignment style, so that Y is the depth and X in the range 0<=X<=Y.
The starting position of each row of the triangle is given turning bits of the depth into powers-of-3.
Y = depth = 2^a + 2^b + 2^c + 2^d ... a>b>c>d... Ndepth = 3^a first N at this depth + 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 width of the row on replicating.
Then the bits of X at the positions of the 1-bits in the depth become the Noffset offset into the row.
a b c d depth = 10010010010 binary X = m00n00p00q0 Noffset = mnpq N = Ndepth + Noffset
For example in depth=6 binary 110 then at X=4=100 take the bits of X where depth has 1s, 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 don't coincide with 1-bits in the depth then that X,Y is not visited. For example depth=6=0b110 X=3=0b11 is not visited because the low bit X=..1 but at that position depth=..0 is not a 1-bit.
The row containing N can be found by the Ndepth formula shown above. The "a" term is the highest 3^a <= N, thus giving a bit 2^a for the depth. Then the remainder Nrem = N - 3^a see 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 the prospective depth, deciding at each bit whether Nrem is big enough that the depth can have 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 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 Xright = a00bc0
For example in depth=5 this spreads out the Noffset bits to give Xright = 000, 001, 100, 101 in binary.
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
The number of children follows a pattern based on the depth.
depth number of children ----- ------------------ 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
At even depth all points have 2 children. For example the depth=6 row has four points all with 2 children each.
At odd depth the number of children is either 1 or 0 according to how the Noffset into the row matches the trailing 1-bits of the depth.
depth=...011111 in binary Noffset = ...00000 \ num children = 1 = ...11111 / = other num children = 0
For example depth=11 is binary 1011 which has low 1-bits "11". Those bits of Noffset must be either 00 or 11, so Noffset=..00 or ..11, but not 01 or 10. Hence the pattern 1,0,0,1,1,0,0,1 reading across the row.
In general when the depth doubles the triangle is replicated twice and the number of children is carried with it, but not the middle two points. For example the triangle of depth=0to3 is replicated twice to make depth=4to7, but the depth=7 row is not 10011001 of a plain doubling of the depth=3 row, but instead 10000001 which is the middle two points becoming 0.
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,
Nmin = N at -Ymin,Ymin Nmax = N at Ymax,Ymax
Or for less work but a bigger over-estimate, invert the Nlevel formulas given in "Row Ranges" above.
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 Y=8 to Y=15 replication.
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 Ndepth, cumulative number of cells up to row N A074330 Nend, right hand end of each row (starting Y=1)
A001316 is the "rowpoints" noted above. A006046 is the cumulative total of that sequence which is the "Ndepth" above, and A074330 is 1 less for "Nend".
A047999 0,1 cells by rows A106344 0,1 cells by upwards sloping dX=3,dY=1 align="right" A075438 0,1 cells by rows including 0 blanks at left of pyramid
A047999 is every second point in the default triangular lattice, or all points in align="right" or "left".
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 "right" alignment.
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
(See for example "Binary Trees" in Math::NumSeq::BalancedBinary on encoding trees as balanced binary.)
Math::PlanePath, Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::SierpinskiArrowheadCentres, Math::PlanePath::CellularRule
Math::NumSeq::SternDiatomic, Math::NumSeq::BalancedBinary
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012 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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.