# 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:** 20\ **Page:** 1
**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 3, 2012, 1:37am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/1 "2012-10-03T01:37:37Z")
As Doper resident mathematicians may know, excepting 2 and 3, all prime numbers are of the form 6x-1 or 6x+1 6X…6X-1…2X…3X…2X…6X+1 0…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…38…39…40…41 42…43…44…45…46…47 48…49…50…51…52…53 54…55…56…57…58…59 60…61…62…63…64…65 66…67…68…69…70…71 72…73…74…75…76…77 78…79…80…81…82…83 84…85…86…87…88…89 90…91…92…93…94…95 96…97…98…99…100…101 multiples of 5 and 7 6X-1 5…11…17…23…29…35 41…47…53…59…65…71 77…83…89…95…101…107 113…119…125…131…137…143 149…155…161…167…173…179 185…191…197…203…209…215 221…227…233…239…245…251 6X+1 7…13…19…25…31…37 43…49…55…61…67…73 79…85…91…97…103…109 115.121…127…133…139…145 151.157…163…169…175…181 187.193…199…205…211…217 223.229…235…241…247…253 As you see, This is a modified Sieve of Eratosthnes (sp?) Arrays 6x-1 and 6x+1 are made of selected elements of the original array up top. (notice, the diagonal lines of 5 and 7 multiples are found in the original array as well) If multiples of 5 and 7 are sieved out and the remnants are re-arranged into a new 6-by-infinity array could you sieve out 11 and 13 the way the above arrays sieved out 2-by-3 and 5-by-7? ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 3, 2012, 2:50am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/2 "2012-10-03T02:50:07Z")
Yes, of course, followed by the multiples of 17, 19, 23, etc. That’s just what the Sieve of Eratosthenes is. Unless I’m misunderstanding what you’re asking? ---
**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\ **Post date:** [October 3, 2012, 3:23am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/3 "2012-10-03T03:23:44Z")
Reminds me of the story of how different professions determine that all odd numbers are prime. Mathematician: “1 is prime, 3=1+2 is prime, 5=3+2 is prime, 7=5+2 is prime… therefore by induction, all odd numbers are prime!” Physicist: “1 is prime, 3 is prime, 5 is prime, 7 is prime, 9… experimental error, 11 is prime and so on. Therefore by experiment, all odd numbers are prime.” Engineer: “1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime and so on. Therefore all odd numbers are prime!” Lawyer: “What’s a prime?” ---
**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 3, 2012, 3:37am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/4 "2012-10-03T03:37:40Z")
> [@Enola\_Straight](#): > > If multiples of 5 and 7 are sieved out and the remnants are re-arranged into a new 6-by-infinity array could you sieve out 11 and 13 the way the above arrays sieved out 2-by-3 and 5-by-7? I mean: 11…17…23…29…41…47 53…59…61…83…89…101 etc,etc 13…19…31…37…43…61 67…73…79…97…103…109 etc.etc Extended out to infinity, can these two arrays display a pattern in multiples of 11 or 13? ---
**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 3, 2012, 3:44am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/5 "2012-10-03T03:44:01Z")
> [@Enola\_Straight](#): > > As Doper resident mathematicians may know, excepting 2 and 3, all prime numbers are of the form 6x-1 or 6x+1 That seems a little obvious. 6x is (2x3)x. That means that (2x3)x can’t be prime - it’s a multiple of 2 and 3 (2x3)x plus or minus 2 can’t be prime - it’s a multiple of 2 (2x3)x plus or minus 3 can’t be prime - it’s a multiple of 3 So all primes above 2 and 3 would have to be 6x-1 or 6x+1 ---
**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 3, 2012, 3:52am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/6 "2012-10-03T03:52:54Z")
> [@Enola\_Straight](#): > > As Doper resident mathematicians may know, excepting 2 and 3, all prime numbers are of the form 6x-1 or 6x+1 This is true, but using this fact to find primes still has a problem. You can immediately rule out all numbers OTHER than 6x-1 and 6x+1 numbers. Among the numbers remaining (the 6x-1 and 6x+1 forms), _some_ of those will be prime and some will not. You still need a sieve of some sort, or else do all the trial divisions, to decide which additional 6x-1 and 6x+1 numbers to cross out. The placement of primes and composites among those 6x-1 and 6x+1 numbers will be irregular. I’m not immediately sure what patterns you could find, by which to do this – other than to work with a full sieve with ALL the integers – BUT, one quick abbreviation you could do is to build a sieve with only the ODD numbers, omitting the evens. I wrote a computer program once to do a sieve like that. For example, if you built an abbreviated sieve of some sort like this, how would you count out ever 7th number to cross out, or every 11th number or ever 13th number? ETA: However, at least it’s nice to have a math topic to discuss other than the one true value of .999… . . . ---
**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 3, 2012, 5:35am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/7 "2012-10-03T05:35:38Z")
> [@Senegoid](#): > > ETA: However, at least it’s nice to have a math topic to discuss other than the one true value of .999… . . . So let’s start another Monty Hall thread. ---
**Author:** ![Wendell\_Wagner](https://avatars.discourse-cdn.com/v4/letter/w/8491ac/32.png) [@Wendell\_Wagner](https://boards.straightdope.com/u/Wendell_Wagner)\ **Post date:** [October 3, 2012, 10:09am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/8 "2012-10-03T10:09:34Z")
Is .9999… prime? ---
**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 3, 2012, 10:23am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/9 "2012-10-03T10:23:55Z")
Back to the OP’s subject … Let me clarify… I think the OP is asking: Can we create an array of numbers having only the 6x-1 and 6x+1 entries (or other such abbreviated arrays) and use that for a Sieve of Eratosthenes? My answer above was NO, but let me be clear: I really meant: No, not to the best of my knowledge. I never really thought it out in much depth beyond that. I did a Sieve once (a computer program) that started with the odd numbers only, and used a compact bit table to represent those. It crossed off numbers by setting individual bits to 0. Thus, it could do a tremendously large sieve in a small amount of memory, and it was blazingly fast. So, maybe some more sophisticated number theorist has a better answer? Can you do a more abbreviated Sieve something like what the OP seems to be asking? At the very least, I think it would have to be sort of tricky. But number theory always is. ---
**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 3, 2012, 10:28am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/10 "2012-10-03T10:28:10Z")
> [@Wendell\_Wagner](#): > > Is .9999… prime? .9999… = 1 right? (Uh… Right? RIGHT?) :eek: Is that prime? Is 1.9999… prime? Is 2.9999… prime? Is 3.9999… prime? Is 4.9999… prime? And so forth. Choose one: 😃 :dubious: :smack: ---
**Author:** ![core\_dump](https://avatars.discourse-cdn.com/v4/letter/c/dec6dc/32.png) [@core\_dump](https://boards.straightdope.com/u/core_dump)\ **Post date:** [October 3, 2012, 10:45am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/11 "2012-10-03T10:45:57Z")
> [@Enola\_Straight](#): > > multiples of 5 and 7 > 6X-1 > > 5…11…17…23…29…35 > 41…47…53…59…65…71 > 77…83…89…95…101..107 > 113..119..125..131..137..143 > 149..155..161..167..173..179 > 185..191..197..203..209..215 > 221..227..233..239..245..251 I think I see what you mean here. If we start with the above matrix and take a modulo 26 of it all, we get: 05 11 17 23 03 09 15 21 01 07 13 19 25 05 11 17 23 03 09 15 21 01 07 13 19 25 05 11 17 23 03 09 15 21 01 07 13 19 25 05 11 17 And then using a crude cipher (A=1, B=2, etc) yields the following: E K Q W C I O U A G M S Y E K Q W C I O U A G M S Y E K Q W C I O U A G M S Y E K Q It spells “QUAKE” not once but in several places. I believe you have predicted the end is near? ---
**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, 10:58am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/12 "2012-10-03T10:58:06Z")
> [@core\_dump](#): > > It spells “QUAKE” not once but in several places. I believe you have predicted the end is near? Either that or some kind fps convention. ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [October 3, 2012, 11:01am UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/13 "2012-10-03T11:01:03Z")
Now, you can make a list of offsets for any product of primes, not just 6 - but for other products, the list will be much longer than 6x-1,6x+1. For instance, all primes above 5 also fall into one of the following four groups: 10x - 3, 10x - 1, 10x + 1, 10x + 3 This is what you get from sieving the multiples of 2 and 5 out of a repeating 10\*x grid. It’s also a different way of restating that all primes above 5 end with a 1, 3, 7, or 9. But unfortunately building rule sets like this doesn’t really help that much with finding big primes, especially since it’s the largest factors that are the hardest to spot. ---
**Author:** ![CurtC](https://avatars.discourse-cdn.com/v4/letter/c/ce73a5/32.png) [@CurtC](https://boards.straightdope.com/u/CurtC)\ **Post date:** [October 3, 2012, 1:25pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/14 "2012-10-03T13:25:04Z")
> [@md2000](#): > > Mathematician: "1 is prime, 3=1+2 is prime… A mathematician should know that 1 is NOT prime. > [@Wendell\_Wagner](#): > > Is .9999… prime? No. ---
**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, 2:54pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/15 "2012-10-03T14:54:31Z")
What about .2357111317192329… Is it transcendental? ---
**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 3, 2012, 3:47pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/16 "2012-10-03T15:47:13Z")
> [@Exapno\_Mapcase](#): > > What about .2357111317192329… > > Is it transcendental? That certainly transcends my merely countable knowledge of the subject. Oh, BTW: Since .9999… doesn’t end with 3, 5, 7, or 9, it may very possibly be prime. But 1 is NOT prime. Hence, it is doubtful that .9999… = 1. :o Here’s an actually interesting tydbyt: When I was in high school, I read about palindromic primes. One of the interesting things about palindromic primes is that I couldn’t see any reason they should be interesting, except that they are. So much for intuition in mathematics. I wrote a program to find a bunch. (I was just learning Fortran II at the time.) I noticed big gaps in their distribution: The entire range 1000 through 9999 had not a single one. I then figured out – and proved – that ANY palindromic number with an even number of digits must be divisible by 11. Thus, 11 itself can be the only palindromic prime with an even number of digits. Today, of course, [everyone knows that](http://en.wikipedia.org/wiki/Palindromic_prime). ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [October 3, 2012, 5:13pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/17 "2012-10-03T17:13:15Z")
> [@Exapno\_Mapcase](#): > > What about .2357111317192329… > > Is it transcendental? That’s the [Copeland-Erdos Constant,](http://mathworld.wolfram.com/Copeland-ErdosConstant.html) and according to [this StackExchange thread](http://math.stackexchange.com/questions/197505/is-0-23571113171923293137-dots-transcendental), it’s not known whether it’s transcendental or not. ---
**Author:** ![gazpacho](https://avatars.discourse-cdn.com/v4/letter/g/6f9a4e/32.png) [@gazpacho](https://boards.straightdope.com/u/gazpacho)\ **Post date:** [October 3, 2012, 6:23pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/18 "2012-10-03T18:23:20Z")
> [@Wendell\_Wagner](#): > > Is .9999… prime? 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. > **[Prime number | Primality of one](https://en.wikipedia.org/wiki/Prime_number#Primality_of_one)** > > Most early Greeks did not even consider 1 to be a number, so they could not consider its primality. A few scholars in the Greek and later Roman tradition, including Nicomachus, Iamblichus, Boethius, and Cassiodorus, also considered the prime numbers to be a subdivision of the odd numbers, so they did not consider ⁠ > > > > 2 > > > {\\displaystyle 2} > > ⁠ to be prime either. However, Euclid and a majority of the other Greek mathematicians considered ⁠ > > > If 1 we... > **[Why is the number one not a prime?](https://t5k.org/notes/faq/one.html)** > > Another page about Prime Numbers and related topics. ---
**Author:** ![gnoitall](https://avatars.discourse-cdn.com/v4/letter/g/bb73d2/32.png) [@gnoitall](https://boards.straightdope.com/u/gnoitall)\ **Post date:** [October 3, 2012, 6:36pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/19 "2012-10-03T18:36:21Z")
> [@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. > > [Prime number - Wikipedia](http://en.wikipedia.org/wiki/Prime_number#Primality_of_one) > > [Why is the number one not a prime?](http://primes.utm.edu/notes/faq/one.html) What? Great. Pluto’s not a planet. 1’s not prime. Is Abraham Lincoln still the 16th President? ---
**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\ **Post date:** [October 3, 2012, 6:52pm UTC](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539/20 "2012-10-03T18:52:27Z")
> [@gnoitall](#): > > What? > > Great. Pluto’s not a planet. 1’s not prime. > > Is Abraham Lincoln still the 16th President? No, Obama’s president now. I think we’re well past 16. Lincoln’s past his prime… [Next page](https://boards.straightdope.com/t/prime-number-sieve-about-5-and-7/636539.md?page=2)