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 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, as the widening is
105 basically a 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 rearranging 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 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 N to X,Y with Wider
256 With the "wider" parameter stretching the spiral loops the formulas
257 above become
258 Nbase = 4*d^2 + (-4+2w)*d + 2-w
260 d = floor ((2-w + sqrt(4N + w^2 - 4)) / 4)
262 Notice for Nbase the w is a term 2*w*d, being an extra 2*w for each
264 loop.
265 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 wl = ceil(w/2)
271 wr = floor(w/2) = w - wl
272 The horizontal lengths increase by w, and positions shift by wl or wr,
274 but the verticals are unchanged.
275 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 ^
288 X=-d-wl
289 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 Nsig = N - Nbase - (4d-1+w)
294 = N - ((4d + 2w)*d + 1)
295 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 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 On that basis the maximum N in a rectangle is at one of the four
317 corners,
318 |
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
329 This path is in Sloane's Online Encyclopedia of Integer Sequences in
330 various forms. Summary at
331 <http://oeis.org/A068225/a068225.html>
333 And various sequences,
335 <http://oeis.org/A174344> (etc),
337 <https://oeis.org/wiki/Ulam's_spiral>
338 wider=0 (the default)
340 A174344 X coordinate
341 A214526 abs(X)+abs(Y) "Manhattan" distance
342 A079813 abs(dY), being k 0s followed by k 1s
344 A063826 direction 1=right,2=up,3=left,4=down
345 A027709 boundary length of N unit squares
347 A078633 grid sticks to make N unit squares
348 A033638 N turn positions (extra initial 1, 1)
350 A172979 N turn positions which are primes too
351 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 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 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 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 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 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 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 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 A062410 total sum previous row or column
405 wider=1
407 A069894 N on South-West diagonal
408 The following have "offset 0" in the OEIS and therefore are based on
410 starting from N=0.
411 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 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
425 Math::PlanePath, Math::PlanePath::PyramidSpiral
426 Math::PlanePath::DiamondSpiral, Math::PlanePath::PentSpiralSkewed,
428 Math::PlanePath::HexSpiralSkewed, Math::PlanePath::HeptSpiralSkewed
429 Math::PlanePath::CretanLabyrinth
431 Math::NumSeq::SpiroFibonacci
433 X11 cursor font "box spiral" cursor which is this style (but going
435 clockwise).
436
438 <http://user42.tuxfamily.org/math-planepath/index.html>
439
441 Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
442 This file is part of Math-PlanePath.
444 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 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 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/>.
457perl v5.28.0 2017-12-03 Math::PlanePath::SquareSpiral(3)
