Left over Sophie Germain primes?

[axn]

Now that the twin prime has been found, can some one just run thru all the -1 primes found and test if k*2^(n+1)-1 is also prime? Eventhough it is a long shot, who knows, there just might be a Sophie Germain prime lurking there!

[R. Gerbicz]

Originally Posted by axn1

Now that the twin prime has been found, can some one just run thru all the -1 primes found and test if k*2^(n+1)-1 is also prime? Eventhough it is a long shot, who knows, there just might be a Sophie Germain prime lurking there!

That would be really inefficient, because for those k values we know only that k*2^n+-1 hasn't got a small factor (say <10^15 or something like that). For the larger one k*2^(n+1)-1 we haven't got information. It would be about 50 times faster to sieve on k*2^n-1,k*2^(n+1)-1 then do the primality tests.

Járai has used a combined sieve, I think for k*2^n+-1 and k*2^(n+1)-1, that's the reason why their k value's are so large (15 digits), and they've found record twin and Sophie Germain primes for n=171960.

[axn]

Originally Posted by R. Gerbicz

That would be really inefficient,

I am not suggesting that the present search continue to look for SG, but merely to take the currently found primes (IIRC, < 1000) and just see if they yield any SG primes. An opportunistic longshot rather than a determined effort.

[R. Gerbicz]

Originally Posted by axn1

I am not suggesting that the present search continue to look for SG, but merely to take the currently found primes (IIRC, < 1000) and just see if they yield any SG primes. An opportunistic longshot rather than a determined effort.

OK, I see what you want. That wouldn't be hard. But the chances are small for a success, say about 2%.

You can double your chance: if k*2^n-1 is prime then check k*2^(n+1)-1 but also check k*2^(n-1)-1.
And you can also sieve up to say 10^7 or something like that, because by large probability these numbers has got a small prime factor. Then do PRP test for the survivors.