1Math::PlanePath::QuinteUtsReerplCiocnattrei(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::QuintetReplicate(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

14       This is a self-similar tiling of the plane with "+" shapes.  It's the
15       same kind of tiling as the "QuintetCurve" (and "QuintetCentres"), but
16       with the middle square of the "+" shape centred on the origin.
17
18                   12                         3
19
20               13  10  11       7             2
21
22                   14   2   8   5   6         1
23
24               17   3   0   1   9         <- Y=0
25
26           18  15  16   4  22                -1
27
28               19      23  20  21            -2
29
30                           24                -3
31
32                        ^
33           -4 -3 -2 -1 X=0  1  2  3  4
34
35       The base pattern is a "+" shape
36
37               +---+
38               | 2 |
39           +---+---+---+
40           | 3 | 0 | 1 |
41           +---+---+---+
42               | 4 |
43               +---+
44
45       which is then replicated
46
47                +--+
48                |  |
49             +--+  +--+  +--+
50             |   10   |  |  |
51             +--+  +--+--+  +--+
52                |  |  |   5    |
53             +--+--+  +--+  +--+
54             |  |   0    |  |
55          +--+  +--+  +--+--+
56          |   15   |  |  |
57          +--+  +--+--+  +--+
58             |  |  |   20   |
59             +--+  +--+  +--+
60                      |  |
61                      +--+
62
63       The effect is to tile the whole plane.  Notice the centres 0,5,10,15,20
64       are the same "+" shape but positioned around at angle atan(1/2)=26.565
65       degrees.  The relative positioning in each of those parts is the same,
66       so at 5 the successive 6,7,8,9 are E,N,W,S like the base shape.
67
68   Complex Base
69       This tiling corresponds to expressing a complex integer X+i*Y as
70
71           base b=2+i
72           X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]
73
74       where each digit position factor a[i] corresponds to N digits
75
76           N digit     a[i]
77           -------    ------
78              0          0
79              1          1
80              2          i
81              3         -1
82              4         -i
83
84       The base b is at an angle arg(b) = atan(1/2) = 26.56 degrees as seen at
85       N=5 above.  Successive powers b^2, b^3, b^4 etc at N=5^level rotate
86       around by that much each time.
87
88           Npow = 5^level  at b^level
89           angle(Npow) = level*26.56 degrees
90           radius(Npow) = sqrt(5) ^ level
91
92       The path can be reckoned bottom-up as a new low digit of N expanding
93       each unit square to the base "+" shape.
94
95                                    +---C
96           D-------C                | 2 |
97           |       |            D---+---+---+
98           |       |     =>     | 3 | 0 | 1 |
99           |       |            +---+---+---B
100           A-------B                | 4 |
101                                    A---+
102
103       Side A-B becomes a 3-segment S.  Such an expansion is the same as the
104       TerdragonCurve or GosperSide, but here turns of 90 degrees.  Like
105       GosperSide there is no touching or overlap of the sides expansions, so
106       boundary length 4*3^level.
107
108   Rotate Numbering
109       Parameter "numbering_type => 'rotate'" applies a rotation to the
110       numbering in each sub-part according to its location around the
111       preceding level.
112
113       The effect can be illustrated by writing N in base-5.  Part 10-14 is
114       the same as the middle 0-4.  Part 20-24 has a rotation by +90 degrees.
115       Part 30-34 has rotation by +180 degrees, and part 40-44 by +270
116       degrees.
117
118                   21
119                 /  |
120               22  20  24      12           numbering_type => 'rotate'
121                 \    /      /    \             N shown in base-5
122                   23   2  13  10--11
123                      /   \   \
124               34   3   0-- 1  14
125                  \   \
126           31--30  33   4  41
127             \    /       /   \
128               32      43  40  42
129                            | /
130                           41
131
132       Notice this means in each part the 11, 21, 31, etc, points are directed
133       away from the middle in the same way, relative to the sub-part
134       locations.
135
136       Working through the expansions gives the following rule for when an N
137       is on the boundary of level k,
138
139           write N in base-5 digits  (empty string if k=0)
140           if length < k then non-boundary
141           ignore high digit and all 1 digits
142           if any pair 32, 33, 44 then non-boundary
143
144       A 0 digit is the middle of a block, so always non-boundary.  After that
145       the 4,1,2,3 parts variously expand with rotations so that a 44 is
146       enclosed on the clockwise side and 32 and 33 on the anti-clockwise
147       side.
148

FUNCTIONS

150       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
151       classes.
152
153       "$path = Math::PlanePath::QuintetReplicate->new ()"
154           Create and return a new path object.
155
156       "($x,$y) = $path->n_to_xy ($n)"
157           Return the X,Y coordinates of point number $n on the path.  Points
158           begin at 0 and if "$n < 0" then the return is an empty list.
159
160   Level Methods
161       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
162           Return "(0, 5**$level - 1)".
163

FORMULAS

165   Axis Rotations
166       The digits positions 1,2,3,4 go around +90deg each, so the N for
167       rotation by +90 is each digit +1, cycling around.
168
169           rot+90(N) = 0, 2, 3, 4, 1, 10, 12, 13, 14, 11, 15, ... decimal
170                     = 0, 2, 3, 4, 1, 20, 22, 23, 24, 21, 30, ... base5
171
172           rot-90(N) = 0, 4, 1, 2, 3, 20, 24, 21, 22, 23,  5, ... decimal
173                     = 0, 4, 1, 2, 3, 40, 44, 41, 42, 43, 10, ... base5
174
175           rot180(N) = 0, 3, 4, 1, 2, 15, 18, 19, 16, 17, 20, ... decimal
176                     = 0, 3, 4, 1, 2, 30, 33, 34, 31, 32, 40, ... base5
177
178   X,Y Extents
179       The maximum X in a given level N=0 to 5^k-1 can be calculated from the
180       replications.  A given high digit 1 to 4 has sub-parts located at
181       b^k*i^(d-1).  Those sub-parts are all the same, so the one with maximum
182       real(b^k*i^(d-1)) contains the maximum X.
183
184           N_xmax_digit(j) = d=1,2,3,4 where real(i^(d-1) * b^j) is maximum
185                           = 1,1,4,4,4,4,3,3,3,2,2,2,1,1, ...
186
187                        k-1
188           N_xmax(k) = digits N_xmax_digit(j)    low digit j=0
189                        j=0
190                     = 0, 1, 6, 106, 606, 3106, 15606, ...    decimal
191                     = 0, 1, 11, 411, 4411, 44411, 444411, ...  base5
192
193                       k-1
194           z_xmax(k) = sum  i^d[j] * b^j
195                       j=0      each d[j] with real(i^d[j] * b^j) maximum
196                     = 0, 1, 3+i, 7-2*i, 18-4*i, 42+3*i, 83+41*i, ...
197
198           xmax(k) = real(z_xmax(k))
199                   = 0, 1, 3, 7, 18, 42, 83, 200, 478, 1005, ...
200
201       For computer calculation these maximums can be calculated by the
202       powers.  The digit parts can also be written in terms of the angle
203       arg(b) = atan(1/2).  For successive k, if adding atan(1/2) pushes the
204       b^k angle past +45deg then the preceding digit goes past -45deg and
205       becomes the new maximum X.  Write the angle as a fraction of 90deg
206       (pi/2),
207
208           F = atan(1/2) / (pi/2)  = 0.295167 ...
209
210       This is irrational since b^k is never on the X or Y axes.  That can be
211       seen since imag(b^k) mod 5 == 1 if k odd and == 4 if k even >= 2.
212       Similarly real(b^k) mod 5 == 2,3 so not on the Y axis, or also anything
213       on the Y axis would have 3*k fall on the X axis.
214
215       Digits low to high successively step back in a cycle 4,3,2,1 so that
216       (with mod giving 0 to 3),
217
218           N_xmax_digit(j) = (-floor(F*j+1/2) mod 4) + 1
219
220       The +1/2 is since initial direction b^0=1 is angle 0 which is half way
221       between -45 and +45 deg.
222
223       Similarly the X,Y location, using -i for rotation back
224
225           z_xmax_exp(j) = floor(F*j+1/2)
226                         = 0,0,1,1,1,1,2,2,2,3,3,3,4,4,4,4,5,5, ...
227           z_xmax(k) = sum(j=0,k-1, (-i)^z_xmax_exp(j) * b^j)
228
229       By symmetry the maximum extent is the same for Y vertically and for X
230       or Y negative, suitably rotated.  The N in those cases has the digits
231       1,2,3,4 cycled around as per "Axis Rotations" above.
232
233       If the +1/2 in the floor is omitted then the effect is to find the
234       maximum point in direction +45deg, so the point(s) with maximum sum S =
235       X+Y.
236
237           N_smax_digit(j) = (-floor(F*j) mod 4) + 1
238                           = 1,1,1,1,4,4,4,3,3,3,3,2,2,2,1, ...
239
240                        k-1
241           N_smax(k) = digits N_smax_digit(j)    low digit j=0
242                        j=0
243                     = 0, 1, 6, 31, 156, 2656, 15156, ...     decimal
244                     = 0, 1, 11, 111, 1111, 41111, 441111, ...  base5
245           and also N_smax() + 1
246
247           z_smax_exp(j) = floor(F*j)
248                         = 0,0,0,0,1,1,1,2,2,2,2,3,3,3,4,4,4,5,5,5, ...
249           z_smax(k) = sum(j=0,k-1, (-i)^z_smax_exp(j) * b^j)
250                     = 0, 1, 3+i, 6+5*i, 8+16*i, 32+23*i, 73+61*i, ...
251           and also z_smax() + 1+i
252
253           smax(k) = real(z_smax(k)) + imag(z_smax(k))
254                   = 0, 1, 4, 11, 24, 55, 134, 295, 602, 1465, ...
255
256       In the base figure points 1 and 2 are both on the same 45deg line and
257       this remains so in subsequent levels, so that for k>=1 N_smax(k) and
258       N_smax(k)+1 are equal maximums.
259

OEIS

261       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
262       this path include
263
264           <http://oeis.org/A316657> (etc)
265
266           A316657    X coordinate
267           A316658    Y coordinate
268           A316707    norm X^2 + Y^2
269

SEE ALSO

271       Math::PlanePath, Math::PlanePath::QuintetCurve,
272       Math::PlanePath::ComplexMinus, Math::PlanePath::GosperReplicate
273

HOME PAGE

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

LICENSE

278       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020,
279       2021 Kevin Ryde
280
281       Math-PlanePath is free software; you can redistribute it and/or modify
282       it under the terms of the GNU General Public License as published by
283       the Free Software Foundation; either version 3, or (at your option) any
284       later version.
285
286       Math-PlanePath is distributed in the hope that it will be useful, but
287       WITHOUT ANY WARRANTY; without even the implied warranty of
288       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
289       General Public License for more details.
290
291       You should have received a copy of the GNU General Public License along
292       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
293
294
295
296perl v5.32.1                      2021-01-2M7ath::PlanePath::QuintetReplicate(3)
Impressum