Prime Numbers And How To Find Them 2: Randomness

10 by 10 grid numbered
Primes under 100

Again, many will be have been acquainted with the number grid showing prime numbers. Immediately, there is an element of randomness but with a little more thought, you may notice columns of non-primes. The more noticeable lines are because of our conventional base-10 (decimal) having factors 2, 5 and 10. If however, we were to choose base-12 (duodecimal or dozenal) with more factors 2, 3, 4, 6, 12 then there are a greater number of blank columns. The quantities represented by the primes are of course the same – remember that our extra-terrestrial mathematicians may own a different number of digits if they have hands at all.

 

10 x 12 primes
12 by 10 grid of primes

 

 

One way of generating primes is by the elimination of composite numbers, a process known as the Sieve of Eratosthenes. This basic algorithm is not used in modern prime searches because it requires so much memory and becomes much too inefficient for larger numbers.

Sieve_of_Eratosthenes_animation
CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=2810935

Thinking of primes in this way, as the left over numbers, you can make an interesting observation which I think introduces the mystery of primes. That is, although composite numbers are periodic, the location of the left overs are not so easily predicted. And this is true, finding and testing for primes are both challenging.

The larger the numbers, the more sparsely distributed the primes. The Sieve of Eratosthenes makes this is intuitive and there are many mathematical ideas regarding the density of primes. The best known of these is The Prime Number Theorem (PNT) which can be presented in one of two ways:

a)    π(N) ~ log(N

where π(N) is the prime-counting function, giving the number of primes less than or equal to N

b)    P(a number less than or equal to N is prime) ~ log(N)

notice that this is simply the proportion of numbers which are prime:  π(N) / N

Another is Bertrand’s postulate, conjectured by Joseph Bertrand and first proven by Pafnuty Chebyshev in the 19th century. But it was 20 year old Paul Erdos who published a much simpler proof and popularised the rhyme:

“Chebyshev said it,

And I say it again,

There is always a prime

Between n and 2n.”

You can find a version of Erdos’ proof on this Wikipedia page.

Take your time as the language in this type of summary is not commonly used. However, do read the summary before you look at the proof for each stage as you will gain a much better understanding of how they fit together and move towards the desired statement.

 

 

The rest of “Prime Numbers and How to Find Them” will be uploaded in short segments throughout the next few weeks. I’ll be talking more about patterns in primes, prime spirals, use in cryptography, modern prime searches and how you can get involved, and the yet unsolved mysteries of prime numbers.  Follow @lulu_beatson for updates on my writing and for other bits of mathematics in 140 characters or less. If you don’t have twitter you can always subscribe by email.

See you soon!