Ulam Spiral

• How it works?
• C# Code

Prime spiral

Ulam spiral is a mathematical structure where numbers are written in a spiral form starting from 1.It is said that this spiral came into existence during a boring meeting,which Ulam was attending.During the meet he got bored and started doodling on his paper a number spiral with 1 at the center and the next numbers following it in a spiral fashion.What surprised Ulam was not the spiral but the placements of the prime numbers on the spiral.As you can see in the second image(right),the prime numbers have aligned themselves in a diagonal fashion.The Ulam spiral is used for understanding the tendencies and behaviors of prime numbers.This post will show you how to generate Ulam spirals and in my next post i will use it to solve a Project Euler problem.

A Ulam spiral on the left and the right spiral with prime numbers marked
courtesy wiki

The above image is a matrix of dimension 7 x 7 with N 49.

Lets take a small matrix of dimension 4 x 4 and see how we can work out.(Max number :16)

A 4 x 4 Matrix with two cycles( Cycle 1- Gray,Cycle 2 -Red) 

Since matrix is a four sided representation every cycle will have 4 iterations(top,left,bottom,right).The gray and red marks in the above image represents two different cycles.

A cycle will be deemed complete when all the cells for that cycle is filled.To work out the number of cells per cycle do (dimension -1) * 4

if we apply this for both the cycles we get

Cycle 1    4-1 * 4 =12

Cycle 2    2-1 * 4= 4 (dimension of red block is 2)

So we have a total of 16 cells to fill ,with 12 cells to fill in cycle 1 and 4 cells to complete in cycle 2.

We will start filling the numbers from the top right corner of matrix,moving left with the placement of every number and cycle in a anticlockwise movement filling all the four sides of every cycle.

By changing the row index and column index of our array ,we can easily move in the direction we want.The direction information will be stored in a small array which would instruct the program to go in a certain direction.{E,S,W,N} E- East,S-South,W-West,N-North.

On first iteration of cycle 1 we would move East and during the second iteration Move South.

On third move West and on the final iteration move North(which is what the direction array {E,S,W,N} tells that in a programmatic fashion) .But how do we know when to stop and change the direction.Simple ,stop after filling (dimension -1) cells on every iteration,then move by one cell in the direction you were moving.Finally change the direction with the help of direction array.

So in our example we need to fill (4-1)=3 cells in every iteration of Cycle 1

For the second cycle we need to fill just one cell on every side.as(2-1)=1

The same procedure will have to be repeated on every cycle until all the cells are filled.

There is one more question to answer how would you move from one cycle to other(gray to red) inside of a matrix.Its simple again subtract your current cycle's dimension by 2 you get the dimension of the enclosed matrix.

for e.g 
Cycle 1 dimension  = 4 
Cycle 2 dimentsion =Cycle 1 dimension  - 2 =  2 (refer second image for clarity).

C# Code

Download Code

Console Output

Ulam spiral for 10 x 10 Matrix