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 above 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, since the widening is a
105       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       rearrange 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 in
249
250           Ronald L. Graham, Donald E. Knuth, Oren Patashnik, "Concrete
251           Mathematics", Addison-Wesley, 1989, chapter 3 "Integer Functions",
252           exercise 40 page 99, answer page 498.
253
254       They start the spiral from 0, and first step North so their x is -Y
255       here.  Their formula for x(n) tests a floor(2*sqrt(N)) to decide
256       whether on a horizontal and so whether to apply the equivalent of Nrem
257       to the result.
258
259   N to X,Y with Wider
260       With the "wider" parameter stretching the spiral loops the formulas
261       above become
262
263           Nbase = 4*d^2 + (-4+2w)*d + 2-w
264
265           d = floor ((2-w + sqrt(4N + w^2 - 4)) / 4)
266
267       Notice for Nbase the w is a term 2*w*d, being an extra 2*w for each
268       loop.
269
270       The left offset ceil(w/2) described above ("Wider") for the N=1
271       starting position is written here as wl, and the other half wr arises
272       too,
273
274           wl = ceil(w/2)
275           wr = floor(w/2) = w - wl
276
277       The horizontal lengths increase by w, and positions shift by wl or wr,
278       but the verticals are unchanged.
279
280                    2d+w
281                +------------+        <- Y=d
282                |            |
283           2d   |            |  2d-1
284                |     .      |
285                |            |
286                |            + X=d+wr,Y=-d+1
287                |
288                +---------------+     <- Y=-d
289                    2d+1+w
290
291                ^
292              X=-d-wl
293
294       The Nsig formulas then have w, wl or wr variously inserted.  In all
295       cases if w=wl=wr=0 then they simplify to the plain versions.
296
297           Nsig = N - Nbase - (4d-1+w)
298                = N - ((4d + 2w)*d + 1)
299
300            side      Nsig range            X,Y result
301            ----      ----------            ----------
302           right         Nsig <= -(2d+w)    X = d+wr
303                                            Y = d+(Nsig+2d+w) = 3d+w+Nsig
304           top      -(2d+w) <= Nsig <= 0    X = -d-wl-Nsig
305                                            Y = d
306           left       0 <= Nsig <= 2d       X = -d-wl
307                                            Y = d-Nsig
308           bottom    2d <= Nsig             X = -d+1-wl+(Nsig-(2d+1)) = Nsig-wl-3d
309                                            Y = -d
310
311   Rectangle to N Range
312       Within each row the minimum N is on the X=Y diagonal and N values
313       increases monotonically as X moves away to the left or right.
314       Similarly in each column there's a minimum N on the X=-Y opposite
315       diagonal, or X=-Y+1 diagonal when X negative, and N increases
316       monotonically as Y moves away from there up or down.  When wider>0 the
317       location of the minimum changes, but N is still monotonic moving away
318       from the minimum.
319
320       On that basis the maximum N in a rectangle is at one of the four
321       corners,
322
323                     |
324           x1,y2 M---|----M x2,y2      corner candidates
325                 |   |    |            for maximum N
326              -------O---------
327                 |   |    |
328                 |   |    |
329           x1,y1 M---|----M x1,y1
330                     |
331

OEIS

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

SEE ALSO

446       Math::PlanePath, Math::PlanePath::PyramidSpiral
447
448       Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiralSkewed,
449       Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed
450
451       Math::PlanePath::CretanLabyrinth
452
453       Math::NumSeq::SpiroFibonacci
454
455       X11 cursor font "box spiral" cursor which is this style (but going
456       clockwise).
457

HOME PAGE

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

LICENSE

462       Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019,
463       2020, 2021 Kevin Ryde
464
465       This file is part of Math-PlanePath.
466
467       Math-PlanePath is free software; you can redistribute it and/or modify
468       it under the terms of the GNU General Public License as published by
469       the Free Software Foundation; either version 3, or (at your option) any
470       later version.
471
472       Math-PlanePath is distributed in the hope that it will be useful, but
473       WITHOUT ANY WARRANTY; without even the implied warranty of
474       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
475       General Public License for more details.
476
477       You should have received a copy of the GNU General Public License along
478       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
479
480
481
482perl v5.32.1                      2021-01-27  Math::PlanePath::SquareSpiral(3)
Impressum