An Ulam spiral (of primes) is a method of visualizing primes when expressed in a (normally counter-clockwise) outward spiral (usually starting at 1),   constructed on a square grid, starting at the "center".

An Ulam spiral is also known as a   prime spiral.

The first grid (green) is shown with sequential integers,   starting at   1.

In an Ulam spiral of primes, only the primes are shown (usually indicated by some glyph such as a dot or asterisk),   and all non-primes as shown as a blank   (or some other whitespace).

Of course, the grid and border are not to be displayed (but they are displayed here when using these Wiki HTML tables).

Normally, the spiral starts in the "center",   and the   2nd   number is to the viewer's right and the number spiral starts from there in a counter-clockwise direction.

There are other geometric shapes that are used as well, including clock-wise spirals.

Also, some spirals (for the   2nd   number)   is viewed upwards from the   1st   number instead of to the right, but that is just a matter of orientation.

Sometimes, the starting number can be specified to show more visual striking patterns (of prime densities).

[A larger than necessary grid (numbers wise) is shown here to illustrate the pattern of numbers on the diagonals   (which may be used by the method to orientate the direction of spiral-construction algorithm within the example computer programs)].

Then, in the next phase in the transformation of the Ulam prime spiral,   the non-primes are translated to blanks.

In the orange grid below,   the primes are left intact,   and all non-primes are changed to blanks.

Then, in the final transformation of the Ulam spiral (the yellow grid),   translate the primes to a glyph such as a    •    or some other suitable glyph.





 65 
 64 
 63 
 62 
 61 
 60 
 59 
 58 
 57


 66 
 37 
 36 
 35 
 34 
 33 
 32 
 31 
 56


 67 
 38 
 17 
 16 
 15 
 14 
 13 
 30 
 55


 68 
 39 
 18 
  5 
  4 
  3 
 12 
 29 
 54


 69 
 40 
 19 
  6 
  1 
  2 
 11 
 28 
 53


 70 
 41 
 20 
  7 
  8 
  9 
 10 
 27 
 52


 71 
 42 
 21 
 22 
 23 
 24 
 25 
 26 
 51


 72 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50


 73 
 74 
 75 
 76 
 77 
 78 
 79 
 80 
 81



   
   
   
   
 61 
   
 59 
   
  


   
 37 
   
   
   
   
   
 31 
  


 67 
   
 17 
   
   
   
 13 
   
  


   
   
   
  5 
   
  3 
   
 29 
  


   
   
 19 
   
   
  2 
 11 
   
 53


   
 41 
   
  7 
   
   
   
   
  


 71 
   
   
   
 23 
   
   
   
  


   
 43 
   
   
   
 47 
   
   
  


 73 
   
   
   
   
   
 79 
   
  



   
   
   
   
  • 
   
  • 
   
  


   
  • 
   
   
   
   
   
  • 
  


  • 
   
  • 
   
   
   
  • 
   
  


   
   
   
  • 
   
  • 
   
  • 
  


   
   
  • 
   
   
  • 
  • 
   
  •


   
  • 
   
  • 
   
   
   
   
  


  • 
   
   
   
  • 
   
   
   
  


   
  • 
   
   
   
  • 
   
   
  


  • 
   
   
   
   
   
  • 
   
  



The Ulam spiral becomes more visually obvious as the grid increases in size.



Task
For any sized   N × N   grid,   construct and show an Ulam spiral (counter-clockwise) of primes starting at some specified initial number   (the default would be 1),   with some suitably   dotty   (glyph) representation to indicate primes,   and the absence of dots to indicate non-primes.

You should demonstrate the generator by showing at Ulam prime spiral large enough to (almost) fill your terminal screen.



Related tasks

   Spiral matrix
   Zig-zag matrix
   Identity matrix 
   Sequence of primes by Trial Division


See also
 Wikipedia entry:   Ulam spiral 
 MathWorld™ entry:   Prime Spiral


 
 43 constant border                                                         \ grid size is border x border
 border border * constant size                                                    
 
 variable crawler                                                           \ position of the crawler
 
 : set.crawler border 2 mod 0= if                                           \ positions the crawler in the middle of the grid
	 size 2 / border 2/ + 1 - crawler !
	 else 
	 size 2 / crawler ! then ;
 
 set.crawler                                                                
 create Grid size cells allot                                               \ creates the grid
 here constant GridEnd                                                      \ used for debugging 
 
 : is.divisor                                                                       
	over 2over
	mod 0= swap drop + ;
 
 : sub.one 
	 swap 1 - swap ;
 
 : next.div
	 is.divisor sub.one ;
 
 : three.test                                                                \ counts divisors for numbers bigger than 2
	 dup 0 
     begin
	 next.div 
     over 1 = until 
	 swap drop
	 swap drop 1 + ;
 
 : not.prime                                                                 \ counts the number of divisors. Primes have exactly two.
    dup
    2 < if drop true else 
	three.test then ;
 
 : sub.four                                                                   \ the crawler takes a number from the stack as direction
	 dup 4 > if 4 - then ;                                                \ this word makes the number roll over.                                                                
                                                                              \ 1-right 2-up 3-left 4-down
 : craw.left                                                                  \ rotates the crawler 90 degrees counter-clockwise
	 1 + sub.four ;
 
 : scan.right 
	 grid crawler @ 1 + cells + @ 0= ;                                    \ checks if cell to the right of the crawler is zero
 
 : scan.left 
	 grid crawler @ 1 - cells + @ 0= ;                                    \ cell to the left
 
 : scan.up 
	 grid crawler @ border - cells + @ 0= ;                               \ cell above
 
 : scan.down 
	 grid crawler @ border + cells + @ 0= ;                               \ and cell below
 
 : crawler.go                                                                 \ moves crawler one cell ahead checks cell to the left... 
	 dup                                                                  \ ...of the direction the crawler is facing, if zero, turns
	 1 = if crawler @ 1 + crawler ! scan.up if craw.left then else       
	 dup 
	 2 = if crawler @ border - crawler ! scan.left if craw.left then else
	 dup 
	 3 = if crawler @ 1 - crawler ! scan.down if craw.left then else
	 dup 
	 4  = if crawler @ border + crawler ! scan.right if craw.left then else
 
	 then then then then ;
 
 : run.crawler                                                              \ crawler moves through the grid and fills it with numbers
	 border 2 < if 1 grid 0 cells + ! else                              \ if the grid is a single cell, puts 1 in it
	 crawler @ border - crawler !	                                    \ crawler moves one step and turn before setting the first... 
	 4                                                                  \ ...number so it is repositioned one cell up facing down
  	 size -1 * 0 do  i
	 i -1 * grid crawler @ cells + ! drop
	 crawler.go
	 -1 +loop then drop ;
 
 : leave.primes                                                                    \ removes non-primes from the grid
	 size 0 do i
	 grid i cells + @ not.prime if 0 grid i cells + ! then drop
	 loop ;
 
 : star.draw1                                                                      \ draws a "*" where number is not zero
	 0> if 42 emit else 32 emit
	 then ;
 
 : star.draw2
	 0> if 42 emit 32 emit else 32 emit 32 emit                                 \ same but adds a space for better presentation
	 then ;
 
 : star.draw3
	 0> if 32 emit 42 emit 32 emit else 32 emit 32 emit 32 emit                 \ adds two spaces
	 then ;
 
 : draw.grid                                                                         \ cuts the array into lines and displays it
	page
	size 0 do i
	i border mod 0= if  cr  then
	grid i cells + @ star.draw2 drop                                             \ may use star.draw1 or 3 here
	loop ; 
 
 : ulam.spiral run.crawler leave.primes draw.grid ;                                  \ draws the spiral. Execute this word to run.
 