and 1 contributors

# NAME

Math::PlanePath::R5DragonCurve -- radix 5 dragon curve

# 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

# 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, area, and more, can be found in the author's mathematical write-up

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

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

A052919,A100702  U part boundary length, N=0 to 5^k

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

A125831    N middle segment of level k, (5^k-1)/2
A008776    count single-visited points N=0 to 5^k, being 2*3^k
A146086    count visited points N=0 to 5^k

A024024    C[k] boundary lengths, 3^k-k
A104743    E[k] boundary lengths, 3^k+k

A135518    1/4 * sum distinct abs(n-other(n)) in level N=0 to 5^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``````

# HOUSE OF GRAPHS

House of Graphs entries for the R5 dragon curve as a graph include

level=2, https://hog.grinvin.org/ViewGraphInfo.action?id=25149
level=3, https://hog.grinvin.org/ViewGraphInfo.action?id=25147

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