and 1 contributors

# NAME

Math::PlanePath::SierpinskiCurveStair -- Sierpinski curve with stair-step diagonals

# SYNOPSIS

`````` use Math::PlanePath::SierpinskiCurveStair;
my \$path = Math::PlanePath::SierpinskiCurveStair->new (arms => 2);
my (\$x, \$y) = \$path->n_to_xy (123);``````

# DESCRIPTION

This is a variation on the `SierpinskiCurve` with stair-step diagonal parts.

``````    10  |                                  52-53
|                                   |  |
9  |                               50-51 54-55
|                                |        |
8  |                               49-48 57-56
|                                   |  |
7  |                         42-43 46-47 58-59 62-63
|                          |  |  |        |  |  |
6  |                      40-41 44-45       60-61 64-65
|                       |                          |
5  |                      39-38 35-34       71-70 67-66
|                          |  |  |        |  |  |
4  |                12-13    37-36 33-32 73-72 69-68    92-93
|                 |  |              |  |              |  |
3  |             10-11 14-15       30-31 74-75       90-91 94-95
|              |        |        |        |        |        |
2  |              9--8 17-16       29-28 77-76       89-88 97-96
|                 |  |              |  |              |  |
1  |        2--3  6--7 18-19 22-23 26-27 78-79 82-83 86-87 98-99
|        |  |  |        |  |  |  |        |  |  |  |        |
Y=0 |     0--1  4--5       20-21 24-25       80-81 84-85       ...
|
+-------------------------------------------------------------
^
X=0 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19``````

The tiling is the same as the `SierpinskiCurve`, but each diagonal is a stair step horizontal and vertical. The correspondence is

``````    SierpinskiCurve        SierpinskiCurveStair

7--                   12--
/                        |
6                     10-11
|                      |
5                      9--8
\                        |
1--2     4             2--3  6--7
/     \  /               |  |  |
0        3             0--1  4--5``````

The `SierpinskiCurve` N=0 to N=3 corresponds to N=0 to N=5 here. N=7 to N=12 which is a copy of the N=0 to N=5 base. Point N=6 is an extra in between the parts. The next such extra is N=19.

## Diagonal Length

The `diagonal_length` option can make longer diagonals, still in stair-step style. For example

``````             diagonal_length => 4
10  |                                 36-37
|                                  |  |
9  |                              34-35 38-39
|                               |        |
8  |                           32-33       40-41
|                            |              |
7  |                        30-31             42-43
|                         |                    |
6  |                     28-29                   44-45
|                      |                          |
5  |                     27-26                   47-46
|                         |                    |
4  |                8--9    25-24             49-48    ...
|                |  |        |              |        |
3  |             6--7 10-11    23-22       51-50    62-63
|             |        |        |        |        |
2  |          4--5       12-13    21-20 53-52    60-61
|          |              |        |  |        |
1  |       2--3             14-15 18-19 54-55 58-59
|       |                    |  |        |  |
Y=0 |    0--1                   16-17       56-57
|
+------------------------------------------------------
^
X=0 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17``````

The length is reckoned from N=0 to the end of the first side N=8, which is X=1 to X=5 for length 4 units.

## Arms

The optional `arms` parameter can give up to eight copies of the curve, each advancing successively. For example

``````    arms => 8

98-90 66-58       57-65 89-97            5
|  |  |        |  |  |
99    82-74 50-42 41-49 73-81    96         4
|              |  |              |
91-83       26-34 33-25       80-88         3
|        |        |        |
67-75       18-10  9-17       72-64         2
|              |  |              |
59-51 27-19     2  1    16-24 48-56         1
|  |  |              |  |  |
43-35 11--3     .  0--8 32-40       <- Y=0

44-36 12--4        7-15 39-47           -1
|  |  |              |  |  |
60-52 28-20     5  6    23-31 55-63        -2
|              |  |              |
68-76       21-13 14-22       79-71        -3
|        |        |        |
92-84       29-37 38-30       87-95        -4
|  |
85-77 53-45 46-54 78-86              -5
|  |  |        |  |  |
93 69-61       62-70 94              -6

^
-6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6``````

The multiples of 8 (or however many arms) N=0,8,16,etc is the original curve, and the further mod 8 parts are the copies.

The middle "." shown is the origin X=0,Y=0. It would be more symmetrical to have the origin the middle of the eight arms, which would be X=-0.5,Y=-0.5 in the above, but that would give fractional X,Y values. Apply an offset X+0.5,Y+0.5 to centre if desired.

## Level Ranges

The N=0 point is reckoned as level=0, then N=0 to N=5 inclusive is level=1, etc. Each level is 4 copies of the previous and an extra 2 points between.

``````    LevelPoints[k] = 4*LevelPoints[k-1] + 2   starting LevelPoints=1
= 2 + 2*4 + 2*4^2 + ... + 2*4^(k-1) + 1*4^k
= (5*4^k - 2)/3

Nlevel[k] = LevelPoints[k] - 1         since starting at N=0
= 5*(4^k - 1)/3
= 0, 5, 25, 105, 425, 1705, 6825, 27305, ...    (A146882)``````

The width along the X axis of a level doubles each time, plus an extra distance 3 between.

``````    LevelWidth[k] = 2*LevelWidth[k-1] + 3     starting LevelWidth=0
= 3 + 3*2 + 3*2^2 + ... + 3*2^(k-1) + 0*2^k
= 3*(2^k - 1)

Xlevel[k] = 1 + LevelWidth[k]
= 3*2^k - 2
= 1, 4, 10, 22, 46, 94, 190, 382, ...           (A033484)``````

## Level Ranges with Diagonal Length

With `diagonal_length` = L, level=0 is reckoned as having L many points instead of just 1.

``````    LevelPoints[k] = 2 + 2*4 + 2*4^2 + ... + 2*4^(k-1) + L*4^k
= ( (3L+2)*4^k - 2 )/3

Nlevel[k] = LevelPoints[k] - 1
= ( (3L+2)*4^k - 5 )/3``````

The width of level=0 becomes L-1 instead of 0.

``````    LevelWidth[k] = 2*LevelWidth[k-1] + 3     starting LevelWidth=L-1
= 3 + 3*2 + 3*2^2 + ... + 3*2^(k-1) + (L-1)*2^k
= (L+2)*2^k - 3

Xlevel[k] = 1 + LevelWidth[k]
= (L+2)*2^k - 2``````

Level=0 as L many points can be thought of as a little block which is replicated in mirror image to make level=1. For example the diagonal 4 example above becomes

``````                8  9            diagonal_length => 4
|  |
6--7 10-11
|        |
.  5       12  .

2--3             14-15
|                    |
0--1                   16-17``````

The spacing between the parts is had in the tiling by taking a margin of 1/2 at the base and 1 horizontally left and right.

## Level Fill

The curve doesn't visit all the points in the eighth of the plane below the X=Y diagonal. In general Nlevel+1 many points of the triangular area Xlevel^2/4 are visited, for a filled fraction which approaches a constant

``````                  Nlevel          4*(3L+2)
FillFrac = ------------   ->  ---------
Xlevel^2 / 4       3*(L+2)^2``````

For example the default L=1 has FillFrac=20/27=0.74. Or L=2 FillFrac=2/3=0.66. As the diagonal length increases the fraction decreases due to the growing holes in the pattern.

# FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

`\$path = Math::PlanePath::SierpinskiCurveStair->new ()`
`\$path = Math::PlanePath::SierpinskiCurveStair->new (diagonal_length => \$L, arms => \$A)`

Create and return a new 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.

Fractional positions give an X,Y position along a straight line between the integer positions.

`\$n = \$path->n_start()`

Return 0, the first N in the path.

## Level Methods

`(\$n_lo, \$n_hi) = \$path->level_to_n_range(\$level)`

Return `(0, ((3*\$diagonal_length +2) * 4**\$level - 5)/3` as per "Level Ranges with Diagonal Length" above.

# OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

``````    A146882   Nlevel, for level=1 up
A033484   Xmax and Ymax in level, being 3*2^n - 2``````