# Primes **URL:** \ **Category:** Factual Questions\ **Created:** [October 30, 2014, 12:54pm UTC](https://boards.straightdope.com/t/primes/702997 "2014-10-30T12:54:11Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 12:54pm UTC](https://boards.straightdope.com/t/primes/702997/1 "2014-10-30T12:54:11Z")
I know that all primes can be expressed as 6n±1. But can more primes be expressed as 6n+1 than 6n-1 or is the number of primes that can be expressed as 6n+1 equal to the number of primes that can be expressed as 6n-1? ---
**Author:** ![Dead\_Cat](https://avatars.discourse-cdn.com/v4/letter/d/9fc29f/32.png) [@Dead\_Cat](https://boards.straightdope.com/u/Dead_Cat)\ **Post date:** [October 30, 2014, 1:20pm UTC](https://boards.straightdope.com/t/primes/702997/2 "2014-10-30T13:20:18Z")
> [@armstrongm](#): > > I know that all primes can be expressed as 6n±1. Apart from 2 and 3, unless you allow n to be a non-integer, which would render the whole thing meaningless. I’m sure you realise this, but it’s best to be precise with mathematical statements. Anyway, with the exception of 2 or 3, this is simply a manifestation of the fact that primes cannot be a multiple of 2 or 3. All numbers not of the form 6n-1 or 6n+1 are multiples of at least one of 2 or 3 (I haven’t checked this rigorously, but 6n is clearly a multiple of 6 (and so not prime), 6n +/- 2 is clearly a multiple of 2 (and so not prime), and 6n +/- 3 is clearly a multiple of 3 (and so not prime) - no doubt a simple proof exists). In terms of your original question, I’ve checked the primes up to 100 (which I know is next to useless in terms of a mathematical proof, I was just interested) and found they appear to be equal up to that point, so I suspect that holds forever - but I would like to see a proof of it. ---
**Author:** ![naita](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/naita/32/5862_2.png) [@naita](https://boards.straightdope.com/u/naita)\ **Post date:** [October 30, 2014, 1:31pm UTC](https://boards.straightdope.com/t/primes/702997/3 "2014-10-30T13:31:28Z")
> [@Dead\_Cat](#): > > Anyway, with the exception of 2 or 3, this is simply a manifestation of the fact that primes cannot be a multiple of 2 or 3. All numbers not of the form 6n-1 or 6n+1 are multiples of at least one of 2 or 3 (I haven’t checked this rigorously, but 6n is clearly a multiple of 6 (and so not prime), 6n +/- 2 is clearly a multiple of 2 (and so not prime), and 6n +/- 3 is clearly a multiple of 3 (and so not prime) - no doubt a simple proof exists). Say p is prime and larger than 3. The p-1 and p+1 are both divisible by two, and p-1, p, p+1 are three consecutive numbers so one of them is divisble by three, and it isn’t p. So one of those numbers has to be divisble by 6, and p can then be described as 6n+1 or 6n-1. I’ve usually seen this as the more amusing problem “prove that p^2 - 1 is divisble by 24 if p is a prime larger than 3”. ---
**Author:** ![Dead\_Cat](https://avatars.discourse-cdn.com/v4/letter/d/9fc29f/32.png) [@Dead\_Cat](https://boards.straightdope.com/u/Dead_Cat)\ **Post date:** [October 30, 2014, 1:37pm UTC](https://boards.straightdope.com/t/primes/702997/4 "2014-10-30T13:37:15Z")
Oops - too late to edit, I notice I made in error in my post above, by erroneously counting 91 as prime. In fact, on rechecking the primes up to 400, I can’t find any sequence (apart from the first 6) where the number of primes with the form 6n-1 equals the number with 6n+1, 6n-1 is always slightly ahead. Again, useless as a mathematical proof, but I’m still keen to hear if there is an answer. Incidentally, while it doesn’t seem to answer the question at hand (which also makes me think there isn’t an answer), the OP and others may find the excellent site [The Prime Pages](https://primes.utm.edu/index.html), in particular [Prime Curios!](https://primes.utm.edu/curios/) ---
**Author:** ![Dead\_Cat](https://avatars.discourse-cdn.com/v4/letter/d/9fc29f/32.png) [@Dead\_Cat](https://boards.straightdope.com/u/Dead_Cat)\ **Post date:** [October 30, 2014, 1:39pm UTC](https://boards.straightdope.com/t/primes/702997/5 "2014-10-30T13:39:41Z")
> [@naita](#): > > Say p is prime and larger than 3. The p-1 and p+1 are both divisible by two, and p-1, p, p+1 are three consecutive numbers so one of them is divisble by three, and it isn’t p. So one of those numbers has to be divisble by 6, and p can then be described as 6n+1 or 6n-1. > > I’ve usually seen this as the more amusing problem “prove that p^2 - 1 is divisble by 24 if p is a prime larger than 3”. Nice, thanks! ---
**Author:** ![naita](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/naita/32/5862_2.png) [@naita](https://boards.straightdope.com/u/naita)\ **Post date:** [October 30, 2014, 1:39pm UTC](https://boards.straightdope.com/t/primes/702997/6 "2014-10-30T13:39:55Z")
In the first 166 such primes there are 48.2 % 6n+1, in the first 998 there are 49,1 %. Checking any more is too much work to confirm my suspicion that it’s 50-50 overall. ---
**Author:** ![naita](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/naita/32/5862_2.png) [@naita](https://boards.straightdope.com/u/naita)\ **Post date:** [October 30, 2014, 1:46pm UTC](https://boards.straightdope.com/t/primes/702997/7 "2014-10-30T13:46:04Z")
> [@naita](#): > > In the first 166 such primes there are 48.2 % 6n+1, in the first 998 there are 49,1 %. > Checking any more is too much work to confirm my suspicion that it’s 50-50 overall. I lied, it wasn’t that much work. In the first 9998 such primes there are 49.89% 6n+1. ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 1:55pm UTC](https://boards.straightdope.com/t/primes/702997/8 "2014-10-30T13:55:34Z")
I have got the first ten thousand primes on excel on my laptop. I checked the first 0-300 primes then I checked the likelihood of 6n+1 and 6n-1 for every 100 primes after. So the first 400 then 500 then 600 etc. primes up to and including the 5155th prime. In every 100 band there was always more primes that could be written as 6n-1. I was wondering if this was a well known mathematical conjecture or if I had discovered something that was not previously known. ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [October 30, 2014, 1:58pm UTC](https://boards.straightdope.com/t/primes/702997/9 "2014-10-30T13:58:18Z")
To directly answer the question, there are infinitely many examples of both, and both sets are countably infinite. I suppose you can take that to mean both are the same “size”, as long as you understand that the “size” of infinitely large sets is a non-trivial concept in itself. ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 2:00pm UTC](https://boards.straightdope.com/t/primes/702997/10 "2014-10-30T14:00:18Z")
I understand that it tends towards being 50% each as a percentage which is what I would expect seeing as the distribution of primes is random. Although I understand there are pseudo random because one can find the next term in the sequence. Even though they tend towards being 50% each the difference in the number of primes that can be written as 6n-1 and 6n+1 grows. Just before someone points it out this is a trend over the primes I have been able to test and the difference between them does ebb and flow. I would also like to apologise in my original post I was slightly confused by the way that I accumulated my data and tested. The data did from the outset indicate that there may be more primes that can be written as 6n-1 than 6n+1. ---
**Author:** ![Great\_Antibob](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@Great\_Antibob](https://boards.straightdope.com/u/Great_Antibob)\ **Post date:** [October 30, 2014, 2:04pm UTC](https://boards.straightdope.com/t/primes/702997/11 "2014-10-30T14:04:29Z")
To follow up, I see you are talking about the _ **density** _ of primes, rather than the total number, i.e. how many primes you might find per 1000, for example. In that case, there is a [theorem from Dirichlet](http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions) that basically shows that the density of primes of the form 6k-1 and 6k+1 is the same over a long enough window. You may get some exceptions in the first 1000 or so primes or in isolated windows, but the “general trend” will be for both to produce the same density of primes. And, actually, this was brought up in an [earlier thread](http://boards.straightdope.com/sdmb/showthread.php?t=638975) from a couple years ago (~post 20 or so). ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 2:04pm UTC](https://boards.straightdope.com/t/primes/702997/12 "2014-10-30T14:04:39Z")
> [@Great\_Antibob](#): > > To directly answer the question, there are infinitely many examples of both, and both sets are countably infinite. > > I suppose you can take that to mean both are the same “size”, as long as you understand that the “size” of infinitely large sets is a non-trivial concept in itself. Yes I agree the size of each data set will be infinitely large rather than both sets being equal to infinity. Although this may be open to debate as it opens up the question what is infinity divided by two anyway? I don’t know. As one gets larger the small difference between each data set may become insignificant in any event as infinity -2 = infinity. But I am of the view as some people who have posted on this thread have tested to far higher values than me that there is most likely more primes that can be written as 6n-1 than 6n+1. ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 2:11pm UTC](https://boards.straightdope.com/t/primes/702997/13 "2014-10-30T14:11:58Z")
> [@Great\_Antibob](#): > > To follow up, I see you are talking about the _ **density** _ of primes, rather than the total number, i.e. how many primes you might find per 1000, for example. > > In that case, there is a [theorem from Dirichlet](http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions) that basically shows that the density of primes of the form 6k-1 and 6k+1 is the same over a long enough window. You may get some exceptions in the first 1000 or so primes or in isolated windows, but the “general trend” will be for both to produce the same density of primes. I think I may be have mislead you by mistake. I have no knowledge about what the density of primes looks like or the number of primes in a given range of numbers. There are some theorems that describe it like the one you have mentioned that I am unable to fully understand. I don’t fully understand all the mathematical tools that were used in proving them. The way that I view it is the following. I think that the percentage of primes written as 6n-1 and 6n+1 will, in my humblest opinion, most likely tend towards 50%. When you reach infinity this will, in all likelihood, be the case. But they will only ever tend towards 50% for any range of data sets I do not think that they will be 50%. I am of the view that for all numbers less than infinity there will be more primes that can be written using the notation 6n-1 than 6n+1 in absolute terms. ---
**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 30, 2014, 2:38pm UTC](https://boards.straightdope.com/t/primes/702997/14 "2014-10-30T14:38:04Z")
> [@armstrongm](#): > > Yes I agree the size of each data set will be infinitely large rather than both sets being equal to infinity. Although this may be open to debate as it opens up the question what is infinity divided by two anyway? I don’t know. As one gets larger the small difference between each data set may become insignificant in any event as infinity -2 = infinity. But I am of the view as some people who have posted on this thread have tested to far higher values than me that there is most likely more primes that can be written as 6n-1 than 6n+1. Since the two sets are countably infinite, they can be placed into one-to-one correspondence. So they are exactly equal. The primes themselves can be placed into one-to-one correspondence with the integers, so they are also exactly equal. Yet common sense would tell us that the primes are fewer than the integers everywhere you can possibly look. That’s why common sense is a terrible tool to use with math. ---
**Author:** ![naita](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/naita/32/5862_2.png) [@naita](https://boards.straightdope.com/u/naita)\ **Post date:** [October 30, 2014, 2:41pm UTC](https://boards.straightdope.com/t/primes/702997/15 "2014-10-30T14:41:47Z")
> [@armstrongm](#): > > I think I may be have mislead you by mistake. I have no knowledge about what the density of primes looks like or the number of primes in a given range of numbers. There are some theorems that describe it like the one you have mentioned that I am unable to fully understand. I don’t fully understand all the mathematical tools that were used in proving them. > > The way that I view it is the following. I think that the percentage of primes written as 6n-1 and 6n+1 will, in my humblest opinion, most likely tend towards 50%. When you reach infinity this will, in all likelihood, be the case. But they will only ever tend towards 50% for any range of data sets I do not think that they will be 50%. I am of the view that for all numbers less than infinity there will be more primes that can be written using the notation 6n-1 than 6n+1 in absolute terms. This may be the case. But if you start at 1001 and go to 10000 the number swings above 50% several times. It could just be that there are more such numbers in the first 1000 and that permanently skews the ratio. It could also be we haven’t looked at enough numbers. ---
**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 30, 2014, 2:43pm UTC](https://boards.straightdope.com/t/primes/702997/16 "2014-10-30T14:43:00Z")
> [@Great\_Antibob](#): > > In that case, there is a [theorem from Dirichlet](http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions) that basically shows that the density of primes of the form 6k-1 and 6k+1 is the same over a long enough window… I don’t see how the conclusion follows from Dirichlet’s theorem. In fact, I wonder if [Chebyshev’s bias](https://en.wikipedia.org/wiki/Chebyshev%27s_bias) implies the opposite. ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 2:51pm UTC](https://boards.straightdope.com/t/primes/702997/17 "2014-10-30T14:51:17Z")
> [@naita](#): > > This may be the case. But if you start at 1001 and go to 10000 the number swings above 50% several times. It could just be that there are more such numbers in the first 1000 and that permanently skews the ratio. It could also be we haven’t looked at enough numbers. I have thought of that possibility as well. I am however, sure that it will in fact take place. I have written down how the absolute difference between the number of primes written as 6n+1 and 6n-1 changes. You are correct that is does swing. The problem with saying that it might be skewed by a value is that the number of primes that can be written as 6n-1 appears to be increasing. Of course there are times where the difference narrows it fell from quite sharply at one point. But, for all the intervals I checked it never once fell below 6. That is for the first 5154 primes. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [October 30, 2014, 2:55pm UTC](https://boards.straightdope.com/t/primes/702997/18 "2014-10-30T14:55:32Z")
> [@septimus](#): > > I don’t see how the conclusion follows from Dirichlet’s theorem. In fact, I wonder if [Chebyshev’s bias](https://en.wikipedia.org/wiki/Chebyshev%27s_bias) implies the opposite. If I understand correctly, Chebyshev’s Bias is about which progression contains more primes in absolute terms, not about the relative density: these are two different things. For example, consider the progression of positive integers: 1, 2, 3, 4, … The relative density of odd numbers and even numbers is the same (50% for both). But the number of odd numbers up to any given point is never less than, and half the time greater than, the number of even numbers up to that point. ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 3:07pm UTC](https://boards.straightdope.com/t/primes/702997/19 "2014-10-30T15:07:28Z")
> [@Thudlow\_Boink](#): > > If I understand correctly, Chebyshev’s Bias is about which progression contains more primes in absolute terms, not about the relative density: these are two different things. For example, consider the progression of positive integers: 1, 2, 3, 4, … The relative density of odd numbers and even numbers is the same (50% for both). But the number of odd numbers up to any given point is never less than, and half the time greater than, the number of even numbers up to that point. That is exactly what I am saying. It has nothing to do with relative density it has everything to do with the absolute difference with regards to the number of primes that can be written as 6n-1 and 6n+1. ---
**Author:** ![armstrongm](https://avatars.discourse-cdn.com/v4/letter/a/50afbb/32.png) [@armstrongm](https://boards.straightdope.com/u/armstrongm)\ **Post date:** [October 30, 2014, 3:15pm UTC](https://boards.straightdope.com/t/primes/702997/20 "2014-10-30T15:15:17Z")
“In general, if 0 \< a, b \< q are integers, (a, q) = (b, q) = 1, a is a quadratic residue, b is a quadratic nonresidue mod q, then π(x; q, b) \> π(x; q, a) occurs more often than not” if I understand it correctly that part of the equation has been proved through the Riemann Hypothesis and that in turn would make the statement that having more primes in the form 6n-1 than 6n+1 is to be expected then? [Next page](https://boards.straightdope.com/t/primes/702997.md?page=2)