and 1 contributors

# 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
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.

## Row Ranges

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.

## Level Sizes

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``````

## Cellular Automaton

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``

## OEIS

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.

# FUNCTIONS

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 to X,Y

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.

## Rectangle to N Range

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 "Level 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.