Random Eratosthenes

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Subscribe!
@ColinTheMathmo

My lastest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:

Why are primes thought to be "random"? - 2011/10/28

Quick reminder - a Prime Number is a number that cannot be written (non-trivially) as the product of two other (whole) numbers. If you have 12 items then they can be arranged in a rectangle (3x4, 2x6) but if you have 13 items then they can't. A number that can be arranged in a rectangle is called "composite".
It's been said that the Prime Numbers are distributed in some sense "randomly," and in part that's what makes them both fascinating and infuriating to study. But a number is either prime or it isn't, so in what sense can we say that they're "random"? In this post we'll have a quick and relatively superficial look at that. The details are scary hard, so I'll just give an idea.

To start with, let's suppose we want to generate all the Prime Numbers up to, say, 150. We can do this using a technique attributed to the ancient Greek mathematician Eratosthenes.

We start by writing out the numbers from 2 up to 150 (or some other limit). We circle the first number that isn't crossed out (which is 2) and then cross out all the multiples of that.

All numbers 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
Circle first number (2) 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
Delete multiples (2) 3 X 5 X 7 X 9 X 11 X 13 X 15 ...
Tidied up (2) 3 5 7 9 11 13 15 ...

So now we've circled 2 and crossed out all its multiple, which is all the even numbers. The next number that isn't crossed out is 3, so we circle that, and cross out all its multiples.

Next number is 3 (2) (3) 4 5 6 7 8 9 10 11 12 13 14 15 ...
Delete multiples (2) (3) 5 X 7 X 11 X 13 X ...
Tidied up (2) (3) 5 7 11 13 ...

Next is 5, so we circle that, and cross out its multiples. Then 7, then 11.

Notice that we didn't have to do any division. That's a key point about the Sieve of Eratosthenes. When writing a computer program to implement the Sieve of Eratosthenes, if you use division (or modulus) then it's not the real thing.
Next is 17, but here's the thing. If any number up to 150 is non-prime, then one of its factors must be less than sqrt(150). But sqrt(150) is 12 and a bit, and we've already crossed out all the multiples of every prime up to that. So in this case we're done!

Everything still not crossed out is prime.

Of course, if we had a higher limit there would be more to do, but we would still only have to go up to the square root of our limit.
So that's cool - now we have all the primes up to 150, and you can see how to do that. We can generalise this idea to get the primes within a range, but that's a bit more work to get right, and there are some icky details. But it's pretty efficient if you want all primes in a given range.

So why am I telling you this?

Well, let's do the same thing, but with a twist. We start the same way, and we write down the numbers from 2 up to 150 (or whatever our chosen limit might be). We again circle the first number that's not crossed out (and again that will be 2) but now we throw in a bit of randomness.

Instead of crossing out every 2nd number, we randomly cross out every number with probability 1/2. The result will be about the same number of crossings out, but they won't be precisely the even numbers.

In particular, I don't know what the next number might be - it might be 3, 4, or anything, really. But whatever the next number is, let's call it K.

So we circle K, and then independently for each number after K, cross it out with probability 1/K.

We'll call the circled numbers Random Eratosthenetic Pseudo-Primes (REPPs).

We'll get different results each time we do this, but now we can look at the expected distribution of the REPPs. These have emerged from the random process, so in some sense they are randomly chosen, but there has been structure to the process that created them, so we would expect there to be structure in the chosen ones.

We can ask about their expected density, and whether we expect there to be infinitely many. We can ask whether there will be long gaps, and whether there will be (in expectation) REPPs that are close together. In short, we can ask all the same sorts of questions about the REPPs that get asked about the primes, and since the process used to generate them is superficially similar, perhaps the behaviour and structure of these numbers will be similar to the behaviour and structure of the primes.

I've heard that REPPs do have the same sort of structure as the true primes. I've heard that their density is indistinguishable from that of the true primes. I've also heard that major results for the true primes are also true (with probability 1) for the REPPs.

None of this (assuming true - can anyone confirm?) is conclusive evidence for anything, but it does go some way to explaining why people think of the primes as being "somewhat random," and why some conjectures can be remarkably difficult to prove.

Examples? Here are just two:

  • Are there infinitely many twin primes?
  • Is every even number the sum of two primes?


<<<< Prev <<<<
Wrapping Up Square Dissection
:
>>>> Next >>>>
Multiple Choice Probability Puzzle ...


You should follow me on twitter @ColinTheMathmo

Comments

I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate.

If the number of emails/comments gets too large to handle then I might return to a semi-automated system. We'll see.


Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!