mersenneforum.org Left over Sophie Germain primes?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-15, 12:13 #1 axn     Jun 2003 112658 Posts Left over Sophie Germain primes? 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!
2007-01-15, 12:30   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

141910 Posts

Quote:
 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.

Last fiddled with by R. Gerbicz on 2007-01-15 at 12:30

2007-01-15, 12:42   #3
axn

Jun 2003

4,789 Posts

Quote:
 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.

Last fiddled with by axn on 2007-01-15 at 12:44 Reason: spelling

2007-01-15, 12:57   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

3×11×43 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Trejack Twin Prime Search 10 2016-06-23 15:10 ProximaCentauri Miscellaneous Math 15 2014-12-25 14:26 firejuggler Software 4 2014-01-10 00:09 petrw1 PrimeNet 311 2010-04-06 05:18 MooooMoo Twin Prime Search 8 2008-11-05 15:03

All times are UTC. The time now is 08:17.

Thu Dec 3 08:17:55 UTC 2020 up 4:29, 0 users, load averages: 1.59, 1.19, 1.04