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 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
0This 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.
Row Ranges
The number of points in each row is always a power of 2 according to the number 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 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,
Nleft(Y) = rowpoints(0) + ... + rowpoints(Y-1)Since the powers of 2 are always even except for 2^0=1 in row Y=0, this Nleft(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.
Level Sizes
Counting the N=0,1,2 part as level 1, each level goes from
Nstart = 0
Nlevel = 3^level - 1 inclusiveFor 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 - 1Align Parameter
An optional align parameter controls how the points are arranged relative to the Y axis. The default shown above is "triangular".
"right" means points to the right of the axis, packed next to each other and so using an eighth of the plane.
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"left" is similar but to the left of the Y axis, ie. into negative 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"diagonal" put rows on diagonals down from the Y axis to the X axis. This uses the whole of the first quadrant (with gaps).
align => "diagonal"
65 15
57 66 14
49 67 13
45 50 58 68 12
37 69 11
33 38 59 70 10
29 39 51 71 9
27 30 34 40 46 52 60 72 8
19 73 7
15 20 61 74 6
11 21 53 75 5
9 12 16 22 47 54 62 76 4
5 23 41 77 3
3 6 17 24 35 42 63 78 2
1 7 13 25 31 43 55 79 1
0 2 4 8 10 14 18 26 28 32 36 44 48 56 64 80 <- Y=0
X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15These diagonals visit all points X,Y where X and Y written in binary have 1-bits in different places, 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 generate 0 or 1 for visited or not visited cells of the pattern. It can be calculated by this diagonal X,Y but then plotted instead as X,X+Y for the "right" align or X-Y,X+Y for "triangular" if desired.
Cellular Automaton
The triangle arises in Stephen Wolfram's CellularRule style 1-D cellular automaton.
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.htmlIn 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 the "triangular" shape 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. And 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 can give a different start, with the same shape. For example starting at 1 (which is per 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
1FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::SierpinskiTriangle->new ()$path = Math::PlanePath::SierpinskiTriangle->new (align => $str)-
Create and return a new path object.
alignis a string, one of the following as described above."triangular" the default "right" "left" "diagonal" ($x,$y) = $path->n_to_xy ($n)-
Return the X,Y coordinates of point number
$non the path. Points begin at 0 and if$n < 0then the return is an empty list.
Tree Methods
@n_children = $path->tree_n_children($n)-
Return the children of
$n, or an empty list if$n < 1(ie. before the start of the path).The children are the none, one or two points diagonally up on the next row. For example N=3 has two children N=5,N=6. 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 0 if$nhas no children. $n_parent = $path->tree_n_parent($n)-
Return the parent node of
$n, orundefif$n <= 1(the top of the triangle).
FORMULAS
N to X,Y
Within a row the X position is given by choosing to keep or clear the 1-bits of Y. For example row Y=5 in binary is 0b101 and the positions of the cells within that row are k = 0b000, 0b001, 0b100, 0b101, and then spread out across every second cell as Y-2*k. The Noffset within the row is thus applied by using the bits of Noffset to select which of the 1 bits of Y to keep.
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 Nleft of Ymin and Nright of Ymax,
Nmin = N at -Ymin,Ymin
Nmax = N at Ymax,YmaxOr 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 - 1For 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.
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 row cells 0 or 1 as binary number
A006046 Nleft, cumulative number of cells up to row N
A074330 Nright, 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 "Nleft" above, and A074330 is 1 less for "Nright".
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 pyramidA047999 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 slopesdX=3,dY=1 sloping lines are equivalent to dX=-1,dY=1 anti-diagonals in "right" alignment.
SEE ALSO
Math::PlanePath, Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::SierpinskiArrowheadCentres, Math::PlanePath::CellularRule
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
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/>.