1Math::PlanePath::SquareUSspeirraClo(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::SquareSpiral(3)
2
3
4

NAME

6       Math::PlanePath::SquareSpiral -- integer points drawn around a square
7       (or rectangle)
8

SYNOPSIS

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

DESCRIPTION

15       This path makes a square spiral,
16
17           37--36--35--34--33--32--31              3
18            |                       |
19           38  17--16--15--14--13  30              2
20            |   |               |   |
21           39  18   5---4---3  12  29              1
22            |   |   |       |   |   |
23           40  19   6   1---2  11  28  ...    <- Y=0
24            |   |   |           |   |   |
25           41  20   7---8---9--10  27  52         -1
26            |   |                   |   |
27           42  21--22--23--24--25--26  51         -2
28            |                           |
29           43--44--45--46--47--48--49--50         -3
30
31                        ^
32           -3  -2  -1  X=0  1   2   3   4
33
34       See examples/square-numbers.pl for a simple program printing these
35       numbers.
36
37   Ulam Spiral
38       This path is well known from Stanislaw Ulam finding interesting
39       straight lines when plotting the prime numbers on it.
40
41           Stein, Ulam and Wells, "A Visual Display of Some Properties of the
42           Distribution of Primes", American Mathematical Monthly, volume 71,
43           number 5, May 1964, pages 516-520.
44           <http://www.jstor.org/stable/2312588>
45
46       The cover of Scientific American March 1964 featured this spiral,
47
48           <http://www.nature.com/scientificamerican/journal/v210/n3/covers/index.html>
49
50           <http://oeis.org/A143861/a143861.jpg>
51
52       See examples/ulam-spiral-xpm.pl for a standalone program, or see math-
53       image using this "SquareSpiral" to draw this pattern and more.
54
55       Stein, Ulam and Wells also considered primes on the
56       Math::PlanePath::Corner path, and on a half-plane like two corners.
57
58   Straight Lines
59       The perfect squares 1,4,9,16,25 fall on two diagonals with the even
60       perfect squares going to the upper left and the odd squares to the
61       lower right.  The pronic numbers 2,6,12,20,30,42 etc k^2+k half way
62       between the squares fall on similar diagonals to the upper right and
63       lower left.  The decagonal numbers 10,27,52,85 etc 4*k^2-3*k go
64       horizontally to the right at Y=-1.
65
66       In general straight lines and diagonals are 4*k^2 + b*k + c.  b=0 is
67       the even perfect squares up to the left, then incrementing b is an
68       eighth turn anti-clockwise, or clockwise if negative.  So b=1 is
69       horizontal West, b=2 diagonally down South-West, b=3 down South, etc.
70
71       Honaker's prime-generating polynomial 4*k^2 + 4*k + 59 goes down to the
72       right, after the first 30 or so values loop around a bit.
73
74   Wider
75       An optional "wider" parameter makes the path wider, becoming a
76       rectangle spiral instead of a square.  For example
77
78           wider => 3
79
80           29--28--27--26--25--24--23--22        2
81            |                           |
82           30  11--10-- 9-- 8-- 7-- 6  21        1
83            |   |                   |   |
84           31  12   1-- 2-- 3-- 4-- 5  20   <- Y=0
85            |   |                       |
86           32  13--14--15--16--17--18--19       -1
87            |
88           33--34--35--36-...                   -2
89
90                            ^
91           -4  -3  -2  -1  X=0  1   2   3
92
93       The centre horizontal 1 to 2 is extended by "wider" many further
94       places, then the path loops around that shape.  The starting point 1 is
95       shifted to the left by ceil(wider/2) places to keep the spiral centred
96       on the origin X=0,Y=0.
97
98       Widening doesn't change the nature of the straight lines which arise,
99       it just rotates them around.  For example in this wider=3 example the
100       perfect squares are still on diagonals, but the even squares go towards
101       the bottom left (instead of top left when wider=0) and the odd squares
102       to the top right (instead of the bottom right).
103
104       Each loop is still 8 longer than the previous, as the widening is
105       basically a constant amount in each loop.
106
107   N Start
108       The default is to number points starting N=1 as shown above.  An
109       optional "n_start" can give a different start with the same shape.  For
110       example to start at 0,
111
112           n_start => 0
113
114           16-15-14-13-12 ...
115            |           |  |
116           17  4--3--2 11 28
117            |  |     |  |  |
118           18  5  0--1 10 27
119            |  |        |  |
120           19  6--7--8--9 26
121            |              |
122           20-21-22-23-24-25
123
124       The only effect is to push the N values around by a constant amount.
125       It might help match coordinates with something else zero-based.
126
127   Corners
128       Other spirals can be formed by cutting the corners of the square so as
129       to go around faster.  See the following modules,
130
131           Corners Cut    Class
132           -----------    -----
133                1        HeptSpiralSkewed
134                2        HexSpiralSkewed
135                3        PentSpiralSkewed
136                4        DiamondSpiral
137
138       The "PyramidSpiral" is a re-shaped "SquareSpiral" looping at the same
139       rate.  It shifts corners but doesn't cut them.
140

FUNCTIONS

142       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
143       classes.
144
145       "$path = Math::PlanePath::SquareSpiral->new ()"
146       "$path = Math::PlanePath::SquareSpiral->new (wider => $integer, n_start
147       => $n)"
148           Create and return a new square spiral object.  An optional "wider"
149           parameter widens the spiral path, it defaults to 0 which is no
150           widening.
151
152       "($x,$y) = $path->n_to_xy ($n)"
153           Return the X,Y coordinates of point number $n on the path.
154
155           For "$n < 1" the return is an empty list, as the path starts at 1.
156
157       "$n = $path->xy_to_n ($x,$y)"
158           Return the point number for coordinates "$x,$y".  $x and $y are
159           each rounded to the nearest integer, which has the effect of
160           treating each N in the path as centred in a square of side 1, so
161           the entire plane is covered.
162

FORMULAS

164   N to X,Y
165       There's a few ways to break an N into a side and offset into the side.
166       One convenient way is to treat a loop as starting at the bottom right
167       turn, so N=2,10,26,50,etc, If the first loop at N=2 is reckoned loop
168       number d=1 then the loop starts at
169
170           Nbase = 4*d^2 - 4*d + 2
171                 = 2,10,26,50,... for d=1,2,3,4,...
172                          (A069894 but it going from d=0)
173
174       For example d=3 is Nbase=4*3^2-4*3+2=26 at X=3,Y=-2.  The biggest d
175       with Nbase <= N can be found by inverting with the usual quadratic
176       formula
177
178           d = floor (1/2 + sqrt(N/4 - 1/4))
179
180       For Perl it's good to keep the sqrt argument an integer (when a UV
181       integer is bigger than an NV float, and for BigRat accuracy), so
182       rearranging to
183
184           d = floor ((1+sqrt(N-1)) / 2)
185
186       So Nbase from this d leaves a remainder which is an offset into the
187       loop
188
189           Nrem = N - Nbase
190                = N - (4*d^2 - 4*d + 2)
191
192       The loop starts at X=d,Y=d-1 and has sides length 2d, 2d+1, 2d+1 and
193       2d+2,
194
195                    2d
196                +------------+        <- Y=d
197                |            |
198           2d   |            |  2d-1
199                |     .      |
200                |            |
201                |            + X=d,Y=-d+1
202                |
203                +---------------+     <- Y=-d
204                    2d+1
205
206                ^
207              X=-d
208
209       The X,Y for an Nrem is then
210
211            side      Nrem range            X,Y result
212            ----      ----------            ----------
213           right           Nrem <= 2d-1     X = d
214                                            Y = -d+1+Nrem
215           top     2d-1 <= Nrem <= 4d-1     X = d-(Nrem-(2d-1)) = 3d-1-Nrem
216                                            Y = d
217           left    4d-1 <= Nrem <= 6d-1     X = -d
218                                            Y = d-(Nrem-(4d-1)) = 5d-1-Nrem
219           bottom  6d-1 <= Nrem             X = -d+(Nrem-(6d-1)) = -7d+1+Nrem
220                                            Y = -d
221
222       The corners Nrem=2d-1, Nrem=4d-1 and Nrem=6d-1 get the same result from
223       the two sides that meet so it doesn't matter if the high comparison is
224       "<" or "<=".
225
226       The bottom edge runs through to Nrem < 8d, but there's no need to check
227       that since d=floor(sqrt()) above ensures Nrem is within the loop.
228
229       A small simplification can be had by subtracting an extra 4d-1 from
230       Nrem to make negatives for the right and top sides and positives for
231       the left and bottom.
232
233           Nsig = N - Nbase - (4d-1)
234                = N - (4*d^2 - 4*d + 2) - (4d-1)
235                = N - (4*d^2 + 1)
236
237            side      Nsig range            X,Y result
238            ----      ----------            ----------
239           right           Nsig <= -2d      X = d
240                                            Y = d+(Nsig+2d) = 3d+Nsig
241           top      -2d <= Nsig <= 0        X = -d-Nsig
242                                            Y = d
243           left       0 <= Nsig <= 2d       X = -d
244                                            Y = d-Nsig
245           bottom    2d <= Nsig             X = -d+1+(Nsig-(2d+1)) = Nsig-3d
246                                            Y = -d
247
248       This calculation can be found as an exercise in Graham, Knuth and
249       Patashnik "Concrete Mathematics", chapter 3 "Integer Functions",
250       exercise 40, page 99.  They start the spiral from 0, and vertically so
251       their x is -Y here.  Their formula for x(n) tests a floor(2*sqrt(N)) to
252       decide whether on a horizontal and so whether to apply the equivalent
253       of Nrem to the result.
254
255   N to X,Y with Wider
256       With the "wider" parameter stretching the spiral loops the formulas
257       above become
258
259           Nbase = 4*d^2 + (-4+2w)*d + 2-w
260
261           d = floor ((2-w + sqrt(4N + w^2 - 4)) / 4)
262
263       Notice for Nbase the w is a term 2*w*d, being an extra 2*w for each
264       loop.
265
266       The left offset ceil(w/2) described above ("Wider") for the N=1
267       starting position is written here as wl, and the other half wr arises
268       too,
269
270           wl = ceil(w/2)
271           wr = floor(w/2) = w - wl
272
273       The horizontal lengths increase by w, and positions shift by wl or wr,
274       but the verticals are unchanged.
275
276                    2d+w
277                +------------+        <- Y=d
278                |            |
279           2d   |            |  2d-1
280                |     .      |
281                |            |
282                |            + X=d+wr,Y=-d+1
283                |
284                +---------------+     <- Y=-d
285                    2d+1+w
286
287                ^
288              X=-d-wl
289
290       The Nsig formulas then have w, wl or wr variously inserted.  In all
291       cases if w=wl=wr=0 then they simplify to the plain versions.
292
293           Nsig = N - Nbase - (4d-1+w)
294                = N - ((4d + 2w)*d + 1)
295
296            side      Nsig range            X,Y result
297            ----      ----------            ----------
298           right         Nsig <= -(2d+w)    X = d+wr
299                                            Y = d+(Nsig+2d+w) = 3d+w+Nsig
300           top      -(2d+w) <= Nsig <= 0    X = -d-wl-Nsig
301                                            Y = d
302           left       0 <= Nsig <= 2d       X = -d-wl
303                                            Y = d-Nsig
304           bottom    2d <= Nsig             X = -d+1-wl+(Nsig-(2d+1)) = Nsig-wl-3d
305                                            Y = -d
306
307   Rectangle to N Range
308       Within each row the minimum N is on the X=Y diagonal and N values
309       increases monotonically as X moves away to the left or right.
310       Similarly in each column there's a minimum N on the X=-Y opposite
311       diagonal, or X=-Y+1 diagonal when X negative, and N increases
312       monotonically as Y moves away from there up or down.  When wider>0 the
313       location of the minimum changes, but N is still monotonic moving away
314       from the minimum.
315
316       On that basis the maximum N in a rectangle is at one of the four
317       corners,
318
319                     |
320           x1,y2 M---|----M x2,y2      corner candidates
321                 |   |    |            for maximum N
322              -------O---------
323                 |   |    |
324                 |   |    |
325           x1,y1 M---|----M x1,y1
326                     |
327

OEIS

329       This path is in Sloane's Online Encyclopedia of Integer Sequences in
330       various forms.  Summary at
331
332           <http://oeis.org/A068225/a068225.html>
333
334       And various sequences,
335
336           <http://oeis.org/A174344> (etc),
337           <https://oeis.org/wiki/Ulam's_spiral>
338
339           wider=0 (the default)
340             A174344    X coordinate
341             A214526    abs(X)+abs(Y) "Manhattan" distance
342
343             A079813    abs(dY), being k 0s followed by k 1s
344             A063826    direction 1=right,2=up,3=left,4=down
345
346             A027709    boundary length of N unit squares
347             A078633    grid sticks to make N unit squares
348
349             A033638    N turn positions (extra initial 1, 1)
350             A172979    N turn positions which are primes too
351
352             A054552    N values on X axis (East)
353             A054556    N values on Y axis (North)
354             A054567    N values on negative X axis (West)
355             A033951    N values on negative Y axis (South)
356             A054554    N values on X=Y diagonal (NE)
357             A054569    N values on negative X=Y diagonal (SW)
358             A053755    N values on X=-Y opp diagonal X<=0 (NW)
359             A016754    N values on X=-Y opp diagonal X>=0 (SE)
360             A200975    N values on all four diagonals
361
362             A137928    N values on X=-Y+1 opposite diagonal
363             A002061    N values on X=Y diagonal pos and neg
364             A016814    (4k+1)^2, every second N on south-east diagonal
365
366             A143856    N values on ENE slope dX=2,dY=1
367             A143861    N values on NNE slope dX=1,dY=2
368             A215470    N prime and >=4 primes among its 8 neighbours
369
370             A214664    X coordinate of prime N (Ulam's spiral)
371             A214665    Y coordinate of prime N (Ulam's spiral)
372             A214666    -X  \ reckoning spiral starting West
373             A214667    -Y  /
374
375             A053999    prime[N] on X=-Y opp diagonal X>=0 (SE)
376             A054551    prime[N] on the X axis (E)
377             A054553    prime[N] on the X=Y diagonal (NE)
378             A054555    prime[N] on the Y axis (N)
379             A054564    prime[N] on X=-Y opp diagonal X<=0 (NW)
380             A054566    prime[N] on negative X axis (W)
381
382             A090925    permutation N at rotate +90
383             A090928    permutation N at rotate +180
384             A090929    permutation N at rotate +270
385             A090930    permutation N at clockwise spiralling
386             A020703    permutation N at rotate +90 and go clockwise
387             A090861    permutation N at rotate +180 and go clockwise
388             A090915    permutation N at rotate +270 and go clockwise
389             A185413    permutation N at 1-X,Y
390                          being rotate +180, offset X+1, clockwise
391
392             A068225    permutation N to the N to its right, X+1,Y
393             A121496     run lengths of consecutive N in that permutation
394             A068226    permutation N to the N to its left, X-1,Y
395             A020703    permutation N at transpose Y,X
396                          (clockwise <-> anti-clockwise)
397
398             A033952    digits on negative Y axis
399             A033953    digits on negative Y axis, starting 0
400             A033988    digits on negative X axis, starting 0
401             A033989    digits on Y axis, starting 0
402             A033990    digits on X axis, starting 0
403
404             A062410    total sum previous row or column
405
406           wider=1
407             A069894    N on South-West diagonal
408
409       The following have "offset 0" in the OEIS and therefore are based on
410       starting from N=0.
411
412           n_start=0
413             A180714    X+Y coordinate sum
414             A053615    abs(X-Y), runs n to 0 to n, distance to nearest pronic
415
416             A001107    N on X axis
417             A033991    N on Y axis
418             A033954    N on negative Y axis, second 10-gonals
419             A002939    N on X=Y diagonal North-East
420             A016742    N on North-West diagonal, 4*k^2
421             A002943    N on South-West diagonal
422             A156859    N on Y axis positive and negative
423

SEE ALSO

425       Math::PlanePath, Math::PlanePath::PyramidSpiral
426
427       Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiralSkewed,
428       Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed
429
430       Math::PlanePath::CretanLabyrinth
431
432       Math::NumSeq::SpiroFibonacci
433
434       X11 cursor font "box spiral" cursor which is this style (but going
435       clockwise).
436

HOME PAGE

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

LICENSE

441       Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
442
443       This file is part of Math-PlanePath.
444
445       Math-PlanePath is free software; you can redistribute it and/or modify
446       it under the terms of the GNU General Public License as published by
447       the Free Software Foundation; either version 3, or (at your option) any
448       later version.
449
450       Math-PlanePath is distributed in the hope that it will be useful, but
451       WITHOUT ANY WARRANTY; without even the implied warranty of
452       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
453       General Public License for more details.
454
455       You should have received a copy of the GNU General Public License along
456       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
457
458
459
460perl v5.28.0                      2017-12-03  Math::PlanePath::SquareSpiral(3)
Impressum