Maths: primes and composites

Etching of an ancient seal identified as Eratosthenes.

The sieve of Eratosthenes

This is an ancient method (or algorithm) for finding prime numbers in a range of numbers. Write down all of the integers between 1 and n, then go through and cross out every second number starting at 4, every third number starting at 6, every fifth number from 10 on, seventh number beginning with 14 and so on. Some numbers will be crossed out more than once, but that doesn’t matter.

You end up with a sequence like this, where the bold numbers are the ones crossed out:

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…

Runs of composites

The aim here is to explore the natural sequence of integers for runs of consecutive integers that are composite, meaning they have factors. Two examples are series like 8, 9, 10, or 24, 25, 26, 27, 28. (Look at the example above: the crossed-out bold bunches are runs of composites.)

I started using a spreadsheet to help me search for runs longer than five composites, but for a while, the best I found was seven in a row: is there any link between the central number in the first example of any run of a particular size? Note that there will always BE a central number, as the totals will always be odd. Can you prove this? I can…

In October 2002, I found a run of 33 consecutive composite numbers, all of them less than 10,000. I used a spreadsheet to do it, and here are a couple of helpful hints.

* Note that I used the =IF function quite a bit…

* To test if a number x is exactly divisible by another number n, you use the form x/n=INT(x/n). I have some kludgy spreadsheet solutions, but no really good ones…

Play with it!

Because even numbers are always composites, and odd numbers are only sometimes composite, each string of composites will start and end with an even number. This means that every string will have an odd number of members. The numbers 8 to 10, 24 to 28 and 90 to 96 represent some of the strings that can be found with ease. For larger sequences, it is possible to construct a spreadsheet that will test for primeness, set flags for all composite numbers, and display longer sequences. Sadly, the margins of this book are too narrow for me to set the method out fully.

One way of generating a string of guaranteed composites is to take the series n! + (2, 3 … n). That is a tricky bit of notation. 5! = 5x4x3x2x1, and one string of composites will be 122, 123, 124, 125, but that is part of a larger string: that sequence is a guaranteed set, that's all. You do the rest.

Side note: n!-1 is often (but not always) prime, and the primes get rarer, once n exceeds 40.

To search this blog, use this link and then use the search box

Another way: use the index!