# Prime Number sieve about 5 and 7 **URL:** \ **Category:** Factual Questions\ **Created:** [October 3, 2012, 1:37am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539 "2012-10-03T01:37:37Z")\ **Posts on this page:** 12\ **Page:** 2
**Author:** ![Exapno\_Mapcase](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/exapno_mapcase/32/1051_2.png) [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)\ **Post date:** [October 3, 2012, 6:56pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/21 "2012-10-03T18:56:19Z")
> [@gnoitall](#): > > Is Abraham Lincoln still the 16th President? Depends on whether you count [David Rice Atchison](http://en.wikipedia.org/wiki/David_Rice_Atchison#.22President_for_One_Day.22). ---
**Author:** ![Darth\_Panda](https://avatars.discourse-cdn.com/v4/letter/d/ee7513/32.png) [@Darth\_Panda](https://boards.straightdope.com/u/Darth_Panda)\ **Post date:** [October 3, 2012, 7:06pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/22 "2012-10-03T19:06:24Z")
> [@gnoitall](#): > > Is Abraham Lincoln still the 16th President? Not if you count the Presidents of the Continental Congress under the Articles of Confederation prior to the adoption of the Constitution. ---
**Author:** ![Senegoid](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/senegoid/32/6606_2.png) [@Senegoid](https://boards.straightdope.com/u/Senegoid)\ **Post date:** [October 4, 2012, 4:33am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/23 "2012-10-04T04:33:26Z")
With apologies to @ **Enola Straight** : As you can see, we seem to be having some difficulty staying on-topic here, despite several (not highly successful) attempts seriously to discuss primes and Sieves and such. I think after that .999… thread, we must all be just a little burnt out on math threads, or something like that. Our attention spans have become countable and finite. ---
**Author:** ![ZenBeam](https://avatars.discourse-cdn.com/v4/letter/z/3ab097/32.png) [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)\ **Post date:** [October 4, 2012, 4:15pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/24 "2012-10-04T16:15:38Z")
> [@gnoitall](#): > > Is Abraham Lincoln still the 16th President? \ No prime numbered president was assassinated. And only one died in office. ---
**Author:** ![Exapno\_Mapcase](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/exapno_mapcase/32/1051_2.png) [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)\ **Post date:** [October 4, 2012, 6:01pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/25 "2012-10-04T18:01:33Z")
> [@ZenBeam](#): > > \ No prime numbered president was assassinated. And only one died in office. If Lincoln was number 17, then both statements are wrong. ---
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [October 4, 2012, 6:19pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/26 "2012-10-04T18:19:55Z")
(6x-1)-5x-7x 11…17…23…29…41…47 53…59…71…83…89…101 107…113…131…137…143…149 167…173…179…191…197…209 221…227…233…239…251…257 (6x+1)-5x-7x 13…19…31…37…43…61 67…73…79…97…103…109 121…127…139…151…157…163 169…181…187…193…199…211 223…229…241…247…253…271 Apparently, the answer to my OP is…no. ☹ ---
**Author:** ![j\_sum1](https://avatars.discourse-cdn.com/v4/letter/j/8baadc/32.png) [@j\_sum1](https://boards.straightdope.com/u/j_sum1)\ **Post date:** [October 4, 2012, 9:46pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/27 "2012-10-04T21:46:37Z")
The diagonalisation pattern you see with the fives and the sevens is a result of overlaying two arithmetic progressions in an array format. I could write out the sequence 21x+7 in rows of 8 and highlight every multiple of 13. I would get a repeating diagonal pattern emerge. It really has nothing to do with the sieve or the arrangement of primes. Here is what you have attempted. You have arranged the naturals in rows of 6. Sensible thing to do since after applying the sieve twice you have the two sequences 6x-1 and 6x+1. You can clearly see that the sieve takes out four whole columns. So far so good. Next you arrange what is left again in rows of 6. I am not sure why you would do this. You find that the multiples of 5 and 7 form a pattern, but this isn’t a real surprise. Next iteration, the numbers remaining ion the sieve are not in arithmetic progression. Now if you highlight a particular multiple, the diagonal pattern will be broken. Each further iteration will only break up the pattern further. In other words, The pattern you see is a result of APs. The sieve produces 2 APs after the first iteration and so you observe the pattern. Arranging the numbers in an array of 6 (or any other number) is not a long-term help to applying the sieve. ---
**Author:** ![j\_sum1](https://avatars.discourse-cdn.com/v4/letter/j/8baadc/32.png) [@j\_sum1](https://boards.straightdope.com/u/j_sum1)\ **Post date:** [October 4, 2012, 10:07pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/28 "2012-10-04T22:07:03Z")
Here is a slightly more systematic approach to applying the sieve of Eratosthenes and arranging the numbers in an array. Iteration one Arrange the naturals in two columns. Eliminate every multiple of 2. The column that remains is the AP 2n-1. Iteration two Arrange the naturals in 6 columns. After eliminating multiples of 2, only three columns remain. Eliminating all multiples of 3 leaves two columns – two APs, 6n-1 and 6n-5 (6n-5 refers to the same column as 6n+1) Iteration three Arrange the naturals in 30 columns Having eliminated the multiples of 2 and 3, only 10 columns are left. Eliminating multiples of five wipes out another 2 columns, leaving 8: 30n+1, 30n+7, 30n+11, 30n+13, 30n+17, 30n+19, 30n+23, 30n+29 Next iteration would have 210 columns. of which 154 have already been eliminated. Knocking out the multiples of 7 would take out several of these leaving about 50 APs to work with. I can’t see that this approach is actually an advantage to using the sieve or provides a whole lot of insight into the arrangement of the primes, but I might be wrong. Incidentally, as I understand it, the main reason for excluding 1 from the primes is that including it destroys the property that the naturals each have a unique prime factorisation. ---
**Author:** ![Little\_Nemo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/little_nemo/32/3120_2.png) [@Little\_Nemo](https://boards.straightdope.com/u/Little_Nemo)\ **Post date:** [October 5, 2012, 12:57am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/29 "2012-10-05T00:57:05Z")
> [@gazpacho](#): > > It used to be but have 1 as a prime number meant a lot of theorems had to use statements like “all the prime numbers except 1”. Mathematicians found that removing 1 from the list of prime numbers made the list more useful. Or they were just being lazy. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [October 5, 2012, 4:43am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/30 "2012-10-05T04:43:01Z")
[John Conway’s Prime Producing Machine](http://www.dms.umontreal.ca/~andrew/conwaymachine.html), although ridiculously impractical, may seem amazing! By repeatedly comparing a variable against 14 fractions, all the primes are produced! [Here’s another link](http://www.jstor.org/discover/10.2307/2690263?uid=3739136&uid=2129&uid=2&uid=70&uid=4&sid=21101282054107) describing what the machine in first link is doing. I don’t know if it relates to OP’s intent, but the numbers S[sub]a[/sub] = {30a,30a+1,30a+2,…,30a+29}, a\>0, contain only eight prime candidates (ten numbers of the form 6x+1 or 6x-1, less 30a+5 and 30a+25.) High-speed primality testers will often handle the first 30 million integers or so with a lookup table, getting 30-to-8 compression by just coding the numbers in S[sub]a[/sub]. ---
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [October 17, 2012, 6:52pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/31 "2012-10-17T18:52:46Z")
I have been looking at the exceptions to the 6x-1:6x+1 rule. 25, 35, 49, 55, 65, 77, 85, 91, 95…etc These numbers are composite…products of two primes…_so…_ (6a-1)(6b-1)…(6a-1)(6b+1)…(6a+1)(6b+1) 25…35…49, the first the exceptions, when a and b equal 1. Other composites occur when a and b are independently valued. C=.a_b 25=5_5 35=5_7 49=7_7 55=5_11 65=5_13 77=7_11 85=5_17 91=7_13 95=5_19 etc Values of a and b do not seem to increase in any obvious mathematical progression. Has any work been done along these lines? ---
**Author:** ![Malacandra](https://avatars.discourse-cdn.com/v4/letter/m/45deac/32.png) [@Malacandra](https://boards.straightdope.com/u/Malacandra)\ **Post date:** [October 17, 2012, 8:25pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/32 "2012-10-17T20:25:07Z")
> [@j\_sum1](#): > > Incidentally, as I understand it, the main reason for excluding 1 from the primes is that including it destroys the property that the naturals each have a unique prime factorisation. Yes. All natural numbers have at least two factors - exactly two, if they are prime - except 1, which has only one. That, I guess, makes it sub-prime, and you know how much trouble _that_ caused. [Previous page](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539.md?page=1)