I'd like to share some thoughts about a specific mathematical phenomenon related to the prime numbers and tiny piece of software to generate visual representation of it.

What is specific about prime numbers?

2 3 5 7 11 13 17 19 ...

You can generate infinite number of primes, but...

• Are primes truly random?
• Do they follow any visible pattern?

The spiral and Stanisław Ulam

When you generate more and more of those numbers, you can see that without any doubt there is a pattern.

First thing that notice is the presence of diagonal lines. What you would expect to see is a random noise, like that below. (I choose only odd numbers to compare because the density is fairly comparable on the image and more importantly all of prime numbers are also odd, except for number 2.)

Later the Ulam's idea was popularized by Martin Gardner, very prominent writer from Scientific American (Scientific American 210, 120 - 128 (1964)) and people started to wonder what is causing the prime numbers to form those distinct patterns when drawn into spiral.

Here is the original cover from the Scientific American:

(source: OEIS)

I will not cover the explanation for the prime spiral mystery, but I can mention that approximate solution is related to the fact that some quadratic polynomials generate great number of primes. You can notice that diagonal lines on the spiral are formed by series of either only odd or even numbers. To learn more, please refer to the Everipedia: Explanation of the Ulam Spiral

Let's see by ourselves

How to generate primes?

In the modern times we would express the Sieve as a Rust code, like here:

 1 pub fn generate_primes(max: u64) -> Vec<u64> {
 2     let mut candidates: Vec<u64> = vec![1; max as usize + 1];
 3     candidates[0] = 0;
 4     candidates[1] = 0;
 5     let max_sqrt = (max as f64).sqrt() as u64 + 1;
 6 
 7     for number in 2..max_sqrt {
 8         let mut multiplied = number * number;
 9         while multiplied < max + 1 {
10             candidates[multiplied as usize] = 0;
11             multiplied += number;
12         }
13     }
14     candidates
15 }

The output of the function would look like this:

1 vec![0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0]

Algorithm for generating the spiral

1. For all directions (down, left, up, right) walk exactly this many times as is the current side length of the spiral.
2. Every second turn add one step to the length, so that we don't overlap the existing spiral.
3. Every time you make a step, pick a element from the array (Vec in our case) and check if the number is a prime. If yes, then paint a pixel.

 1 let directions = &["down", "left", "up", "right"];
 2 
 3         while !stop {
 4 
 5             for direction in directions {
 6                 turn += 1;
 7                 for _ in 0..times {
 8                     if counter < numbers_len {
 9                         stop = self.move_cursor(&mut x, &mut y, direction);
10                         if numbers[counter] == 1 {
11                             img.put_pixel(x, y, pixel)
12                         }
13                         counter += 1;
14                     }
15                 }
16                 if turn == 2 {
17                     times += 1;
18                     turn = 0;
19                 }
20             }
21             if (counter >= numbers_len) | (x <= 2) {
22                 stop = true;
23             }
24         }

1 image::ImageBuffer<image::Rgb<u8>, Vec<u8>>

Later the buffer can be used for two purposes:

• Save the data as the png file
• Show the image in the window

What did not work as expected

After having some hard time with the code I decided that this feature is not so cool to spend more time on it. Don't try to fix something that is GOOD ENOUGH.
In my opinion it's really important to show not only successful results in software engineering, but also the failures. They are also part of the job and they tell the story about the amount of time and effort that was spent overall on some task.

In the next post I'll give some more details about the Rust programming with Gtk, which was pretty exciting, but also a bit challenging.

Source code

Sources:

Worth visiting: