1Math::PlanePath::SquareUSspeirraClo(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::SquareSpiral(3)
2
6 Math::PlanePath::SquareSpiral -- integer points drawn around a square
7 (or rectangle)
8
10 use Math::PlanePath::SquareSpiral;
11 my $path = Math::PlanePath::SquareSpiral->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This path makes a square spiral,
16 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 ^
32 -3 -2 -1 X=0 1 2 3 4
33 See examples/square-numbers.pl for a simple program printing these
35 numbers.
36 Ulam Spiral
38 This path is well known from Stanislaw Ulam finding interesting
39 straight lines when plotting the prime numbers on it.
40 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 The cover of Scientific American March 1964 featured this spiral,
47 <http://www.nature.com/scientificamerican/journal/v210/n3/covers/index.html>
49 <http://oeis.org/A143861/a143861.jpg>
51 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 Stein, Ulam and Wells above also considered primes on the
56 Math::PlanePath::Corner path, and on a half-plane like two corners.
57 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 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 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 Wider
75 An optional "wider" parameter makes the path wider, becoming a
76 rectangle spiral instead of a square. For example
77 wider => 3
79 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 ^
91 -4 -3 -2 -1 X=0 1 2 3
92 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 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 Each loop is still 8 longer than the previous, since the widening is a
105 constant amount in each loop.
106 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 n_start => 0
113 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 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 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 Corners Cut Class
132 ----------- -----
133 1 HeptSpiralSkewed
134 2 HexSpiralSkewed
135 3 PentSpiralSkewed
136 4 DiamondSpiral
137 The "PyramidSpiral" is a re-shaped "SquareSpiral" looping at the same
139 rate. It shifts corners but doesn't cut them.
140
142 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
143 classes.
144 "$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 "($x,$y) = $path->n_to_xy ($n)"
153 Return the X,Y coordinates of point number $n on the path.
154 For "$n < 1" the return is an empty list, as the path starts at 1.
156 "$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
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 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 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 d = floor( 1/2 + sqrt(N/4 - 1/4) )
179 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 d = floor( (1+sqrt(N-1))/2 )
185 So Nbase from this d leaves a remainder which is an offset into the
187 loop
188 Nrem = N - Nbase
190 = N - (4*d^2 - 4*d + 2)
191 The loop starts at X=d,Y=d-1 and has sides length 2d, 2d+1, 2d+1 and
193 2d+2,
194 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 ^
207 X=-d
208 The X,Y for an Nrem is then
210 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 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 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 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 Nsig = N - Nbase - (4d-1)
234 = N - (4*d^2 - 4*d + 2) - (4d-1)
235 = N - (4*d^2 + 1)
236 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 This calculation can be found in
249 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 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 N to X,Y with Wider
260 With the "wider" parameter stretching the spiral loops the formulas
261 above become
262 Nbase = 4*d^2 + (-4+2w)*d + 2-w
264 d = floor ((2-w + sqrt(4N + w^2 - 4)) / 4)
266 Notice for Nbase the w is a term 2*w*d, being an extra 2*w for each
268 loop.
269 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 wl = ceil(w/2)
275 wr = floor(w/2) = w - wl
276 The horizontal lengths increase by w, and positions shift by wl or wr,
278 but the verticals are unchanged.
279 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 ^
292 X=-d-wl
293 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 Nsig = N - Nbase - (4d-1+w)
298 = N - ((4d + 2w)*d + 1)
299 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 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 On that basis the maximum N in a rectangle is at one of the four
321 corners,
322 |
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
333 This path is in Sloane's Online Encyclopedia of Integer Sequences in
334 various forms. Summary at
335 <http://oeis.org/A068225/a068225.html>
337 And various sequences,
339 <http://oeis.org/A174344> (etc),
341 <https://oeis.org/wiki/Ulam's_spiral>
342 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 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 A027709 boundary length of N unit squares
356 A078633 grid sticks to make N unit squares
357 A240025 turn 1=left,0=straight (extra initial 1)
359 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 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 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 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 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 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 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 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 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 A062410 total sum previous row or column
427 wider=1
429 A069894 N on South-West diagonal
430 The following have "offset 0" S and therefore start from N=0.
432 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 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
446 Math::PlanePath, Math::PlanePath::PyramidSpiral
447 Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiralSkewed,
449 Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed
450 Math::PlanePath::CretanLabyrinth
452 Math::NumSeq::SpiroFibonacci
454 X11 cursor font "box spiral" cursor which is this style (but going
456 clockwise).
457
459 <http://user42.tuxfamily.org/math-planepath/index.html>
460
462 Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019,
463 2020, 2021 Kevin Ryde
464 This file is part of Math-PlanePath.
466 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 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 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/>.
479perl v5.34.0 2022-01-21 Math::PlanePath::SquareSpiral(3)
