Ulam spiral

This page contains some information on how to program a simple Ulam spiral. Please refer to the Wikipedia page to get an in detail explanation of the Ulam spiral.

Basically, the Ulam spiral is a nice way to show the distribution of prime numbers.

1. Ulam created a spiral starting at “1” in the center like shown below:

This is the spiral with all numbers form 1 to 120.
This is the spiral with all numbers form 1 to 120.

This is the spiral, showing the direction of the movement.
This is the spiral, showing the direction of the movement.

Download the spiral code.

2. Then Ulam marked/circled the prime numbers. The resulting plot below is not random as one would expect. Rather, it seems that the occurrence/distribution of prime numbers follows some (unknown) order.

The Ulam spiral with 400 by 400 pixesl.
The Ulam spiral with 400 by 400 pixesl.

Download the ulam code.

The JavaScript code to perform step one, without the corresponding html-file is given by

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// I took the drawing to canvas prototype from the examples at http://www.w3schools.com/
var doc = document.getElementById("Canvas");
var ctx = doc.getContext("2d");
 
// Put the point (0,0) in the center of the canvas
ctx.translate( Math.round( doc.width / 2 ), Math.round( doc.height / 2 ) );
 
// Start at position xpos = 0 and ypos = 0. Set the line size to 1 pixel. Set the distance between lines to 5 pixels.
var xpos = 0, ypos = 0, lin_size = 1, dist_size = 5;
// This is the state variable. State -> 1: right, 2: up, 3: left, 4: down
var next_step = 1;
// Some helper variables
var i, inc = 0, inc_next = 1;
 
// Blue color for the 2x2 dots
ctx.fillStyle="#0000FF";
 
for( i = 1; i < = doc.width * doc.height; i++ ) {
 
    ctx.beginPath();
    ctx.moveTo(xpos, ypos);
 
    /*
        The Ulam spiral starts at 1 at point (0,0) and than goes 1 step right to point (1,0).
        After that, go one step up to (1,-1). Go one step left to (0,-1). Go one step left to (-1,-1) ...
 
        Thus at the end, we have the following chain:
 
        1 x right, 1 x up, 2 x left, 2 x down, 3 x right, 3 x up, 4 x left, 4 x down, 5 x right ...
 
        Thus, for inc_next:
 
        inc_next = 1, inc_next = 1, inc_next = 2, inc_next = 2, inc_next = 3, inc_next = 3 ...
 
        Every time inc is equal to inc_next, it is set to zero and the next_step state variable is incremented
    */
    if ( inc == inc_next ) {
        inc = 0;
        next_step ++;
        if (next_step == 5) {
            next_step = 1;
        }
 
        if ( next_step == 1 || next_step == 3 ) {
            inc_next = inc_next + 1;
        }
    }
 
    // Depending on the next_step state, either go right, up, left or down
    switch ( next_step ) {
        case 1:
            xpos = xpos + dist_size;
            break;
        case 2:
            ypos = ypos - dist_size;
            break;
        case 3:
            xpos = xpos - dist_size;
            break;
        case 4:
            ypos = ypos + dist_size;
            break;
    }
 
    ctx.lineTo (xpos , ypos, lin_size, lin_size);
    ctx.stroke();
 
    inc ++;
 
}

After we know, how to generate the spiral, the only thing thats left is to eliminate all non-prime numbers. Afterwards, mark only the pixels corresponding to prime numbers by blue (or black or any other) color. This is step two and the JavaScript code, without the corresponding html-file is given by

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// I took the drawing to canvas prototype from the examples at http://www.w3schools.com/
var doc = document.getElementById("Canvas");
var ctx = doc.getContext("2d");
 
// Put the point (0,0) in the center of the canvas
ctx.translate( Math.round( doc.width / 2 ), Math.round( doc.height / 2 ) );
 
// Start at position xpos = 0 and ypos = 0. Set the dot size to 1 x 1 pixel
var xpos = 0, ypos = 0, dot_size = 1;
// This is the state variable. State -> 1: right, 2: up, 3: left, 4: down
var next_step = 1;
// Some helper variables
var i, inc = 0, inc_next = 1;
 
// Blue color for the 2x2 dots
ctx.fillStyle="#0000FF";
 
for( i = 1; i < = doc.width * doc.height; i++ ) {
 
    if ( isPrime(i) ) {
        // If i is prime, draw a dot of size dot_size x dot_size
        ctx.fillRect (xpos , ypos, dot_size, dot_size);
    }
 
    /*
        The Ulam spiral starts at 1 at point (0,0) and than goes 1 step right to point (1,0).
        After that, go one step up to (1,-1). Go one step left to (0,-1). Go one step left to (-1,-1) ...
 
        Thus at the end, we have the following chain:
 
        1 x right, 1 x up, 2 x left, 2 x down, 3 x right, 3 x up, 4 x left, 4 x down, 5 x right ...
 
        Thus, for inc_next:
 
        inc_next = 1, inc_next = 1, inc_next = 2, inc_next = 2, inc_next = 3, inc_next = 3 ...
 
        Every time inc is equal to inc_next, it is set to zero and the next_step state variable is incremented
    */
    if ( inc == inc_next ) {
        inc = 0;
        next_step ++;
        if (next_step == 5) {
            next_step = 1;
        }
 
        if ( next_step == 1 || next_step == 3 ) {
            inc_next = inc_next + 1;
        }
    }
 
    // Depending on the next_step state, either go right, up, left or down
    switch ( next_step ) {
        case 1:
            xpos = xpos + dot_size;
            break;
        case 2:
            ypos = ypos - dot_size;
            break;
        case 3:
            xpos = xpos - dot_size;
            break;
        case 4:
            ypos = ypos + dot_size;
            break;
    }
 
    inc ++;
 
}
 
function isPrime( num ) {
 
    /*
        Check for numbers which are smaller then 2 (negative numbers cannot be prime either)
        Check for non-integer numbers which cannot be prime
    */
    if ( num < 2 && num != Math.round(num) ) {
        return false;
    }
 
    /*
        To check for num being a prime number, we will iterate from i = 2 to sqrt(num).
        If i divided by num delivers an integer, num cannot be prime.
        In other words, the remainder of the modulo operation ( num % i ) must be zero 
    */
    for( var i = 2; i <= Math.sqrt(num); i++ ) {
        /*
            Once we found a non-prime number, we can exit the for-statement and also the isPrime() function
            with a false return value.
            Returning early from the function will be slightly faster as we do not need to check all the other i's,
            once we know num cannot be prime.
        */
        if ( num % i == 0 ) {
            return false;
        }
    }
 
    // If we have come this far, num must be prime.
    return true;
 
};

Leave a Reply

Your email address will not be published. Required fields are marked *

*