Provided by: libmath-planepath-perl_129-1_all bug

NAME

       Math::PlanePath::QuintetReplicate -- self-similar "+" tiling

SYNOPSIS

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

DESCRIPTION

       This is a self-similar tiling of the plane with "+" shapes.  It's the same kind of tiling
       as the "QuintetCurve" (and "QuintetCentres"), but with the middle square of the "+" shape
       centred on the origin.

                   12                         3

               13  10  11       7             2

                   14   2   8   5   6         1

               17   3   0   1   9         <- Y=0

           18  15  16   4  22                -1

               19      23  20  21            -2

                           24                -3

                        ^
           -4 -3 -2 -1 X=0  1  2  3  4

       The base pattern is a "+" shape

               +---+
               | 2 |
           +---+---+---+
           | 3 | 0 | 1 |
           +---+---+---+
               | 4 |
               +---+

       which is then replicated

                +--+
                |  |
             +--+  +--+  +--+
             |   10   |  |  |
             +--+  +--+--+  +--+
                |  |  |   5    |
             +--+--+  +--+  +--+
             |  |   0    |  |
          +--+  +--+  +--+--+
          |   15   |  |  |
          +--+  +--+--+  +--+
             |  |  |   20   |
             +--+  +--+  +--+
                      |  |
                      +--+

       The effect is to tile the whole plane.  Notice the centres 0,5,10,15,20 are the same "+"
       shape but positioned around at angle atan(1/2)=26.565 degrees.  The relative positioning
       in each of those parts is the same, so at 5 the successive 6,7,8,9 are E,N,W,S like the
       base shape.

   Complex Base
       This tiling corresponds to expressing a complex integer X+i*Y as

           base b=2+i
           X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]

       where each digit position factor a[i] corresponds to N digits

           N digit     a[i]
           -------    ------
              0          0
              1          1
              2          i
              3         -1
              4         -i

       The base b is at an angle arg(b) = atan(1/2) = 26.56 degrees as seen at N=5 above.
       Successive powers b^2, b^3, b^4 etc at N=5^level rotate around by that much each time.

           Npow = 5^level  at b^level
           angle(Npow) = level*26.56 degrees
           radius(Npow) = sqrt(5) ^ level

       The path can be reckoned bottom-up as a new low digit of N expanding each unit square to
       the base "+" shape.

                                    +---C
           D-------C                | 2 |
           |       |            D---+---+---+
           |       |     =>     | 3 | 0 | 1 |
           |       |            +---+---+---B
           A-------B                | 4 |
                                    A---+

       Side A-B becomes a 3-segment S.  Such an expansion is the same as the TerdragonCurve or
       GosperSide, but here turns of 90 degrees.  Like GosperSide there is no touching or overlap
       of the sides expansions, so boundary length 4*3^level.

   Rotate Numbering
       Parameter "numbering_type => 'rotate'" applies a rotation to the numbering in each sub-
       part according to its location around the preceding level.

       The effect can be illustrated by writing N in base-5.  Part 10-14 is the same as the
       middle 0-4.  Part 20-24 has a rotation by +90 degrees.  Part 30-34 has rotation by +180
       degrees, and part 40-44 by +270 degrees.

                   21
                 /  |
               22  20  24      12           numbering_type => 'rotate'
                 \    /      /    \             N shown in base-5
                   23   2  13  10--11
                      /   \   \
               34   3   0-- 1  14
                  \   \
           31--30  33   4  41
             \    /       /   \
               32      43  40  42
                            | /
                           41

       Notice this means in each part the 11, 21, 31, etc, points are directed away from the
       middle in the same way, relative to the sub-part locations.

       Working through the expansions gives the following rule for when an N is on the boundary
       of level k,

           write N in base-5 digits  (empty string if k=0)
           if length < k then non-boundary
           ignore high digit and all 1 digits
           if any pair 32, 33, 44 then non-boundary

       A 0 digit is the middle of a block, so always non-boundary.  After that the 4,1,2,3 parts
       variously expand with rotations so that a 44 is enclosed on the clockwise side and 32 and
       33 on the anti-clockwise side.

FUNCTIONS

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

       "$path = Math::PlanePath::QuintetReplicate->new ()"
           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.

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "(0, 5**$level - 1)".

FORMULAS

   Axis Rotations
       The digits positions 1,2,3,4 go around +90deg each, so the N for rotation by +90 is each
       digit +1, cycling around.

           rot+90(N) = 0, 2, 3, 4, 1, 10, 12, 13, 14, 11, 15, ... decimal
                     = 0, 2, 3, 4, 1, 20, 22, 23, 24, 21, 30, ... base5

           rot-90(N) = 0, 4, 1, 2, 3, 20, 24, 21, 22, 23,  5, ... decimal
                     = 0, 4, 1, 2, 3, 40, 44, 41, 42, 43, 10, ... base5

           rot180(N) = 0, 3, 4, 1, 2, 15, 18, 19, 16, 17, 20, ... decimal
                     = 0, 3, 4, 1, 2, 30, 33, 34, 31, 32, 40, ... base5

   X,Y Extents
       The maximum X in a given level N=0 to 5^k-1 can be calculated from the replications.  A
       given high digit 1 to 4 has sub-parts located at b^k*i^(d-1).  Those sub-parts are all the
       same, so the one with maximum real(b^k*i^(d-1)) contains the maximum X.

           N_xmax_digit(j) = d=1,2,3,4 where real(i^(d-1) * b^j) is maximum
                           = 1,1,4,4,4,4,3,3,3,2,2,2,1,1, ...

                        k-1
           N_xmax(k) = digits N_xmax_digit(j)    low digit j=0
                        j=0
                     = 0, 1, 6, 106, 606, 3106, 15606, ...    decimal
                     = 0, 1, 11, 411, 4411, 44411, 444411, ...  base5

                       k-1
           z_xmax(k) = sum  i^d[j] * b^j
                       j=0      each d[j] with real(i^d[j] * b^j) maximum
                     = 0, 1, 3+i, 7-2*i, 18-4*i, 42+3*i, 83+41*i, ...

           xmax(k) = real(z_xmax(k))
                   = 0, 1, 3, 7, 18, 42, 83, 200, 478, 1005, ...

       For computer calculation these maximums can be calculated by the powers.  The digit parts
       can also be written in terms of the angle arg(b) = atan(1/2).  For successive k, if adding
       atan(1/2) pushes the b^k angle past +45deg then the preceding digit goes past -45deg and
       becomes the new maximum X.  Write the angle as a fraction of 90deg (pi/2),

           F = atan(1/2) / (pi/2)  = 0.295167 ...

       This is irrational since b^k is never on the X or Y axes.  That can be seen since
       imag(b^k) mod 5 == 1 if k odd and == 4 if k even >= 2.  Similarly real(b^k) mod 5 == 2,3
       so not on the Y axis, or also anything on the Y axis would have 3*k fall on the X axis.

       Digits low to high successively step back in a cycle 4,3,2,1 so that (with mod giving 0 to
       3),

           N_xmax_digit(j) = (-floor(F*j+1/2) mod 4) + 1

       The +1/2 is since initial direction b^0=1 is angle 0 which is half way between -45 and +45
       deg.

       Similarly the X,Y location, using -i for rotation back

           z_xmax_exp(j) = floor(F*j+1/2)
                         = 0,0,1,1,1,1,2,2,2,3,3,3,4,4,4,4,5,5, ...
           z_xmax(k) = sum(j=0,k-1, (-i)^z_xmax_exp(j) * b^j)

       By symmetry the maximum extent is the same for Y vertically and for X or Y negative,
       suitably rotated.  The N in those cases has the digits 1,2,3,4 cycled around as per "Axis
       Rotations" above.

       If the +1/2 in the floor is omitted then the effect is to find the maximum point in
       direction +45deg, so the point(s) with maximum sum S = X+Y.

           N_smax_digit(j) = (-floor(F*j) mod 4) + 1
                           = 1,1,1,1,4,4,4,3,3,3,3,2,2,2,1, ...

                        k-1
           N_smax(k) = digits N_smax_digit(j)    low digit j=0
                        j=0
                     = 0, 1, 6, 31, 156, 2656, 15156, ...     decimal
                     = 0, 1, 11, 111, 1111, 41111, 441111, ...  base5
           and also N_smax() + 1

           z_smax_exp(j) = floor(F*j)
                         = 0,0,0,0,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5, ...
           z_smax(k) = sum(j=0,k-1, (-i)^z_smax_exp(j) * b^j)
                     = 0, 1, 3+i, 6+5*i, 8+16*i, 32+23*i, 73+61*i, ...
           and also z_smax() + 1+i

           smax(k) = real(z_smax(k)) + imag(z_smax(k))
                   = 0, 1, 4, 11, 24, 55, 134, 295, 602, 1465, ...

       In the base figure points 1 and 2 are both on the same 45deg line and this remains so in
       subsequent levels, so that for k>=1 N_smax(k) and N_smax(k)+1 are equal maximums.

OEIS

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

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

           A316657    X coordinate
           A316658    Y coordinate
           A316707    norm X^2 + Y^2

SEE ALSO

       Math::PlanePath, Math::PlanePath::QuintetCurve, Math::PlanePath::ComplexMinus,
       Math::PlanePath::GosperReplicate

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021 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/>.