Author |
Topic: 4n+1 vs 4n+3 primes (Read 5502 times) |
|
Mickey1
Junior Member
Gender: 
Posts: 116
|
 |
4n+1 vs 4n+3 primes
« on: Jan 27th, 2011, 6:51am » |
 Quote  Modify
|
Does anyone know the relation between the number of 4n+3 and 4n+1 primes?
Should we expect the ratio to converge to 0.5?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #1 on: Jan 27th, 2011, 8:56am » |
Quote Modify
|
It seems to be pretty much 50-50, looking at the first 4 million primes.
| #primes | | #(4n+1) | | #(4n+3) | | 8 | | 3 | | 5 | | 16 | | 7 | | 9 | | 32 | | 14 | | 18 | | 64 | | 29 | | 35 | | 128 | | 61 | | 67 | | 256 | | 122 | | 134 | | 512 | | 250 | | 262 | | 1024 | | 509 | | 515 | | 2048 | | 1009 | | 1039 | | 4096 | | 2036 | | 2060 | | 8192 | | 4084 | | 4108 | | 16384 | | 8183 | | 8201 | | 32768 | | 16358 | | 16410 | | 65536 | | 32715 | | 32821 | | 131072 | | 65504 | | 65568 | | 262144 | | 131007 | | 131137 | | 524288 | | 262036 | | 262252 | | 1048576 | | 524113 | | 524463 | | 2097152 | | 1048358 | | 1048794 | | 4000000 | | 1999605 | | 2000395 |
|
| « Last Edit: Jan 27th, 2011, 9:02am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #2 on: Jan 28th, 2011, 1:34am » |
Quote Modify
|
Thank you for that. I note you are very active on the forum, much to my benefit.
I take it there is no proof of this since you took the truble to calculate, but 50-50 seems to be a fair bet.
I am trying to calculate the number of 4n+1 primes by adding up different sum of squares. The number of combinations of different squares with sum < n is approximately pi*(square(n))^2/8 = pi*n/8.
I then have to subtract all doublets such as 65=81+4 = 16+49 and such pairs with a non-prime sum of squares such as 3, 4and 5. I believe that triplets such as 325 with 3 pairs of sums, and other errors due to higher orders, 4 pairs, would (perhaps) be marginal.
If I managed to do that I would then need the ratio of 4n+1 to 4n+3 primes to estimate the primes < n.
(I am also beginning to think about a generalization of what you found out, whether all such parallell series for instance 10*N+1, 10*N+3, 10N + 9 would have the same number of primes. I note from elsewhere on the forum that Dirichlet's theorem proove that there are an infinite such primes, but it doesn't seem to have any information about the prime's density).
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #3 on: Jan 28th, 2011, 4:17am » |
Quote Modify
|
on Jan 28th, 2011, 1:34am, Mickey1 wrote:| I take it there is no proof of this since you took the truble to calculate, but 50-50 seems to be a fair bet. |
|
According to this page, it is true, although the proof is not given there.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #4 on: Jan 28th, 2011, 9:00am » |
Quote Modify
|
on Jan 28th, 2011, 1:34am, Mickey1 wrote:| I take it there is no proof of this since you took the truble to calculate, but 50-50 seems to be a fair bet. |
|
It mostly means that proving it is harder for my than writing a program that checks the first several million primes 
I'm not very good with proofs of prime properties beyond proving there are an unlimited number of them.
Quote:| (I am also beginning to think about a generalization of what you found out, whether all such parallell series for instance 10*N+1, 10*N+3, 10N + 9 would have the same number of primes.) |
|
It seem to be true for 10N+{1,3,7,9}
I'll have a look at some more numbers over the weekend, to see if some stand out.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #5 on: Jan 28th, 2011, 11:13am » |
Quote Modify
|
After a bit of googling, a fascinating (and quite accessable) paper by Andrew Granville and Greg Martin pops up.
The basic result is called "the prime number theorem for arithmetic progressions”, first proven by a belgian mathematician, telling that there are an equal number of primes of the form 4k+1 as 4k+3.
But there is more. Someone proved that 99.59% of the time the primes of the form 4k+3 are more frequent.
As for writing an counting program, things get interesting modulo 8. 8k+1 only gets the lead at 608,981,813,029.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #6 on: Jan 31st, 2011, 6:54am » |
Quote Modify
|
Very interesting.
The article is informative but does not give a clue to the proof.
I note 4n+3 has a relatively short lead. I tried to give 4n+1 a lead to see when the situaiton changed, using towr's numbers as a random sample.
I tried to see how much more head start I should add to the 4n+1 in order to change the balance. I started with the 16th first primes so that the first 8 would be lower and the first 16 primes would higher with a head start of 1 and if I took a head start of 2 the 4n+1 would "win". For all the even number of towr's 20 rows I tried to see what head start would change so that the 2nth row would change from 50-50 to a majority for 4n+1.
#primes Head start for 4n+1 to win
16..........................2
64..........................3
256........................6
1024......................6
4096......................6
16384...................12
65536...................12
262144.................18
1048576...............24
4000000...............24
The needed head start is small and it seems to grow more or less with the logarithm of the #primes.
|
| « Last Edit: Jan 31st, 2011, 6:57am by Mickey1 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #7 on: Jan 31st, 2011, 8:49am » |
Quote Modify
|
on Jan 31st, 2011, 6:54am, Mickey1 wrote:| The article is informative but does not give a clue to the proof. |
|
If you follow the reference in the wikipedia article, it points to http://www.math.umass.edu/~isoprou/pdf/primes.pdf which seems to contain a proof.
Also via wikipedia, http://www.dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf discusses prime races, i.e. when for example 4n+1 is ahead and when 4n+3.
|
| « Last Edit: Feb 1st, 2011, 8:33am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #9 on: Feb 1st, 2011, 8:36am » |
Quote Modify
|
on Feb 1st, 2011, 4:05am, JohanC wrote:
I suppose here you meant to link to Granville&Martin? |
|
Yeah..
Seems to be just a later version of what you linked to, too; so doesn't add that much.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #10 on: Feb 8th, 2011, 8:15am » |
Quote Modify
|
I thank you all on this topic. It seems the proof involves Riemann's continuation of Euler's zeta function, i.e. a (for me) prohibitively difficult issue.
Let me just ask one addiitonal question. In towr's list above, the difference #4n+3- #4n+1 is always an even number. Is that self-evident to you?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 4n+1 vs 4n+3 primes
« Reply #11 on: Feb 8th, 2011, 9:37am » |
Quote Modify
|
Yes, if you have an even number of primes (or anything else) and divide it into two sets of n and m elements each, the difference between n and m must be even.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print