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!

 

 

 

Prime Numbers And How To Find Them 1: Introduction

The fundamental theorem of arithmetic states that every integer greater than one is either is prime or the unique product of primes, ignoring the order.

Many will remember the definition from primary school. A prime is a number divisible by only two others, one and itself. All other numbers are made from two or more of these primes multiplied together. Some might even remember that one itself is not prime. But mainly, people remember the tedious process of finding prime factorizations of numbers and lowest common factors of pairs. It’s not until after a little exploration into number theory that one begins to realise the mysterious yet powerful properties of these numbers.

Prime numbers are universal. Prime numbers are compared to fundamental particles, making up all numbers and they conserve this property in any base, in any language. If we were to encounter extraterrestrials on their planet, a list of primes in an intuitive form could be the best way to establish the level of their development. (I say on their planet because if they had the means to travel to Earth they are bound to be somewhat intelligent and scientific)

Alien primes

There are an infinite number of primes. The best known and most easily understood proof is by Euclid and uses contradiction:

1. Assume that there are a finite number of primes

2, 3, 5, 7 … p               (mathematicians often use lowercase p to represent a prime)

2. Multiply each known prime together and add one to get a new larger number q

q = 2 x 3 x 5 x 7 x … x p  + 1

3. None of the known primes between 2, p is a factor of q. Each would leave a remainder of 1 on division.

4. If q is not prime then it must still be divisible by a prime larger than p. Otherwise, q is itself prime. In both these cases, there must be a prime larger than p.

5. Steps 1-4 can always be applied to the newly obtained set of prime, extending it. Hence the list is the real never ending story, in other words infinite.

 

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, the Sieve of Eratosthenes, prime spirals, use in cryptography, modern prime searches and how you can get involved, and the yet unsolved mysteries of prime numbers.  Follow my twitter feed for updates on my writing and for other bits of mathematics in 140 characters or less.

 

 

 

WELCOME

This site is still under construction, due to be finished in summer 2017. In the meantime, bookmark this page and follow @lulu_beatson for updates and content.
You can be expecting blog posts about my studies (transitioning from 6th form to University, studying mathematics obviously) as well as advice and revision resources for A-level Mathematics, Further Mathematics, Physics, and Chemistry.
I look forward to seeing you in the near future,
Lulu