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 by 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. (These powers-of-2 are known as 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 after the 2^0=1 in row Y=0, the leftmost N is always odd, and the self-similar nature of the triangle means the same is true of the sub-triangles, like N=31,35,41,47,etc on the left of the X=8,Y=8 triangle. This means in particular the primes fall predominately on the left side of the triangles.
Counting the N=0,1,2 part as level 1, each 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 triangle arises in Stephen Wolfram's "rule 90" cellular automaton. In each row a cell turns on on if one but not both its diagonal predecessors are on, which is a mod 2 sum giving Pascal's triangle mod 2.
http://mathworld.wolfram.com/Rule90.html
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::SierpinskiTriangle->new ()
Create and return a new triangle path object.
($x,$y) = $path->n_to_xy ($n)
Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.
$n
$n < 0
Within a row the X position is given by choosing among the 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, then spread out across every second cell as Y-2*k. The N offset within the row is thus applied by using the bits of N to select which of the 1 bits of Y to select.
Since N increases upwards and to the right, the bottom-left and top-right corners are the N range for a rectangle if those corners are points on the triangular path.
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 left of Ymin and right 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/A047999 etc A001316 - number of cells in each row A001317 - row 0 or 1 as binary number A006046 - cumulative number of cells up to row N A047999 - rows of 0 or 1
A001316 is the "rowpoints" Gould's sequence noted above. A006046 is the cumulative which is the Nleft above.
The path uses every second point to make a triangular lattice (see "Triangular Lattice" in Math::PlanePath). The 0/1 pattern in A047999 of a row Y=k is therefore every second point X=-k, X=-k+2, X=-k+4, etc for k+1 many points through to X=k.
Math::PlanePath, Math::PlanePath::SierpinskiArrowhead, Math::PlanePath::SierpinskiArrowheadCentres
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.