= Ulam's Spiral of Prime Numbers =

<<TableOfContents>>

== About Ulam's Spiral ==

The Polish mathematician Stanisław Ulam discovered an interesting way of viewing the distribution of prime numbers, now known as an [[http://en.wikipedia.org/wiki/Ulam_spiral|Ulam Spiral]].

Imagine writing down a spiral of numbers which starts with '1' in the centre and then spirals outwards:

{{{
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 ...etc
}}}
Now put a circle around each prime number and look at the pattern produced. You might expect to get a random distribution, but instead the primes seem to line up along diagonal lines. Here, for example, is the 20 x 20 spiral with prime number positions indicated by '○' characters:
{{{
   ○       ○     ○
        ○   ○ ○   ○
 ○     ○         ○ ○
  ○   ○ ○
         ○ ○     ○
  ○ ○   ○       ○
         ○ ○   ○
○   ○ ○     ○ ○ ○
 ○ ○ ○ ○   ○       ○
        ○ ○ ○
   ○   ○  ○○ ○ ○ ○
    ○ ○ ○
     ○   ○
○   ○ ○   ○   ○ ○
 ○   ○     ○     ○ ○
      ○           ○
 ○ ○     ○   ○   ○
  ○           ○
     ○   ○ ○
    ○ ○   ○     ○
}}}


== Ulam's Spiral in APL ==

We can generate Ulam spirals in APL using two simple functions. The first of these is based on the [[SieveOfEratosthenes|Sieve of Eratosthenes]] and generates prime numbers:

{{{
      ∇R←Primes N
[1]   R←(2=+⌿0=(⍳N)∘.|⍳N)/⍳N
      ∇  
}}}

The second function generates a spiral pattern:
{{{
      ∇R←Spiral N;start;indices;⎕IO
[1]   ⎕IO←1
[2]   start←(2|N)+(N+1)×⌊N÷2
[3]   indices←+\(N*2)↑start,(2/⍳N)/(2×N)⍴1 (-N) ¯1 N
[4]   R[indices]←R←⍳⍴indices
[5]   R←(N,N)⍴R
      ∇  
}}}

Together we can use them to generate Ulam spirals:
{{{
      X←7           ⍝ Choose a small size so it fits easily on Wiki page
      Primes X*2
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
      Spiral X
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
      ' ○'[⎕IO+(Spiral X)∊Primes X*2]      
○     ○
 ○   ○
  ○ ○ ○
 ○  ○○
○ ○
   ○
○   ○
}}}

Large patterns get too big to display in this form. Instead we can display the spiral in a window:

{{attachment:ulam150.jpg}}

You can do this in APLX (not under development any more) using the following code. Other APLs allow something similar.
{{{
'win' ⎕WI 'new' 'window'('title' 'Ulam Spiral')
'win.picture' ⎕WI 'new' 'picture'('align' ¯1)
'win.picture' ⎕WI 'bitmap'(~(Spiral X)∊Primes N*X)  
}}}
&nbsp;
&nbsp;

== How the APL code works ==

The function to generate prime numbers is discussed fully here: [[SieveOfEratosthenes|Sieve of Eratosthenes]] 

To understand the Spiral function, start by considering the following 7 x 7 spiral:
{{{
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
}}}

If you were to walk this spiral you would start in the middle, then go right one, up one, left two, down two, etc. Suppose we use the following representation:
||<style="text-align: right;">1 || Right ||
||<style="text-align: right;">¯7 || Up ||
||<style="text-align: right;">¯1 || Left ||
||<style="text-align: right;">7 || Down ||

Using this representation, we would walk the spiral using the following steps:

1 ¯7 ¯1 ¯1 7 7 1 1 1 ¯7 ¯7 ¯7 ¯1 ¯1 ¯1 ¯1 7 7 7 7 1 1 1 1 1 ¯7 ¯7 ¯7 ¯7 ¯7  ...etc

Using parentheses makes the pattern clearer: (1),(¯7),(¯1,¯1),(7,7),(1,1,1),(¯7,¯7,¯7) etc  

We can generate this pattern in APL using the following expression:
{{{
      N←7
      2/⍳N
1 1 2 2 3 3 4 4 5 5 6 6 7 7
      (2/⍳N)/(2×N)⍴1 (-N) ¯1 N
1 ¯7 ¯1 ¯1 7 7 1 1 1 ¯7 ¯7 ¯7 ¯1 ¯1 ¯1 ¯1 7 7 7 7 1 1 1 1 1 ¯7 ¯7 ¯7 ¯7 ¯7 ...etc
}}}

Now consider the index positions of the elements of the 7 x 7 grid:
{{{
      (N,N)⍴⍳N*2
 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35
36 37 38 39 40 41 42
43 44 45 46 47 48 49
}}}

If we were to start the walk in the middle and follow the same outward spiral, we would encounter the numbers in the following order: 25 26 19 18 17 24 31 32 33 34 27 20 13 12 11 10 9 16 23 etc. Notice that we get this sequence by starting with '25' and then successively adding each number in the sequence 1 ¯7 ¯1 ¯1 7 7 1 1 1...

First of all we need to find the number at the middle. We need to consider grids where N is odd and even:
{{{
      start←(2|N)+(N+1)×⌊N÷2
      start
25
}}}

We use this to generate the sequence of index positions:
{{{
      indices←+\(N*2)↑start,(2/⍳N)/(2×N)⍴1 (-N) ¯1 N
      indices
25 26 19 18 17 24 31 32 33 34 27 20 13 12 11 10 9 16 23...
}}}

To finish the Spiral function, we use selective assignment to put a '1' in index position '25', a '2' in position '26', etc, and reshape the result to a 7 x 7 grid: 
{{{
      R[indices]←R←⍳⍴indices
      R←(N,N)⍴R
      R
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
}}} 

Now we're ready to use the Prime and Spiral functions to generate a spiral of primes, putting a '1' wherever we find a prime number.
{{{
      (Spiral X)∊Primes X*2
1 0 0 0 0 0 1
0 1 0 0 0 1 0
0 0 1 0 1 0 1
0 1 0 0 1 1 0
1 0 1 0 0 0 0
0 0 0 1 0 0 0
1 0 0 0 1 0 0
}}}

Finally, we can replace 1 and 0 by '○' and a blank space to make the pattern easier to see:
{{{
     ' ○'[⎕IO+(Spiral X)∊Primes X*2]
○     ○
 ○   ○
  ○ ○ ○
 ○  ○○
○ ○
   ○
○   ○
}}}

== Non-Square Matrices ==

As an extra here is an extended version of Spiral (by DanB) that accepts non square matrices:
{{{
     ∇ R←Spiral N;col;direction;indices;repeat;row;start;t;tr;⎕IO
[1]   ⍝ Build a spiralling list of integers into an N[×M] matrix
[2]    ⎕IO←1
[3]    tr←>/(row col)←2⍴N
[4]    (row col)←tr⌽row col                   ⍝ work on wide matrices
[5]    start←(2|row)+t+col×t←⌊row÷2           ⍝ where the 1st element will be
[6]    repeat←,(t+col-row),[1.1]t←⍳row
[7]    indices←+\(row×col)↑start,repeat/(2×row)⍴1,(-col),¯1,col
[8]    R←⍋indices
[9]    R←(1+tr,~tr)⍉row col⍴R                 ⍝ restore order
[10]   →tr↓0 ⋄ R←⌽R                           ⍝ correct direction
     ∇
}}}
with an example
{{{
      Spiral   6 4
11 10  9 24
12  1  8 23
13  2  7 22
14  3  6 21
15  4  5 20
16 17 18 19
}}}

Author: SimonMarsden

----
CategoryShowCases