How can I most quickly find a big prime, p, for which 4p+1 is also prime? For example, p=37 works. I wonder if these special primes have been researched and some characteristics are known. Are there infinitely many of these primes?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ This brings to mind Sophie Germain primes, i.e. primes $p$ for which $2p+1$ is a prime, and whether there are infinitely many such primes is a notorious open question: en.wikipedia.org/wiki/Sophie_Germain_prime $\endgroup$– Alain ValetteApr 21, 2013 at 10:45
-
$\begingroup$ Just knowing that, it becomes easier to search the web. I found that this sequence is documented at oeis.org/A023212 and, from the graphs, guess that about 1 in 14 prime numbers might meet this requirement in the infinite limit. But, if primes were truly random, the prime number theorem makes me think that this ratio should go to zero. I'm leaning towards it going to zero. $\endgroup$– bobuhitoApr 21, 2013 at 13:07
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
There are very likely infinitely many primes of this form but this is open.
If one where to count the number of such primes up to $x$, one expects to find $$ \frac{C x}{( \log x)^2} $$ for some constant $C$ that one could compute, so on the one hand not too few but still only a set of relative density (in the primes) $0$, as expected by OP and compatible with the observation that early on there are not too few.
Where does this expectation come from: one can rephrase the problem as the problem of searching solutions in the primes of the linear equation $X = 4 Y +1$.
A linear equation (or a system thereof) is expected to have a infinitely many solutions in the primes if it has in the integers and there is no local restriction, that is there is no congruence relation that 'forbids' all variables to be prime, say $X=Y+3$ cannot have infinitely many solutions as it 'does not work' modulo $2$, and there is no problem due to positivity of the primes, say $X+Y = 1000$ cannot have infinitely many solutions in primes. And, there is also a prediction for the number of solutions.
This circle of ideas goes under the name Generalized Hardy--Littlewood conjectures.
For certain systems it is known that there are infinitely many solutions but for others not. Essentially, what is the case (under currently known results) is governed by the complexity of the system (in a precise technical sense see the reference below).
The equation you are looking at has infinite complexity (in this sense) and therefore it is not known (yet conjectured) that there are infinitely many solutions.
The introduction of 'Linear equations in primes' by Green and Tao gives a good overview; the paper itself makes important progress on these types of problems, note that the results in this paper are formulated conditionally on two conjectures but meawhile these are settled by the same two and Ziegler.
If you want to search for such primes a thing to note are congruence conditions to exclude unecessary test. For example, one can use that if $p$ and $4p +1$ are prime than $p$ can only be congruent $7$, $13$, $19$ modulo $30$, which follows by looking at the problem modulo $3$ and $5$ (and the info one has modulo $2$). One could add info for additional primes but perhaps this mod $30$ is a good balance.
-
$\begingroup$ An addition regarding finding large ones: if you really would only like so find one or some large pair it should in fact be slightly better so consider congruence classes for a larger modulus. For $30$ you have $3$ classes that will contain all such primes, for $210$ you would have $15$, for $2310 = 210.11$ you would have $135=15.9$ and so on, since for each 'new' prime $p$ you have $p-2$ admissible classes modulo $p$, all except $0$ and $-1/4$ mod $p$. To keep track of all this could be inconvenient for not that much gain. But if you do not want all but just some you could restrict... $\endgroup$– user9072Apr 21, 2013 at 14:14
-
$\begingroup$ ...to just one class or few classes modulo a product of more primes. In this or these classes the density of the pirmes (of your form) then will be somewhat higher. But after a certain point the increase in denity will be very slow. But to go somewhat beyond $2.3.5$ still seems reasonable if you want to do a large computation. $\endgroup$– user9072Apr 21, 2013 at 14:23
-
$\begingroup$ There is a minor imprecission in my answer, which I noticed in view of Victor Protsak's data, here is the coorecttion: $p=3$ while an exmple is outside the classes I mentioned, yet it is the only one, being the only prime congruent $0$ modulo $3$ (and the ther two exceptional primes 2 and 5 are not examples). $\endgroup$– user9072Apr 21, 2013 at 20:54
-
$\begingroup$ Easier to keep track of which classes not to bother with. Assuming that the primes $p$ are coming from a list as in Victors one line program above we could put in extra conditions before isprime of $i \mod 3 \ne 2, i \mod 5 \ne 1, i \mod 7 \ne 5, i\mod 11 \ne 3$ . $\endgroup$ Apr 22, 2013 at 1:48
-
$\begingroup$ @Aaron Meyerowitz: true, I was more working under the assumption that one has no a priori list. Another thing to keeo in mind is that after one already has the $p$ identified as prime, these checks are possibly not as useful anymore, since they exclude only precisely those where 4p+1 has small prime-factors and thus they'd be detected as a nonprime very quickly anyway. $\endgroup$– user9072Apr 22, 2013 at 9:17
$\begingroup$
$\endgroup$
Sage (http://www.sagemath.org) has an object type "generator". If you execute
quad=([p,4*p+1] for p in Primes() if is_prime(4*p+1))
quad.next() will generate consecutive pairs of primes of the form [$p$,$4p+1$]. Here how the list of the first 10 such pairs is generated:
for i in range(0,10):
quad.next()
[3, 13]
[7, 29]
[13, 53]
[37, 149]
[43, 173]
[67, 269]
[73, 293]
[79, 317]
[97, 389]
[127, 509]
answered Apr 21, 2013 at 20:39
$\begingroup$
$\endgroup$
You might take a modular prime number sieve, i.e. an ascending sequence of prime numbers {p1, p2,..., pn} with P being their product, and a grid S ⊂ {1,...,P-1}, where the numbers divisible by any prime of the sequence are taken out. Now, c = P∙k + s with s∈S, k∈ℕ0 is an optional prime number and c>pn is not a prime number, if there is no such composition. For 4c+1>pn being a prime is necessarily 4c+1 ≡ 4s+1 (mod P) ∈ S. So you can reduce the grid S to a grid S' = {s∈S | 4s+1∈S (mod P) } and S'+P∙ℕ0 contains all prime numbers p>pn with p'=4p+1 being prime.
