 ## SYNOPSIS

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

## DESCRIPTION

This path is a ``DDUU'' turn pattern similar in nature to the terdragon but on a square grid and with 5 segments instead of 3.

```             31-----30     27-----26                                  5
|      |      |      |
32---29/33--28/24----25                                  4
|      |
35---34/38--39/23----22     11-----10      7------6      3
|      |             |      |      |      |      |
36---37/41--20/40--21/17--16/12---13/9----8/4-----5      2
|      |      |      |      |      |
--50     47---42/46--19/43----18     15-----14      3------2      1
|      |      |      |                                  |
49/53--48/64  45/65--44/68    69                    0------1  <-Y=0
^      ^      ^      ^      ^      ^      ^      ^      ^
-7     -6     -5     -4     -3     -2     -1     X=0     1
```

The name ``R5'' is by Jorg Arndt. The base figure is an ``S'' shape

```    4----5
|
3----2
|
0----1
```

which then repeats in self-similar style, so N=5 to N=10 is a copy rotated +90 degrees, as per the direction of the N=1 to N=2 segment.

```    10    7----6
|    |    |  <- repeat rotated +90
9---8,4---5
|
3----2
|
0----1
```

Like the terdragon there are no reversals or mirroring. Each replication is the plain base curve.

The shape of N=0,5,10,15,20,25 repeats the initial N=0 to N=5,

```           25                          4
/
/           10__              3
/           /    ----___
20__         /            5      2
----__  /            /
15            /        1
/
0       <-Y=0
^    ^    ^    ^    ^    ^
-4   -3   -2   -1   X=0   1
```

The curve never crosses itself. The vertices touch at corners like N=4 and N=8 above, but no edges repeat.

## Spiralling

The first step N=1 is to the right along the X axis and the path then slowly spirals anti-clockwise and progressively fatter. The end of each replication is

```    Nlevel = 5^level
```

Each such point is at arctan(2/1)=63.43 degrees further around from the previous,

```    Nlevel     X,Y     angle (degrees)
------    -----    -----
1        1,0         0
5        2,1        63.4
25       -3,4      2*63.4 = 126.8
125      -11,-2     3*63.4 = 190.3
```

## Arms

The curve fills a quarter of the plane and four copies mesh together perfectly rotated by 90, 180 and 270 degrees. The "arms" parameter can choose 1 to 4 such curve arms successively advancing.

"arms => 4" begins as follows. N=0,4,8,12,16,etc is the first arm (the same shape as the plain curve above), then N=1,5,9,13,17 the second, N=2,6,10,14 the third, etc.

```    arms => 4
16/32---20/63
|
21/60    9/56----5/12----8/59
|       |       |       |
17/33--- 6/13--0/1/2/3---4/15---19/35
|       |       |       |
10/57----7/14---11/58   23/62
|
22/61---18/34
```

With four arms every X,Y point is visited twice, except the origin 0,0 where all four begin. Every edge between the points is traversed once.

## Tiling

The little ``S'' shapes of the N=0to5 base shape tile the plane with 2x1 bricks and 1x1 holes in the following pattern,

```    +--+-----|  |--+--+-----|  |--+--+---
|  |     |  |  |  |     |  |  |  |
|  |-----+-----|  |-----+-----|  |---
|  |  |  |     |  |  |  |     |  |  |
+-----|  |-----+-----|  |-----+-----+
|     |  |  |  |     |  |  |  |     |
+-----+-----|  |-----+-----|  |-----+
|  |  |     |  |  |  |     |  |  |  |
---|  |-----+-----|  |-----+-----|  |
|  |  |  |     |  |  |  |     |  |
---+-----|  |-----o-----|  |-----+---
|  |     |  |  |  |     |  |  |  |
|  |-----+-----|  |-----+-----|  |---
|  |  |  |     |  |  |  |     |  |  |
+-----|  |-----+-----|  |-----+-----+
|     |  |  |  |     |  |  |  |     |
+-----+-----|  |-----+-----|  |-----+
|  |  |     |  |  |  |     |  |  |  |
---|  |-----+-----|  |-----+-----|  |
|  |  |  |     |  |  |  |     |  |
---+--+--|  |-----+--+--|  |-----+--+
```

This is the curve with each segment N=2mod5 to N=3mod5 omitted. A 2x1 block has 6 edges but the ``S'' traverses just 4 of them. The way the blocks mesh meshes together mean the other 2 edges are traversed by another brick, possibly a brick on another arm of the curve.

This tiling is also found for example at

<http://tilingsearch.org/HTML/data182/AL04.html>

Or with enlarged square part, <http://tilingsearch.org/HTML/data149/L3010.html>

## FUNCTIONS

See ``FUNCTIONS'' in Math::PlanePath for behaviour common to all path classes.
"\$path = Math::PlanePath::R5DragonCurve->new ()"
"\$path = Math::PlanePath::R5DragonCurve->new (arms => 4)"
Create and return a new path object.

The optional "arms" parameter can make 1 to 4 copies of the curve, each arm successively advancing.

"(\$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 \$n gives an X,Y position along a straight line between the integer positions.

"\$n = \$path->xy_to_n (\$x,\$y)"
Return the point number for coordinates "\$x,\$y". If there's nothing at "\$x,\$y" then return "undef".

The curve can visit an "\$x,\$y" twice. The smallest of the these N values is returned.

"@n_list = \$path->xy_to_n_list (\$x,\$y)"
Return a list of N point numbers for coordinates "\$x,\$y".

The origin 0,0 has "arms_count()" many N since it's the starting point for each arm. Other points have up to two Ns for a given "\$x,\$y". If arms=4 then every "\$x,\$y" except the origin has exactly two Ns.

"\$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, 5**\$level)", or for multiple arms return "(0, \$arms * 5**\$level + (\$arms-1))".

There are 5^level segments in a curve level, so 5^level+1 points numbered from 0. For multiple arms there are arms*(5^level+1) points, numbered from 0 so n_hi = arms*(5^level+1)-1.

## FORMULAS

Various formulas for boundary length and area can be found in the author's mathematical write-up

<http://user42.tuxfamily.org/r5dragon/index.html>

## Turn

At each point N the curve always turns 90 degrees either to the left or right, it never goes straight ahead. As per the code in Jorg Arndt's fxtbook, if N is written in base 5 then the lowest non-zero digit gives the turn

```    lowest non-0 digit     turn
------------------     ----
1              left
2              left
3              right
4              right
```

At a point N=digit*5^level for digit=1,2,3,4 the turn follows the shape at that digit, so two lefts then two rights,

```    4*5^k----5^(k+1)
|
|
2*5^k----2*5^k
|
|
0------1*5^k
```

The first and last unit segments in each level are the same direction, so at those endpoints it's the next level up which gives the turn.

## Next Turn

The turn at N+1 can be calculated in a similar way but from the lowest non-4 digit.

```    lowest non-4 digit     turn
------------------     ----
0              left
1              left
2              right
3              right
```

This works simply because in N=...z444 becomes N+1=...(z+1)000 and so the turn at N+1 is given by digit z+1.

## Total Turn

The direction at N, ie. the total cumulative turn, is given by the direction of each digit when N is written in base 5,

```    digit       direction
0             0
1             1
2             2
3             1
4             0
direction = (sum direction for each digit) * 90 degrees
```

For example N=13 in base 5 is ``23'' so digit=2 direction=2 plus digit=3 direction=1 gives direction=(2+1)*90 = 270 degrees, ie. south.

Because there's no reversals etc in the replications there's no state to maintain when considering the digits, just a plain sum of direction for each digit.

## OEIS

The R5 dragon is in Sloane's Online Encyclopedia of Integer Sequences as,

<http://oeis.org/A175337> (etc)

```    A175337    next turn 0=left,1=right
(n=0 is the turn at N=1)
A006495    level end X, Re(b^k)
A006496    level end Y, Re(b^k)
A079004    boundary length N=0 to 5^k, skip initial 7,10
being 4*3^k - 2
A048473    boundary/2 (one side), N=0 to 5^k
being half whole, 2*3^n - 1
A198859    boundary/2 (one side), N=0 to 25^k
being even levels, 2*9^n - 1
A198963    boundary/2 (one side), N=0 to 5*25^k
being odd levels, 6*9^n - 1
A007798    1/2 * area enclosed N=0 to 5^k
A016209    1/4 * area enclosed N=0 to 5^k
A005058    1/2 * new area N=5^k to N=5^(k+1)
being area increments, 5^n - 3^n
A005059    1/4 * new area N=5^k to N=5^(k+1)
being area increments, (5^n - 3^n)/2
A008776    count single-visited points N=0 to 5^k
being 2*3^k
A024024    C[k] boundary lengths, 3^k-k
A104743    E[k] boundary lengths, 3^k+k
arms=1 and arms=3
A059841    abs(dX), being simply 1,0 repeating
A000035    abs(dY), being simply 0,1 repeating
arms=4
A165211    abs(dY), being 0,1,0,1,1,0,1,0 repeating
```

<http://user42.tuxfamily.org/math-planepath/index.html>