Author 
Message 
JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

Sophie Germain Prime Search
This is the next addition to PrimeGrid's ever expanding prime search projects. The Sophie Germain Prime search honors MarieSophie Germain, an extraordinary "French mathematician who made important contributions to the fields of differential geometry and number theory, and to the study of Fermat's Last Theorem." (Wiki)
A prime number p is called a Sophie Germain prime if 2p + 1 is also prime. For example, 5 is a Sophie Germain prime because it is prime and 2 × 5 + 1 = 11, is also prime.
We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors. The opportunity to find SG's and Twins in the same sieve file is appealing. However, we "expect" to find a Sophie Germain prime first.
This quad sieve was prepared quite some time ago; so it was readily available. Here are some stats for the search:
k range: 1<k<41T
n=666666 (actual 666666666685)
sieve depth: p=200T
candidates remaining: 34,190,344
Probability of one or more significant pair = 80.1%
Probability of one or more SG = 66.7%
Probability of one or more Twin = 42.3%
Approximate WU length:
Athlon64 2.1Ghz  ~2000 secs (~33.3 minutes)
C2D 2.1 Ghz  ~1015 secs (~16.9 minutes) per core
C2Q 2.4 GHz  ~880 secs (~14.7 minutes) per core
C2Q 3.2 GHz  ~600 secs (~10.0 minutes) per core
For more information about Sophie Germain primes, please visit these links:
http://primes.utm.edu/glossary/page.php?sort=SophieGermainPrime
http://mathworld.wolfram.com/SophieGermainPrime.html
http://en.wikipedia.org/wiki/Sophie_Germain_prime
For more infomation about MarieSophie Germain, please visit these links:
http://en.wikipedia.org/wiki/Sophie_Germain
http://www.pbs.org/wgbh/nova/proof/germain.html
____________




Excellent! I was wondering when this was going to happen. :D
Thanks guys
____________




What's so special about Sophie Germain primes? The 2p+1 definition seems kind of arbitrary. Why not 3p + 2? I can think of a few  5 and 17, 23 and 71, etc. Or 6p + 1? 7 and 43 match that too.
I know you included links, but the only thing interesting about them is that they were once mentioned in a movie. 



There seems to be no double checkers on these WUs. Why is this so?
____________




It seems fairly random. Some of min have dblchk, some don't
____________



pschoeferVolunteer developer Volunteer tester
Send message
Joined: 20 Sep 05 Posts: 677 ID: 845 Credit: 2,865,160,764 RAC: 517,112

We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1.
Will the additional tests be done manually, or in the same workunit, so that a WU with a prime is four times as long as a normal WU?
____________




SGP was also on PRPNet. It will be remove from PRPnet server? Should I update my init file to remove this search?
Thanks
____________
Badge Score: 1*2 + 1*5 + 9*6 + 5*7 + 3*8 + 1*9 = 134 



SGP was also on PRPNet. It will be remove from PRPnet server? Should I update my init file to remove this search?
Thanks
We need to dry the PRPNet server so keep it in list for now.
Please do some work and we can dry it sooner.
Lennart 



We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1.
Will the additional tests be done manually, or in the same workunit, so that a WU with a prime is four times as long as a normal WU?
You will check k*2^n1 and if prime you will also search k*2^n+1
We will search all primes externally on PG server for k*2^(n1)1, & k*2^(n+1)1
Lennart 


JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

There seems to be no double checkers on these WUs. Why is this so?
It seems fairly random. Some of min have dblchk, some don't
Adaptive Replication
This is a refinement of the replication policy. It randomly decides whether to replicate jobs, based on the measured error rate of hosts. If the first instance of a job is sent to a host with a low error rate, then with high probability no further instances will be sent.
Adaptive replication is independent of the comparison policy; you can use it with either bitwise comparison, fuzzy comparison, or homogeneous replication.
____________




What happens if a WU with no replication turns out to be prime? Will it then be sent for a double check?
____________



JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

What happens if a WU with no replication turns out to be prime? Will it then be sent for a double check?
Yes, all primes are double checked.
____________




An odd thing that I've noticed is that it seems to take significantly longer (~20% longer) to process these WUs then to process pps_llr WUs that test n values >666666. Why do these tasks take longer to process than the pps tasks that are testing larger numbers? Is the algorithm different? From the original post I assumed that the WUs would only be longer than normal if a prime was found and a test of the other three forms was necessary. Just curious...
Cheers!
Alan
____________




An odd thing that I've noticed is that it seems to take significantly longer (~20% longer) to process these WUs then to process pps_llr WUs that test n values >666666. Why do these tasks take longer to process than the pps tasks that are testing larger numbers? Is the algorithm different? From the original post I assumed that the WUs would only be longer than normal if a prime was found and a test of the other three forms was necessary. Just curious...
Cheers!
Alan
Becuse the bigger k value. Here is some tests done on n=450k
Lennart
3*2^4500001 is not prime. LLR Res64: 41DC49206C003650 Time : 191.636 sec.
95*2^4500001 is not prime. LLR Res64: B68A9B531D48CE4C Time : 237.690 sec.
207*2^4500001 is not prime. LLR Res64: AFA085A93236BE97 Time : 237.702 sec.
509*2^4500001 is not prime. LLR Res64: 2EF3E515DE834DC4 Time : 237.519 sec.
1049*2^4500001 is not prime. LLR Res64: 84A3F5A1A834BDCC Time : 246.983 sec.
2019*2^4500001 is not prime. LLR Res64: BB3B39FDAFE07AC4 Time : 247.371 sec.
5043*2^4500001 is not prime. LLR Res64: 0289F1AE44813108 Time : 246.789 sec.
10007*2^4500001 is not prime. LLR Res64: B8854C4D30576ABA Time : 246.766 sec.
20015*2^4500001 is not prime. LLR Res64: D2BCF73F969CD087 Time : 324.821 sec.
50003*2^4500001 is not prime. LLR Res64: F019BEEFDD7C3B7D Time : 324.970 sec.
100095*2^4500001 is not prime. LLR Res64: F197B35F9F5626A9 Time : 324.837 sec.
200007*2^4500001 is not prime. LLR Res64: 6CD221DB2CF8348E Time : 324.883 sec.
500015*2^4500001 is not prime. LLR Res64: 5BB10EA4AB0C28CA Time : 432.913 sec.
1000023*2^4500001 is not prime. LLR Res64: EDB3E49680CB449D Time : 432.925 sec.
2000049*2^4500001 is not prime. LLR Res64: 954B92D0B4AEB21C Time : 432.858 sec.
5000019*2^4500001 is not prime. LLR Res64: 26F59AB7C18268C7 Time : 432.948 sec.
10000133*2^4500001 is not prime. LLR Res64: 9D18BDFB989F45A6 Time : 432.861 sec.
20000187*2^4500001 is not prime. LLR Res64: 76E252A6FD6C5468 Time : 433.279 sec.
50000043*2^4500001 is not prime. LLR Res64: 9C985D5E47C95E98 Time : 433.091 sec.
100000115*2^4500001 is not prime. LLR Res64: EF7DC18C6E7A2327 Time : 433.043 sec.
200000007*2^4500001 is not prime. LLR Res64: FF761C6F58717618 Time : 433.037 sec.
500000079*2^4500001 is not prime. LLR Res64: F9C08E06DC2A8673 Time : 433.091 sec.
1000000029*2^4500001 is not prime. LLR Res64: 7B38B46F5DB67F3C Time : 433.080 sec.
2000000033*2^4500001 is not prime. LLR Res64: 74C2495548F72BAF Time : 433.048 sec.
5000000003*2^4500001 is not prime. LLR Res64: C91CF9303119CAD7 Time : 433.055 sec.
10000000035*2^4500001 is not prime. LLR Res64: 13B4B699DACA308D Time : 433.195 sec.
20000000015*2^4500001 is not prime. LLR Res64: 899F0B4FA6EC82F2 Time : 433.144 sec.
50000000043*2^4500001 is not prime. LLR Res64: 978694633A8690C9 Time : 433.132 sec.
100000000037*2^4500001 is not prime. LLR Res64: 03C9FB78A347AAD2 Time : 433.056 sec.
200000000007*2^4500001 is not prime. LLR Res64: 0B9ADAC5C06FEA0C Time : 432.996 sec.
500000000027*2^4500001 is not prime. LLR Res64: 379E82A9C791FDD6 Time : 433.079 sec.
1000000000019*2^4500001 is not prime. LLR Res64: 56B8861600FCA256 Time : 433.164 sec.
2000000000019*2^4500001 is not prime. LLR Res64: C0CD98A1E30CC8CA Time : 432.979 sec.
5000000000049*2^4500001 is not prime. LLR Res64: 87B31BF96B27584D Time : 432.948 sec.
10000000000025*2^4500001 is not prime. LLR Res64: F64ABB39E393274E Time : 433.044 sec.
20000000000019*2^4500001 is not prime. LLR Res64: 9C6FDC753594EEF8 Time : 432.945 sec.
50000000000027*2^4500001 is not prime. LLR Res64: A16D2400005B0C90 Time : 432.945 sec.
100000000000025*2^4500001 is not prime. LLR Res64: 6805EF4EB4BDBE07 Time : 433.010 sec.
200000000000063*2^4500001 is not prime. LLR Res64: DACEA6688FC6DB99 Time : 432.972 sec.
500000000000085*2^4500001 is not prime. LLR Res64: 23B5078C0925A196 Time : 432.970 sec.
1000000000000005*2^4500001 is not prime. LLR Res64: D8229F3D187C8E6B Time : 1178.190 sec.




Thanks Lennart...Wow, it is interesting that the size of k matters more than the size of the actual number being tested.
For instance, 1177*2^669246+1 took 498s to crunch
http://www.primegrid.com/workunit.php?wuid=82112380
while 16715444655*2^6666701 took 682s to crunch on the same box.
http://www.primegrid.com/workunit.php?wuid=82113124
There are far more digits in 1177*2^669246+1 than in 16715444655*2^6666701. It's a bit counterintuitive to me that the bigger number is faster to crunch, but I guess the llr program must take advantage of some shortcut with smaller k values?
____________




Iam missing a server status for SGPS?!
____________




Are there plans to have a server status section for the Sophie Germain prime search?
Just wondering
____________



RytisVolunteer moderator Project administrator
Send message
Joined: 22 Jun 05 Posts: 2653 ID: 1 Credit: 89,719,258 RAC: 51,571

Are there plans to have a server status section for the Sophie Germain prime search?
Just wondering
Actually, the stats are already there. I added them a few minutes before you wrote the message :)
____________




Rytis,
I see the stats on http://www.primegrid.com/stats_sgs_llr.php
Question on the totals.
In the statspage totals are missing for the "total tasks" and "done tasks" Doing a quick count I got to 218687 total tasks, of which 25% appears to be done. According to the stats we will be done within a few weeks.
In the initial post it is stated "candidates remaining: 34,190,344". If that is true this will run for a few months.
Which interpretation is correct?
Alexander 



Rytis,
I see the stats on http://www.primegrid.com/stats_sgs_llr.php
Question on the totals.
In the statspage totals are missing for the "total tasks" and "done tasks" Doing a quick count I got to 218687 total tasks, of which 25% appears to be done. According to the stats we will be done within a few weeks.
In the initial post it is stated "candidates remaining: 34,190,344". If that is true this will run for a few months.
Which interpretation is correct?
Alexander
Candidates remaining is ~34M.
We will not insert all 34M at once.
I'll insert work for about 1 Month every time.
Lennart




Rytis: The deadline with 4 days is very short, can you extend it to 7 days?
____________




@Alan: Actually the factor k is also a multiplicative time factor to compute the result with the LLR algorithm. The complexity is about k * complexity of primetesting of (2^n1). 



cool:) Thanks Bruno!
____________




is this search done once we've crunched the remaining units? or will it be extended to other n values? 



I am unclear on this. John posted message 22519 in the AP26 Found!!! board, saying that the Sophie Germain Prime Search has a definite end goal.
What exactly is this goal, and when are we expecting to achieve it?
____________
May the Force be with you always.




It is when the sophie germain prime has been found. So finding a prime k*2^n1 where k*2^(n+1)1 is prime also. 



I believe that I understand now. Thank you.
____________
May the Force be with you always.




So when a prime is found in SGS, is it automatically tested to see if it fits into the full SGS? I see posts in here that people post their prime then someone tests it.
I found one
7555140078885*2^6666661
____________
My lucky numbers are 121*2^45538991 and 3756801695685*2^666669±1
My movie https://vimeo.com/manage/videos/502242 


JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

So when a prime is found in SGS, is it automatically tested to see if it fits into the full SGS? I see posts in here that people post their prime then someone tests it.
I found one
7555140078885*2^6666661
It is automatically tested.
In the SGS search, when the client finds a prime, it then checks to see if it's a twin. Once those results are returned to the server, the prime is further checked another 2 times to see if it's a Sophie Germain.
The four tests conducted are as follows:
k*2^n1 clientside
if prime, then the following
k*2^n+1 clientside
k*2^(n1)1 serverside
k*2^(n+1)1 serverside
Using your prime above, the client tested:
7555140078885*2^6666661
7555140078885*2^666666+1
and the server tested
7555140078885*2^6666651
7555140078885*2^6666671
____________




So how do we know if it's a twin? 


JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

So how do we know if it's a twin?
Bells and whistles will go off! :D just joking
For it to be a twin, k*2^n1 and k*2^n+1 must both be prime. If they are, you'll be notified in an email. :)
____________




Iam missing the digits view in subproject status...
____________




Sophie Germain Prime Search
...
We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1.
I was happy at the report of having a prime k*2^n1 with just
over 200K digits (earlier today). Now that I have one, I see that
I didn't do a very good job of reading the info here. So from
Here are some stats for the search:
...
candidates remaining: 34,190,344
Probability of one or more significant pair = 80.1%
Probability of one or more SG = 66.7%
Probability of one or more Twin = 42.3%
we perhaps ought to observe that hardly any (at most 2 or 3,
in expectation?) of these primes k*2^n1 will be either a SG prime
or a Twin prime. Checking the prime pages, the current record
for a SG prime has just under 80K digits, while the record Twin
has just over 100K digits. So we're not just looking for anyold
random SG/Twin, but for a fairly huge jump of the record size.
And lastly, while the odds of a SG are somewhat larger than for
a Twin, both are sufficiently unlikely that seeing a Twin before a
SG wouldn't be too surprising.
Still, a Proth prime and a SG/Twin candidate prime in the same
day is my current best Primegrid result; quite a welcome start to
the morning!
Regards, Bruce* 



If someone with Intel I7 2600K could test a few units with and without HT? 


ardo Send message
Joined: 12 Dec 10 Posts: 168 ID: 76659 Credit: 1,693,455,577 RAC: 0

I'm running this on a Intel i7 2600k with HT. :)
What info are you looking for? 



What clock, stock or OC? 


ardo Send message
Joined: 12 Dec 10 Posts: 168 ID: 76659 Credit: 1,693,455,577 RAC: 0

stock with temps around 60C
I have not attempted to oc yet; might do that this weekend. 



Ok, thanks for that information. Interesing, what time would be on 4.0/4.5 GHz. 



Hi
Sorry for my poor english. I m french I a prefered lear women than other language ...
I'm not mathemetician but inbformatician*
My goal is to done max computer power to the scientist not to do heir jobs
I 'm not able to create a sieve but give me the idea and I make the max powerful application(I try...)
Interested by twin( I have a twin brother)
I download TPS code and I don't belive it:
35 pages of code,1 or 2 G of RAM, X G of HD space and year of cpu
To do a Sophie Germain search you need 10 liines of code, no ram,no hd,
You(mathematicians) find that a Sophie number is can be write 6k1
So we only have to compute all caandidas verify if is_Prime
add 2 and verify the primarity of the new walue
You don't realaese the importanec ,for computer,of this
We can write a stieve 10 times more speed hat Erasthotèène!!!!!
the naif code ot search twin smaller then 1 000 000 is:
B:=1000000;
A:=5; // we begin with 11 a:= (6 *1) 1
repeat
A:= A+6;
If Is_Prime (A) then
if Is prime(A+2) then
begin
Inc(Offset)
twins[offset]:=A;
end;
until A>B;
With this sieve no first attemp to eliminate candidat,
no RAM, no Hd direcly the number of candidats. B div 6 =166667 primeity tst
You can make the resarch on a Phone(Idea to BOINC)
AND DON'T FORGET
it' the naif code : it's easy to do speeder
What is the WR for Twin? 120 000 Digits?
Jerôme 



Hi
I a prefered lear women than other language ...
Same here.




Hi,
Your code could be written in full to give a useful routine for finding either primes or twin primes for the lower numbers (up to say 10^8) with reasonable speed, higher if you are patient, but the catch is the "Is_prime" subroutine.
It would be something like :
Is_prime (a)
Var
file : primes.CSV {2,3,5}
file twins.CSV {2:3,3:5}
Begin
c :=a1
d:=a+1
Is_primec :=1
Is_primed :=1
open primes
while not EOF repeat
read test
sqr := sqrt(a+1)
while test < sqr do
begin
if mod(c,test) = 0 then Is_primec :=0
if mod(d,test) = 0 then Is_primed
end
if Is_primec and Is_primed <> 0 then next test
else end
If Is_primec = 1 then append primes(","c)
if Is_primed = 1 then append primes(","d)
if Is_primec and Is_primed = 1 then append twin (","c":"d)
end
This tests both a1 and a+1 for primality and twin primality and saves the result to the file if either is prime, the same prime file being reused in the testing. The files are .CSV files.
The program is not of course complete, but it does show the idea.
The problem is that as we get to very big numbers (10^100000) the files would be MASSIVE, many million tersbytes in length, and the tests would take hundreds of years to complete even on the fastest PC.
The idea could however be useful as a student code example. About 20 years ago when I did my BComp degree we were given an assignment in optimisation using Turbo Pascal, 10 or 20% of the marks were based on the 10 percentile placing in the class when the code was run to 1,ooo,ooo on the lecturers PC. The slowest tested every number (including even ones), others tested every odd number, the faster tested at 6n+_1. Testing for divisibility by all numbers, just odd numbers and only primes gives added speed variation. Many other optimisations are possible but they will never solve the problems for extreme times with the size of numbers PG uses.
It could be written in any language but Java would be good and allow easy graphic displays of the population densities of the resuts for example.
____________
Member team AUSTRALIA
My lucky number is 9291*2^1085585+1 


HonzaVolunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1943 ID: 352 Credit: 5,939,210,715 RAC: 1,574,944

Among Newly reported primes there are some 333333. How comes?
65516468355*2^333333+1
65516468355*2^3333331
This is also listed under Other significant primes.
____________
My stats 



Among Newly reported primes there are some 333333. How comes?
65516468355*2^333333+1
65516468355*2^3333331
This is also listed under Other significant primes.
They seem to be reported within "Twin Prime Search" subproject. Old primes with a new twin counterpart found? Or is it the server having "flashbacks"? 


JohnHonorary cruncher
Send message
Joined: 21 Feb 06 Posts: 2875 ID: 2449 Credit: 2,681,934 RAC: 0

Among Newly reported primes there are some 333333. How comes?
65516468355*2^333333+1
65516468355*2^3333331
This is also listed under Other significant primes.
They seem to be reported within "Twin Prime Search" subproject. Old primes with a new twin counterpart found? Or is it the server having "flashbacks"?
In reviewing the most recent twin, it was discovered that the +1 form didn't show up in the user's prime list. It was the same for the first n=333333 prime. Therefore, I had to go back and update the DB entry
manually.
____________




As you are searching for Sophie Germain Prime, I wonder if you could give me some Sophie Germain Prime between 2^4096 ~ 2^32768. All I can found on the internet either too large or too small for me. I've got two in the site primes.utm.edu. 18458709× 2^32611 1 and 470943129×2^16352 1 is what I have at hand. I need another two at least. The more, the better. I would be very appreciate is you could give me some. Thank you! 



As you are searching for Sophie Germain Prime, I wonder if you could give me some Sophie Germain Prime between 2^4096 ~ 2^32768. All I can found on the internet either too large or too small for me. I've got two in the site primes.utm.edu. 18458709× 2^32611 1 and 470943129×2^16352 1 is what I have at hand. I need another two at least. The more, the better. I would be very appreciate is you could give me some. Thank you!
PrimeGrid is not your (nor anyones) personal prime generating project. Since the numbers are really small you should easily be able to find them yourself. Or else you could always start your own distributed computing effort to find them.
____________
PrimeGrid Challenge Overall standings  Last update: From Pi to Paddy (2016)




As you are searching for Sophie Germain Prime, I wonder if you could give me some Sophie Germain Prime between 2^4096 ~ 2^32768. All I can found on the internet either too large or too small for me. I've got two in the site primes.utm.edu. 18458709× 2^32611 1 and 470943129×2^16352 1 is what I have at hand. I need another two at least. The more, the better. I would be very appreciate is you could give me some. Thank you!
PrimeGrid is not your (nor anyones) personal prime generating project. Since the numbers are really small you should easily be able to find them yourself. Or else you could always start your own distributed computing effort to find them.
I respect your hard work. Finding them is beyond my ability. I'm not treated it as a personal project. I thought it's public. That's why I'm here. what's purpose the sophie germain prime your are searching for? No offense, If you treat it as a breaking record game. I must say you're underestimate your work. 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

As you are searching for Sophie Germain Prime, I wonder if you could give me some Sophie Germain Prime between 2^4096 ~ 2^32768. All I can found on the internet either too large or too small for me. I've got two in the site primes.utm.edu. 18458709× 2^32611 1 and 470943129×2^16352 1 is what I have at hand. I need another two at least. The more, the better. I would be very appreciate is you could give me some. Thank you!
Go to http://primes.utm.edu/primes/search.php
Put Sophie Germain (p) in the "Text Comment" textbox
Select "All verified primes" radio button.
Enter 500 in "Maximum number of primes to output "
Select output style as "Text (printable)"
62102 18131*22817#1 9853 L 2000 Sophie Germain (p)
62119 18458709*2^326111 9825 CK 1999 Sophie Germain (p)
62470 847067781*2^307901 9278 L4 2003 Sophie Germain (p)
62708 415365*2^300521 9053 g141 1999 Sophie Germain (p)
62920 60940331*2^29439+1 8870 g136 2002 Sophie Germain (p)
63182 23345*2^28601+1 8615 g171 2003 Sophie Germain (p)
63688 18482685*2^271821 8190 g206 2001 Sophie Germain (p)
63979 22717075*2^26000+1 7835 x11 2001 Sophie Germain (p)
64316 161193945*2^252531 7611 g137 2001 Sophie Germain (p)
64461 121063995*2^250941 7563 g120 2001 Sophie Germain (p)
64462 120136023*2^250941 7563 g120 2001 Sophie Germain (p)
64540 1051054917*2^250001 7535 g52 2000 Sophie Germain (p)
64651 626711007*2^247121 7448 g144 2001 Sophie Germain (p)
64652 885817959*2^247111 7448 g217 2001 Sophie Germain (p)
64664 1392082887*2^246801 7439 g137 2000 Sophie Germain (p)
64940 14516877*2^241761 7285 CK 1999 Sophie Germain (p)
65097 471631965*2^240001 7234 g298 2002 Sophie Germain (p)
65300 72021*2^236301 7119 g0 1998 Sophie Germain (p)
65352 325034895*2^234721 7075 g205 2000 Sophie Germain (p)
65353 1297743285*2^234701 7075 g205 2001 Sophie Germain (p)
65372 1186447755*2^234571 7071 g144 2000 Sophie Germain (p)
65386 613702635*2^234571 7071 g144 2000 Sophie Germain (p)
65954 1354921707*2^230051 6935 g141 2001 Sophie Germain (p)
65961 224420829*2^230031 6933 g141 2000 Sophie Germain (p)
65962 1579278645*2^230001 6933 g141 2000 Sophie Germain (p)
65963 255346125*2^230021 6933 g141 2000 Sophie Germain (p)
66932 1654523577*2^203041 6122 g137 2000 Sophie Germain (p)
67297 29553033*2^199901 6026 g141 1999 Sophie Germain (p)
67337 184748277*2^199121 6003 g206 2000 Sophie Germain (p)
67393 31467345*2^197611 5957 g141 1999 Sophie Germain (p)
67556 2375063906985*2^193801 5847 IJ 1996 Sophie Germain (p)
67687 276311*2^19003+1 5726 g23 1998 Sophie Germain (p)
68901 3382599*2^170751 5147 g27 1999 Sophie Germain (p)
68910 757321845*2^170511 5142 g141 2000 Sophie Germain (p)
68911 454332273*2^170511 5142 g141 2000 Sophie Germain (p)
68913 338234883*2^170501 5142 g141 2000 Sophie Germain (p)
68924 421907295*2^170291 5135 g141 2000 Sophie Germain (p)
69006 48859797*2^170001 5126 g141 1999 Sophie Germain (p)
69029 92305*2^16998+1 5122 g14 1998 Sophie Germain (p)
69177 8069496435*10^50721 5082 D 1995 Sophie Germain (p)
69956 "2^163832^163191+2^63*(floor(2^16254*Pi)+50814484)"
4932 c9 2003 ECPP, Sophie Germain (p) (**)
70052 470943129*2^163521 4932 IJ 1995 Sophie Germain (p)
70144 157324389*2^163521 4931 IJ 1995 Sophie Germain (p)
70596 12359*2^15405+1 4642 g122 2000 Sophie Germain (p)
70726 11263*2^15318+1 4616 g122 2000 Sophie Germain (p)
70899 5415312903*10^45261 4536 D 1994 Sophie Germain (p)
70974 48101037*2^150051 4525 g141 2000 Sophie Germain (p)
70975 28671705*2^150051 4525 g141 2000 Sophie Germain (p)
70983 44941785*2^149991 4523 g141 2000 Sophie Germain (p)
71633 10211*2^13491+1 4066 g122 2000 Sophie Germain (p)
71818 1468358892*10^40031 4013 D 1994 Sophie Germain (p)
71930 1883535*2^131331 3960 g141 1999 Sophie Germain (p)
72021 224529135*2^126481 3816 g2 1998 Sophie Germain (p)
72204 "2^122872^122231+2^63*(floor(2^12158*Pi)+7425765)"
3699 c9 2003 ECPP, Sophie Germain (p) (**)
72206 5293*2^12270+1 3698 g122 2000 Sophie Germain (p)
72358 15614233635*10^35291 3540 D 1994 Sophie Germain (p)
73717 27692175*2^104091 3141 g141 1999 Sophie Germain (p)
73799 22155*2^101641 3065 g35 1998 Sophie Germain (p)
73818 5546061*2^101131 3052 g155 1999 Sophie Germain (p)
74523 47013511545*10^29991 3010 D 1993 Sophie Germain (p)
74635 4627755*2^98781 2981 g2 1998 Sophie Germain (p)
74676 196949037*2^97521 2944 g141 1999 Sophie Germain (p)
75031 15489885*2^89061 2689 g27 1999 Sophie Germain (p)
75362 1746052308*10^25811 2591 D 1993 Sophie Germain (p)
76938 22714209*2^80871 2442 g14 1998 Sophie Germain (p)
77053 9303607*2^8004+1 2417 g2 1998 Sophie Germain (p)
77069 10497687*2^80001 2416 g210 2001 Sophie Germain (p)
77900 4837*2^7574+1 2284 DM 1996 Sophie Germain (p)
78229 2667027*2^73891 2231 CK 1999 Sophie Germain (p)
78877 8980569*2^71791 2169 g14 1998 Sophie Germain (p)
78910 14096107*2^7168+1 2165 CR 1997 Sophie Germain (p)
78911 12271975*2^7168+1 2165 CR 1997 Sophie Germain (p)
78912 12259585*2^7168+1 2165 CR 1997 Sophie Germain (p)
79224 6341*2^7039+1 2123 g34 1998 Sophie Germain (p)
79282 21063042*10^21101 2118 D 1993 Sophie Germain (p)
79363 20114275*2^7000+1 2115 CR 1997 Sophie Germain (p)
80195 2926924*10^2032+1 2039 D 1992 Sophie Germain (p)
82573 736320585*2^61941 1874 g95 1998 Sophie Germain (p)
82608 713851138*10^1854+1 1863 D 1990 Sophie Germain (p)
82771 337047945*2^59991 1815 g210 2001 Sophie Germain (p)
82796 39051*2^60011 1812 K 1986 Sophie Germain (p)
84026 89687295*2^50011 1514 g38 1998 Sophie Germain (p)
84031 6238665*2^50041 1514 g14 1998 Sophie Germain (p)
84032 67621539*2^50001 1513 g158 1999 Sophie Germain (p)
84033 61022115*2^50001 1513 g158 1999 Sophie Germain (p)
84034 110266875*2^49991 1513 g158 1999 Sophie Germain (p)
84037 9769767*2^50011 1513 g158 1999 Sophie Germain (p)
84041 5004615*2^50011 1513 g158 1999 Sophie Germain (p)
84043 4133481*2^50011 1513 K 1988 Sophie Germain (p)
87360 81127*2^4350+1 1315 g14 1998 Sophie Germain (p)
87388 531667*2^4346+1 1315 g14 1997 Sophie Germain (p)
87838 6206682*10^13001 1307 CR 1997 Sophie Germain (p)
88877 296385*2^42511 1286 Z 1989 Sophie Germain (p)
89731 53373*2^42031 1270 Z 1989 Sophie Germain (p)




As you are searching for Sophie Germain Prime, I wonder if you could give me some Sophie Germain Prime between 2^4096 ~ 2^32768. All I can found on the internet either too large or too small for me. I've got two in the site primes.utm.edu. 18458709× 2^32611 1 and 470943129×2^16352 1 is what I have at hand. I need another two at least. The more, the better. I would be very appreciate is you could give me some. Thank you!
Go to http://primes.utm.edu/primes/search.php
Put Sophie Germain (p) in the "Text Comment" textbox
Select "All verified primes" radio button.
Enter 500 in "Maximum number of primes to output "
Select output style as "Text (printable)"
62102 18131*22817#1 9853 L 2000 Sophie Germain (p)
62119 18458709*2^326111 9825 CK 1999 Sophie Germain (p)
62470 847067781*2^307901 9278 L4 2003 Sophie Germain (p)
62708 415365*2^300521 9053 g141 1999 Sophie Germain (p)
62920 60940331*2^29439+1 8870 g136 2002 Sophie Germain (p)
63182 23345*2^28601+1 8615 g171 2003 Sophie Germain (p)
63688 18482685*2^271821 8190 g206 2001 Sophie Germain (p)
63979 22717075*2^26000+1 7835 x11 2001 Sophie Germain (p)
64316 161193945*2^252531 7611 g137 2001 Sophie Germain (p)
64461 121063995*2^250941 7563 g120 2001 Sophie Germain (p)
64462 120136023*2^250941 7563 g120 2001 Sophie Germain (p)
64540 1051054917*2^250001 7535 g52 2000 Sophie Germain (p)
64651 626711007*2^247121 7448 g144 2001 Sophie Germain (p)
64652 885817959*2^247111 7448 g217 2001 Sophie Germain (p)
64664 1392082887*2^246801 7439 g137 2000 Sophie Germain (p)
64940 14516877*2^241761 7285 CK 1999 Sophie Germain (p)
65097 471631965*2^240001 7234 g298 2002 Sophie Germain (p)
65300 72021*2^236301 7119 g0 1998 Sophie Germain (p)
65352 325034895*2^234721 7075 g205 2000 Sophie Germain (p)
65353 1297743285*2^234701 7075 g205 2001 Sophie Germain (p)
65372 1186447755*2^234571 7071 g144 2000 Sophie Germain (p)
65386 613702635*2^234571 7071 g144 2000 Sophie Germain (p)
65954 1354921707*2^230051 6935 g141 2001 Sophie Germain (p)
65961 224420829*2^230031 6933 g141 2000 Sophie Germain (p)
65962 1579278645*2^230001 6933 g141 2000 Sophie Germain (p)
65963 255346125*2^230021 6933 g141 2000 Sophie Germain (p)
66932 1654523577*2^203041 6122 g137 2000 Sophie Germain (p)
67297 29553033*2^199901 6026 g141 1999 Sophie Germain (p)
67337 184748277*2^199121 6003 g206 2000 Sophie Germain (p)
67393 31467345*2^197611 5957 g141 1999 Sophie Germain (p)
67556 2375063906985*2^193801 5847 IJ 1996 Sophie Germain (p)
67687 276311*2^19003+1 5726 g23 1998 Sophie Germain (p)
68901 3382599*2^170751 5147 g27 1999 Sophie Germain (p)
68910 757321845*2^170511 5142 g141 2000 Sophie Germain (p)
68911 454332273*2^170511 5142 g141 2000 Sophie Germain (p)
68913 338234883*2^170501 5142 g141 2000 Sophie Germain (p)
68924 421907295*2^170291 5135 g141 2000 Sophie Germain (p)
69006 48859797*2^170001 5126 g141 1999 Sophie Germain (p)
69029 92305*2^16998+1 5122 g14 1998 Sophie Germain (p)
69177 8069496435*10^50721 5082 D 1995 Sophie Germain (p)
69956 "2^163832^163191+2^63*(floor(2^16254*Pi)+50814484)"
4932 c9 2003 ECPP, Sophie Germain (p) (**)
70052 470943129*2^163521 4932 IJ 1995 Sophie Germain (p)
70144 157324389*2^163521 4931 IJ 1995 Sophie Germain (p)
70596 12359*2^15405+1 4642 g122 2000 Sophie Germain (p)
70726 11263*2^15318+1 4616 g122 2000 Sophie Germain (p)
70899 5415312903*10^45261 4536 D 1994 Sophie Germain (p)
70974 48101037*2^150051 4525 g141 2000 Sophie Germain (p)
70975 28671705*2^150051 4525 g141 2000 Sophie Germain (p)
70983 44941785*2^149991 4523 g141 2000 Sophie Germain (p)
71633 10211*2^13491+1 4066 g122 2000 Sophie Germain (p)
71818 1468358892*10^40031 4013 D 1994 Sophie Germain (p)
71930 1883535*2^131331 3960 g141 1999 Sophie Germain (p)
72021 224529135*2^126481 3816 g2 1998 Sophie Germain (p)
72204 "2^122872^122231+2^63*(floor(2^12158*Pi)+7425765)"
3699 c9 2003 ECPP, Sophie Germain (p) (**)
72206 5293*2^12270+1 3698 g122 2000 Sophie Germain (p)
72358 15614233635*10^35291 3540 D 1994 Sophie Germain (p)
73717 27692175*2^104091 3141 g141 1999 Sophie Germain (p)
73799 22155*2^101641 3065 g35 1998 Sophie Germain (p)
73818 5546061*2^101131 3052 g155 1999 Sophie Germain (p)
74523 47013511545*10^29991 3010 D 1993 Sophie Germain (p)
74635 4627755*2^98781 2981 g2 1998 Sophie Germain (p)
74676 196949037*2^97521 2944 g141 1999 Sophie Germain (p)
75031 15489885*2^89061 2689 g27 1999 Sophie Germain (p)
75362 1746052308*10^25811 2591 D 1993 Sophie Germain (p)
76938 22714209*2^80871 2442 g14 1998 Sophie Germain (p)
77053 9303607*2^8004+1 2417 g2 1998 Sophie Germain (p)
77069 10497687*2^80001 2416 g210 2001 Sophie Germain (p)
77900 4837*2^7574+1 2284 DM 1996 Sophie Germain (p)
78229 2667027*2^73891 2231 CK 1999 Sophie Germain (p)
78877 8980569*2^71791 2169 g14 1998 Sophie Germain (p)
78910 14096107*2^7168+1 2165 CR 1997 Sophie Germain (p)
78911 12271975*2^7168+1 2165 CR 1997 Sophie Germain (p)
78912 12259585*2^7168+1 2165 CR 1997 Sophie Germain (p)
79224 6341*2^7039+1 2123 g34 1998 Sophie Germain (p)
79282 21063042*10^21101 2118 D 1993 Sophie Germain (p)
79363 20114275*2^7000+1 2115 CR 1997 Sophie Germain (p)
80195 2926924*10^2032+1 2039 D 1992 Sophie Germain (p)
82573 736320585*2^61941 1874 g95 1998 Sophie Germain (p)
82608 713851138*10^1854+1 1863 D 1990 Sophie Germain (p)
82771 337047945*2^59991 1815 g210 2001 Sophie Germain (p)
82796 39051*2^60011 1812 K 1986 Sophie Germain (p)
84026 89687295*2^50011 1514 g38 1998 Sophie Germain (p)
84031 6238665*2^50041 1514 g14 1998 Sophie Germain (p)
84032 67621539*2^50001 1513 g158 1999 Sophie Germain (p)
84033 61022115*2^50001 1513 g158 1999 Sophie Germain (p)
84034 110266875*2^49991 1513 g158 1999 Sophie Germain (p)
84037 9769767*2^50011 1513 g158 1999 Sophie Germain (p)
84041 5004615*2^50011 1513 g158 1999 Sophie Germain (p)
84043 4133481*2^50011 1513 K 1988 Sophie Germain (p)
87360 81127*2^4350+1 1315 g14 1998 Sophie Germain (p)
87388 531667*2^4346+1 1315 g14 1997 Sophie Germain (p)
87838 6206682*10^13001 1307 CR 1997 Sophie Germain (p)
88877 296385*2^42511 1286 Z 1989 Sophie Germain (p)
89731 53373*2^42031 1270 Z 1989 Sophie Germain (p)
Wow. Excellent. More than I expected. Thank you. 



We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1.
Will the additional tests be done manually, or in the same workunit, so that a WU with a prime is four times as long as a normal WU?
You will check k*2^n1 and if prime you will also search k*2^n+1
We will search all primes externally on PG server for k*2^(n1)1, & k*2^(n+1)1
A prime number p is called a Sophie Germain prime if 2p + 1 is also prime.
Is there a name for prime numbers p if 2p  1 is also prime?
The first few primes are:
3, 7, 19, 31, 37, 79, 97, 139, 157, 199... (sequence A005382 in OEIS).
What is the largest known prime of this form?
Do we check k*2^n+1 primality even if k*2^n1 is composite?
Do we check k*2^(n+1)+1 primality if k*2^n+1 is prime?
____________




I've already found that the largest known primes of this form is
648309*2^148311+1  Cunningham chain 2nd kind (2p1)
648309*2^148310+1  Cunningham chain 2nd kind (p)
44652 and 43058 digits only...
____________



JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 918 ID: 107307 Credit: 977,945,376 RAC: 0

John wrote: You will check k*2^n1 and if prime you will also search k*2^n+1
We will search all primes externally on PG server for k*2^(n1)1, & k*2^(n+1)1
x3mEn wrote: Do we check k*2^n+1 primality even if k*2^n1 is composite?
Do we check k*2^(n+1)+1 primality if k*2^n+1 is prime?
Simple answer: No, Yes.
The arguments we supply to the BOINC client for testing SGS say to test the k*2^n1 form first and to only test the k*2^n+1 if that first test comes out prime. That's why double credit is awarded for a prime  two tests were performed.
For every SGS prime, no matter whether the +1 form is prime or not we test both the k*2^(n1)1 and k*2^(n+1)1 forms on the server. Here is the final form of the data in our science table for a recent SGS prime:
1054899866865*2^12900001 is prime! Time : 2542.378 sec.
1054899866865*2^1290000+1 is not prime. Proth RES64: B0CF6CED1998C23F Time : 2498.885 sec.
1054899866865*2^12899991 is not prime. LLR Res64: 32BFA46352FDCC7C Time : 2311.508 sec.
1054899866865*2^12900011 is not prime. LLR Res64: 21D0038F7A5148BA Time : 2277.467 sec.




Okay, why the pair of primes (p; 2p+1) has its own name  Sophie Germain primes,
but the pair of primes (p; 2p1) hasn't, it has only the general name "Cunningham chain of the second kind of lehgth 2" ?
Do we have a plan to establish the search of the largest pair of primes (p; 2p1) just as Sophie Germain Prime Search attempts to find the largest pair of primes (p; 2p+1)?
If a prime p is the Proth number, p = k*2^n+1,
2p1 is the Proth number too: 2p1 = k*2^(n+1)+1
I guess the pair of primes
648309*2^148311+1  Cunningham chain 2nd kind (2p1)
648309*2^148310+1  Cunningham chain 2nd kind (p)
is small enough (44652 and 43058 digits) and there is a sense try to renew the world record. What do you think about that?
____________




JimB wrote:
For every SGS prime, no matter whether the +1 form is prime or not we test both the k*2^(n1)1 and k*2^(n+1)1 forms on the server. Here is the final form of the data in our science table for a recent SGS prime:
1054899866865*2^12900001 is prime! Time : 2542.378 sec.
1054899866865*2^1290000+1 is not prime. Proth RES64: B0CF6CED1998C23F Time : 2498.885 sec.
1054899866865*2^12899991 is not prime. LLR Res64: 32BFA46352FDCC7C Time : 2311.508 sec.
1054899866865*2^12900011 is not prime. LLR Res64: 21D0038F7A5148BA Time : 2277.467 sec.
My question was about testing k*2^(n+1)+1 if k*2^n+1 is prime.
But k*2^n+1 is checked only when k*2^n1 is prime.
So k*2^(n+1)+1 will be checked only when/if we will find Twin primes, k*2^n1 first and k*2^n+1 second, it happend in PrimeGrid only twice as I know.
____________



compositeVolunteer tester Send message
Joined: 16 Feb 10 Posts: 1108 ID: 55391 Credit: 962,427,254 RAC: 663,306

x3mEn wrote:
My question was about testing k*2^(n+1)+1 if k*2^n+1 is prime.
But k*2^n+1 is checked only when k*2^n1 is prime.
Great idea! Since k*2^n+1 and k*2^(n+1)+1 were filtered by the quad sieve except for the highest n of the range, it's reasonable to start another segment of the SGS project (SGSE?) to test these pairs as potential SGS candidates. The search can run up nwise for fixed k, and use "free" results where SGS has already tested k*2^n+1. If a new test of k*2^n+1 results in a prime, then k*2^n1 can be be ignored where it was already tested by SGS, or it could kick off an early SGS WU for k*2^n1 not already tested. 


Sysadm@NbgVolunteer moderator Volunteer tester Project scientist
Send message
Joined: 5 Feb 08 Posts: 1214 ID: 18646 Credit: 851,940,027 RAC: 111,695

no available SGS llr tasks
as_of_now wrote: 3219 Sophie Germain Prime Search (LLR) 0 / 0
is this shortage planned for any reason?
____________
Sysadm@Nbg
my current lucky number: 113856050^65536 + 1
PSAPRPNetStatsURL: http://ugf.de/PRPNet/



Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

no available SGS llr tasks
is this shortage planned for any reason?
Fixed, and no.
EDIT: and if you're reading this immediately after I posted it, the front page only updates every 5 minutes, so it might still show 0 even though there actually is work available right now.
____________
My lucky number is 75898^{524288}+1 


Sysadm@NbgVolunteer moderator Volunteer tester Project scientist
Send message
Joined: 5 Feb 08 Posts: 1214 ID: 18646 Credit: 851,940,027 RAC: 111,695

no available SGS llr tasks
is this shortage planned for any reason?
Fixed, and no.
EDIT: and if you're reading this immediately after I posted it, the front page only updates every 5 minutes, so it might still show 0 even though there actually is work available right now.
got some tasks
thanks a lot (helping me on my run to the gold badge)
thought, it could been in relation with some wrapper or appupdates you let the work run out
____________
Sysadm@Nbg
my current lucky number: 113856050^65536 + 1
PSAPRPNetStatsURL: http://ugf.de/PRPNet/




We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors. The opportunity to find SG's and Twins in the same sieve file is appealing. However, we "expect" to find a Sophie Germain prime first.
Probably a silly question, but I tried to check if the recent find was part of a longer chain (Cunningham chain) which, unsurprisingly, is not the case:
2618163402417*2^1289999  1 has factor 5
2618163402417*2^1290000  1 prime (Sophie Germain)
2618163402417*2^1290001  1 prime (safe prime)
2618163402417*2^1290002  1 has factor 91331
But this made me wonder. Given the quoted description of the sieve, since it is known that we started from 2618163402417*2^1290000  1, so with the notation from above k=2618163402417 and n=1290000, then how is it possible that k*2^(n1)1 has such a small factor (5 is small!)? See the above description of a "quad sieve".
/JeppeSN 


Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 783 ID: 164101 Credit: 305,458,910 RAC: 4,919

2618163402417*2^1289999  1 has factor 5
[...] how is it possible that k*2^(n1)1 has such a small factor (5 is small!)?
2618163402417 mod 5 = 2
2^1289999 mod 5 = 2^(1289999 mod 4) mod 5 = 2^3 mod 5 = 3 [Fermat's little theorem]
2*31 = 5




2618163402417*2^1289999  1 has factor 5
[...] how is it possible that k*2^(n1)1 has such a small factor (5 is small!)?
2618163402417 mod 5 = 2
2^1289999 mod 5 = 2^(1289999 mod 4) mod 5 = 2^3 mod 5 = 3 [Fermat's little theorem]
2*31 = 5
Sure, but that is not what I ask! I do see that 5 divides that number.
I ask why this project considered 2618163402417*2^1290000  1 at all. The description I quoted said "This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors.", however in our case the secondlast one of them did have a small divisor (namely 5).
So how does that "quad sieve" work? Does the sieve permit just one of those three related numbers to have a trivial factor?
Given p = 2618163402417*2^1290000  1, the three related numbers are p+2, (p1)/2, and 2p+1. Since (p1)/2 has a supersmall factor (5), why did the sieve not remove p?
/JeppeSN 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

Given that the first post mentions n=666666, perhaps the quadsieve was done for that one and only a triple sieve was done for 1.29M?
Definitely the current one would not have survived a quad sieve. Only multiples of 15 would have survived a quad sieve. Looking at the 1290000 "normal" primes, roughly half of them don't fit this criteria.
EDIT: The initial sieving (small p) would've been done for different kranges, and then the survivors would've been combined into a single file. It could be that only some kranges weren't quad sieved. 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

I'm certain the description is either incomplete or being misinterpreted. Small factors in the subsequent tests make sense if you think about it, because it we only tested candidates where all 4 numbers remained in the sieve, we would only be testing numbers where:
a) A twin is possible
AND
b) an SGS pair with n1 is possible
AND
c) an SGS pair with n+1 is possible
If we require all three to be true, then many actual SGS pairs and many twins would be skipped, because all 3 conditions need to be satisfied. That doesn't make a lot of sense to me  and I doubt it makes sense to anyone else, either.
On the other hand, if the quad sieve allows the candidate to pass through when ANY of those three conditions are true, you have this:
a) A twin is possible
OR
b) an SGS pair with n1 is possible
OR
c) an SGS pair with n+1 is possible
Which makes a LOT more sense  you'll be testing candidates that can be EITHER a twin or an SGS, but not requiring the candidate to potentially be both.
When you do the sieve this way, you'll see candidates in the subsequent tests that were sieved out, including candidates with small factors.
(I'm speculating here  I'm not certain exactly what criteria the sieve is using to remove candidates. However, smallfactor removal ARE very common in the serverside tests, and it makes far more sense for the sieve to work as an "OR" rather than an "AND".)
____________
My lucky number is 75898^{524288}+1 



Michael, I am not sure it makes sense. The quote "The opportunity to find SG's and Twins in the same sieve file is appealing" is not very relevant if you use "OR  OR" rather than "AND  AND", because then for most of the candidates, in reality, there would be (very often) just a single chance (not three chances) for a "pairing".
I thought we were indeed skipping a lot of SGS pairs because we insisted on having three chances for every prime found.
But someone who knows precisely how the quad sieve is supposed to work, and what k values were in fact quad sieved for 1290000, will surely give an authoritative answer soon.
/JeppeSN




SG pair is a Cunningham chain of length n=2.
How does one maximize their chances of success of finding one? Anyone who pondered about this question for more than a moment would realize that one would want to sieve for chains of length n+1, then check the middle survivor (because this is a computationally expensive check) and then have double chances of completing the chain.
For larger n values, one can improve slightly more; e.g. for a chain of length n=6, one can sieve for length n+2, then check the middle 4 elements {c(i),c(i+1),c(i+2),c(i+3)} and if successful, proceed to checking c(i1),c(i+4); if one of them is prime use the last chance, and if both are prime, one already has a CC6 and still a minuscule chance of CC7 and CC8.
So, notwithstanding that this SG pair was found (congratulations!) and that it would not have been found if quad sieving was done correctly,  the fact is that over the same time/effort you would have found perhaps two SG pairs (different from this one, of course) and/or would have found the first of the two already a year ago. 



SG pair is a Cunningham chain of length n=2.
How does one maximize their chances of success of finding one? Anyone who pondered about this question for more than a moment would realize that one would want to sieve for chains of length n+1, then check the middle survivor (because this is a computationally expensive check) and then have double chances of completing the chain.
For larger n values, one can improve slightly more; e.g. for a chain of length n=6, one can sieve for length n+2, then check the middle 4 elements {c(i),c(i+1),c(i+2),c(i+3)} and if successful, proceed to checking c(i1),c(i+4); if one of them is prime use the last chance, and if both are prime, one already has a CC6 and still a minuscule chance of CC7 and CC8.
So, notwithstanding that this SG pair was found (congratulations!) and that it would not have been found if quad sieving was done correctly,  the fact is that over the same time/effort you would have found perhaps two SG pairs (different from this one, of course) and/or would have found the first of the two already a year ago.
So you seem to say this search was not performed in an optimal way.
But can anyone shed some light on how the sieving was actually done up to now? Was a quad sieve used, and if yes, how does that sieve operate (algorithm)?
/JeppeSN 



I have not checked how TwinGen is coded (and more importantly how was it actually applied), but NewPgen (see source here) proceeds by iterating over a prime generator, finding the modular exponent 2^n mod p (or (1/2)^n mod p for some sieving modes) and then removing k values for all requested composite candidates for each of the four variations (there is no room for "OR"s in that algorithm; if any of the four derivative forms k*2^(n+x)+c (where x and c are some pertinent subset of 1,0,1, ...as well as some higher x>1 for CC sieving) is divisible by p, then k is struck out; the bitmask/sparsearray structure for all prior k values does not have any counters of strikeouts or similar  only 1 or 0 for each k). NewPgen has some excellent heuristics for managing the large bit arrays and switches between when the initially huge input range collapses, but it does manage single bits; no second chances (say, 3 out of 4) are given  the latter can only be arranged by external scripting; it's not hard even if a bit tedious.
TwinGen page is quite informative on multisieve principles, and (I quote) "The decision criteria and discussion is more than can be easily typed into an introductory web page." 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

But can anyone shed some light on how the sieving was actually done up to now? Was a quad sieve used, and if yes, how does that sieve operate (algorithm)?
Unfortunately, no. Lennart is the one who did the sieving, and he's not available.
____________
My lucky number is 75898^{524288}+1 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

But can anyone shed some light on how the sieving was actually done up to now? Was a quad sieve used, and if yes, how does that sieve operate (algorithm)?
Looking at the found primes, it seems that this search was using a Triple sieve only. TwinGen supports the requisite triple sieve (Twin/SG k.2^n±1 and k.2^(n+1)1). So there was only double the chance of finding a pair (compared to regular SG search), instead of triple chance had it been a quad sieve.
But had it been a quad sieve, it is possible that the k values would have been too high for LLR to test it efficiently and/or the sieving range would have been too large to effectively manage. /speculation 



But had it been a quad sieve, it is possible that the k values would have been too high for LLR to test it efficiently and/or the sieving range would have been too large to effectively manage. /speculation
Clearly the k values would grow faster with a "quad" criterion, but it would be natural to just skip to another n value, for example go from n=1,290,000 to n=1,290,005 and so on, or something like that. /JeppeSN 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

Clearly the k values would grow faster with a "quad" criterion, but it would be natural to just skip to another n value, for example go from n=1,290,000 to n=1,290,005 and so on, or something like that. /JeppeSN
Yep, the obvious downside being that it would double the sieve effort. That might not be so bad, but if you needed even more N's, it might add up.
At any rate, I'm firmly in the "quad sieve if you can" camp. I was merely speculating the reasons why it was not done. 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

One thing I can answer: We're going to continue searching the current n range of 1290000 for more Sophie Germain pairs and twin primes. This will continue at least until SGS falls off the bottom of the T5K list. I expect that to be in about 18 months. We will reevaluate staying at 1290000 at that time.
There's about 10 years worth of work remaining at 1290000.
____________
My lucky number is 75898^{524288}+1 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

One thing I can answer: We're going to continue searching the current n range of 1290000 for more Sophie Germain pairs and twin primes. This will continue at least until SGS falls off the bottom of the T5K list. I expect that to be in about 18 months. We will reevaluate staying at 1290000 at that time.
There's about 10 years worth of work remaining at 1290000.
It is not too late to retroactively quad sieve the remaining candidates (or rather, just sieve for the missing form). That will reduce the number of candidates (by a factor of 20+/) and provide 50% extra ROI on LLR (2 instead of 3 chances for a pair). 



The next Challenge is the SGS LLR with the challenge being held for 1 day. Is this misprint or are we just having a crunch fest of the fastest computers. Maybe I am really thick but 11 days seems more of a contest for the proletarian as myself, to participate in. A one day challenge is not very much to crunch unless you have a Super. Hmmm, how much are those going for, wonder if I can get a lease, or lease time? LOL 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

The next Challenge is the SGS LLR with the challenge being held for 1 day. Is this misprint or are we just having a crunch fest of the fastest computers. Maybe I am really thick but 11 days seems more of a contest for the proletarian as myself, to participate in. A one day challenge is not very much to crunch unless you have a Super. Hmmm, how much are those going for, wonder if I can get a lease, or lease time? LOL
They're REALLY short tasks. Unless your computer is very, very old, you should be able to do quite a few of these in 24 hours. I'll certainly do several times as many tasks in that 1 day challenge as I'll do in the current ESP 5 day challenge.
One reason that we run short challenges when running short tasks like this is that a long challenge would generate millions of SGS tasks, and this could cause problems with the performance of the server's database.
Another reason this challenge is short is to add some variety to the schedule.
(The SGS challenge in 2014 was also a 1 day challenge.)
____________
My lucky number is 75898^{524288}+1 



Hi,
is this the only project to search for twinprimes or are there other projects on PrimeGrid that specifically look for them?
Thanks and cheers,
Chris 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

Hi,
is this the only project to search for twinprimes or are there other projects on PrimeGrid that specifically look for them?
Thanks and cheers,
Chris
This is the only project to search specifically for twin primes.
While it's theoretically possible for some other projects to find, separately, twin primes, it's extremely unlikely. A few projects test both the +1 and 1 versions of numbers, so there's a (very small) possibility that they could find two primes that are only separated by a value of 2.
Those projects are:
321
The combination of Cullen and Woodall together finding a twin (Woodall finding the 1, Cullen finding the +1)
27 (PRPNet)
121 (PRPNet)
Primorial (PRPNet)
Factorial (PRPNet)
____________
My lucky number is 75898^{524288}+1 



Thank you Michael for the answer.
That is what I figured.
Thanks,
Chris




Thanks Michael, just the thing to OC for.
____________
GPU drivers 



Out of curiosity:
All new (e.g.,) GFN15 primes are reported on the message boards, but new primes found in the SG search are not. What is the reason for this? Are they too numerous, or are they deemed uninteresting?
I'm not critical, just curious.



CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 3188 ID: 50683 Credit: 122,490,922 RAC: 937,411

Out of curiosity:
All new (e.g.,) GFN15 primes are reported on the message boards, but new primes found in the SG search are not. What is the reason for this? Are they too numerous, or are they deemed uninteresting?
I'm not critical, just curious.
They are reported
Newly reported primes
39884560^32768+1 (Mumps [MM]); 3172136327715*2^12900001 (meteor); 3175204825947*2^12900001 (puh32); 3170617556925*2^12900001 (masumi hamada);
____________
92*10^^{1439761}1 NEARREPDIGIT PRIME :) :) :)
4 * 650^^{498101}1 CRUS PRIME
2022202116^^{131072}+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! 



>They are reported
But not in the "Sophie Germain Prime Search" forum, sticky thread style, right?
But rather, I presume, under "Primegrid Primes by Project".
I was curious why some types of primes get a sticky thread whereas others don't. (It is not a terribly important question, as you call tell.)



CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 3188 ID: 50683 Credit: 122,490,922 RAC: 937,411

>They are reported
But not in the "Sophie Germain Prime Search" forum, sticky thread style, right?
But rather, I presume, under "Primegrid Primes by Project".
I was curious why some types of primes get a sticky thread whereas others don't. (It is not a terribly important question, as you call tell.)
GFN is special case: because GFN 15 is too small to go to TOP5000, so if you have find it, you will never know. On the other side SGS is going to Top 5000 prime list, so you will got mail when you find it, and also will appear in the front page under newly discovered prime.
____________
92*10^^{1439761}1 NEARREPDIGIT PRIME :) :) :)
4 * 650^^{498101}1 CRUS PRIME
2022202116^^{131072}+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

Out of curiosity:
All new (e.g.,) GFN15 primes are reported on the message boards, but new primes found in the SG search are not. What is the reason for this? Are they too numerous, or are they deemed uninteresting?
I'm not critical, just curious.
The reason is because I've been very involved in the GFN search and I take the time to personally post those messages. Part of that is due to the fact that the n=32768 primes are the only primes too small not to reported, so if I didn't do that there wouldn't be much of a permanent record of the details of their discovery.
Also, "SGS primes" aren't actually Sophie Germain primes. Once in a blue moon we find a Sophie Germain pair or a twin prime, but otherwise the primes found by SGS are just ordinary run of the mill small primes. SG pairs and twin primes get a full official announcement, of course.
But the real reason is that I put together some message threads on the forums to help me organize the expanding GFN search late last year, and never saw a reason to stop collecting that information.
____________
My lucky number is 75898^{524288}+1 



OK, thanks guys, good to know. 



Sophie Germain Prime Search
...
We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors. The opportunity to find SG's and Twins in the same sieve file is appealing....
Have I understood this correctly please
You eliminated a k, n combo at the sieving stage if ANY ONE of the four targets was found to be composite?




Sophie Germain Prime Search
...
We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors. The opportunity to find SG's and Twins in the same sieve file is appealing....
Have I understood this correctly please
You eliminated a k, n combo at the sieving stage if ANY ONE of the four targets was found to be composite?
The last time a Sophie Germain prime was found, it started from the number:
a = 2618163402417*2^12900001
which had clearly not been removed by the sieve. The three related numbers were:
x = 2618163402417*2^1290000+1
y = 2618163402417*2^12899991
z = 2618163402417*2^12900011
It turned out that z was also prime.
At the time I noted that the number y above had small factors like 5, 11, and 61. That was a surprise to me at the time.
So it shows that the sieve did not work the way you think at the time we sieved for this candidate.
Maybe it should have? Perhaps I can find the thread from then ...
/JeppeSN 



Similarly, the last time a twin prime was found, it started from the number:
a = 2996863034895*2^12900001
which had clearly not been removed by the sieve. The three related numbers were:
x = 2996863034895*2^1290000+1
y = 2996863034895*2^12899991
z = 2996863034895*2^12900011
It turned out that x was also prime.
Again I noted that the number y above had small factors like 7^2, 13, 53, 1523, 3373, and 451331.
Can anyone tell how the quad sieve works? If "a" has no small factors, is it enough that two of the three numbers "x", "y", and "z" also has no small factors?
/JeppeSN 



The quad sieve must be broken!
For each of 30 recent primes found in this project, call them a, so:
a = k*2^1290000  1
I checked for very small factors of the numbers:
x(a) = a + 2 = k*2^1290000 + 1
y(a) = (a  1)/2 = k*2^1289999  1
z(a) = 2*a + 1 = k*2^1290001  1
In no of the 30 cases did I find any small factors of x(a) or z(a).
In every case (out of the 30 cases possible), I found small factors of y(a). See here:
3245342317875:
163,259201,483247,
3243877613865:
19,337,4409,11959,
3243218889057:
5,
3242533780995:
13,31,453703,
3241517936247:
5,37,41011,
3241123387077:
5,7,31,2357,197963,
3241051435695:
3583,296843,
3240418526427:
5,
3238753581357:
5,179,7253,12007,
3238123437705:
7,11,67,
3236272270647:
5,19,281,
3235742767257:
5,154991,
3233188072077:
5,13,29,5659,
3233012242845:
105817,
3231473842905:
7321,448607,
3229863126525:
11,17,103,
3229683461217:
5,73,
3229486111887:
5,11,1091,28163,
3229219894197:
5,29,23059,604973,
3228908406225:
2141,
3228803925615:
7,59,683,6553,35291,
3228238240185:
11,251,479,39113,
3226875304635:
293,
3226135737645:
7,13,
3225985652307:
5,13,
3225013611657:
5,11,811,64151,
3224599971255:
89,281,111857,
3224481727857:
5,12923,
3222254520285:
59,163,
3222237085707:
5,11,1721,
The table lists k value followed by a colon, and in the next line small factors of the y number associated to that k. Not indicated if the square or cube of the primes in the commaseparated list actually divides the number.
Will someone please check if I am right? I do not want to conclude that the quad sieve is broken and never checks the y number.
/JeppeSN 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

I don't know exactly how it works  but I know I would NOT want it to work they way you're suggesting.
The way it SHOULD work is that as long as (a) is not factored out, the candidate should stay in the sieve if ANY of (x), (y), or (z) is also not factored out. That way you have the greatest chance of finding a twin or a Sophie. If you required all three to not have any factors, you would eliminate most of the actual twins or Sophies from the sieve, no?
It doesn't surprise me that you're finding that one of x, y, or z always has small factors. I'd be surprised if they didn't.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

Sophie Germain Prime Search
...
We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors. The opportunity to find SG's and Twins in the same sieve file is appealing....
Have I understood this correctly please
You eliminated a k, n combo at the sieving stage if ANY ONE of the four targets was found to be composite?
(See my previous reply. This answers your question directly.)
Speculation (this is how it should work, but I don't know if it actually works this way): The a, k, n combo is removed from the sieve ONLY if that number has a factor and NONE of the other three have a factor.
____________
My lucky number is 75898^{524288}+1 



I don't know exactly how it works  but I know I would NOT want it to work they way you're suggesting.
The way it SHOULD work is that as long as (a) is not factored out, the candidate should stay in the sieve if ANY of (x), (y), or (z) is also not factored out. That way you have the greatest chance of finding a twin or a Sophie. If you required all three to not have any factors, you would eliminate most of the actual twins or Sophies from the sieve, no?
It doesn't surprise me that you're finding that one of x, y, or z always has small factors. I'd be surprised if they didn't.
But in 30 cases out of 30 possible it was (y) that had a small factor. Never (x), never (z).
This is either (I) an extremely unlikely coincidence. Or (II) some theorem that with our choice of n (n=1290000) the (y) case has a much different possibility than the other cases. Or (III) some bug in the sieve.
Or (IV) some other explanation.
I could be fooling myself? Will think about it for a while.
/JeppeSN 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

But in 30 cases out of 30 possible it was (y) that had a small factor. Never (x), never (z).
This is either (I) an extremely unlikely coincidence. Or (II) some theorem that with our choice of n (n=1290000) the (y) case has a much different possibility than the other cases. Or (III) some bug in the sieve.
Or (IV) some other explanation.
I could be fooling myself? Will think about it for a while.
/JeppeSN
I found that interesting as well.
____________
My lucky number is 75898^{524288}+1 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

But in 30 cases out of 30 possible it was (y) that had a small factor. Never (x), never (z).
It turns out your data set was too small. You checked 30 cases. We keep that information in our primes database, so I checked all 2729 SGS primes with n=1290000:
mysql> select count(*) from primes where project='sgs' and n=1290000;
++
 count(*) 
++
 2729 
++
1 row in set (0.02 sec)
mysql> select count(*) from primes where project='sgs' and n=1290000 and extra like '%12899991 has a small factor%';
++
 count(*) 
++
 1847 
++
1 row in set (0.01 sec)
mysql> select count(*) from primes where project='sgs' and n=1290000 and extra not like '%12899991 has a small factor%';
++
 count(*) 
++
 882 
++
1 row in set (0.02 sec)
mysql> select count(*) from primes where project='sgs' and n=1290000 and extra like '%12899991 is not prime%';
++
 count(*) 
++
 882 
++
1 row in set (0.02 sec)
____________
My lucky number is 75898^{524288}+1 



How often do '%1290000+1' and '%12900011' have small factors, in comparison?
/JeppeSN 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

How often do '%1290000+1' and '%12900011' have small factors, in comparison?
/JeppeSN
Well, that's certainly an interesting question.
The answer is "None".
____________
My lucky number is 75898^{524288}+1 



So out of 2729 cases, for what I called (y), in 1847 cases (68%) there was a "small factor" (as defined by your database).
And for the same 2729 cases, there were no cases (0%) where (x) had a "small factor", and no cases (0%) where (z) had a "small factor".
Maybe there is really something wrong with the quad sieve. Does it check (a + 3)/2 instead of (a  1)/2?
Michael Goetz, it could be interesting to check a sample of cases where the main number (what I called (a)) has survived the sieve but not yet been primality tested. For such a sample, how many percent of x(a), y(a), z(a) have a "small factor"? I want to check the output of the sieve directly, with no filtering down to the cases where (a) is prime.
/JeppeSN 



Also see the posts above (this thread!) from 1 March 2016 when the latest Sophie Germain prime had recently been found. User serge (Serge Batalov) had some interesting comments on how a quad sieve should work (after I had pointed out that y(a) was divisible by 5). /JeppeSN 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

So out of 2729 cases, for what I called (y), in 1847 cases (68%) there was a "small factor" (as defined by your database).
And for the same 2729 cases, there were no cases (0%) where (x) had a "small factor", and no cases (0%) where (z) had a "small factor".
Maybe there is really something wrong with the quad sieve. Does it check (a + 3)/2 instead of (a  1)/2?
Michael Goetz, it could be interesting to check a sample of cases where the main number (what I called (a)) has survived the sieve but not yet been primality tested. For such a sample, how many percent of x(a), y(a), z(a) have a "small factor"? I want to check the output of the sieve directly, with no filtering down to the cases where (a) is prime.
/JeppeSN
I only have that information for primes.
EDIT: Actually, those tests are not done at all UNLESS 'a' is prime, so the data doesn't exist.
____________
My lucky number is 75898^{524288}+1 



I only have that information for primes.
EDIT: Actually, those tests are not done at all UNLESS 'a' is prime, so the data doesn't exist.
If you can post (or mail me) 30 recent values of k where k*2^1290000  1 was not prime, I can quickly test for extremely small factors of the 30 × 3 related numbers. Just to confirm that the pattern is the same.
I expect it will be the same as for the 30 k values I found from primes.
/JeppeSN 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

I only have that information for primes.
EDIT: Actually, those tests are not done at all UNLESS 'a' is prime, so the data doesn't exist.
If you can post (or mail me) 30 recent values of k where k*2^1290000  1 was not prime, I can quickly test for extremely small factors of the 30 × 3 related numbers. Just to confirm that the pattern is the same.
I expect it will be the same as for the 30 k values I found from primes.
/JeppeSN
Ask me again when we're closer to the end of the current sieve file, which will be in about 10 years. I'm not going to put any more time into this right now, sorry.
____________
My lucky number is 75898^{524288}+1 


axnVolunteer developer Send message
Joined: 29 Dec 07 Posts: 285 ID: 16874 Credit: 28,027,106 RAC: 0

Looking at the found primes, it seems that this search was using a Triple sieve only. TwinGen supports the requisite triple sieve (Twin/SG k.2^n±1 and k.2^(n+1)1). So there was only double the chance of finding a pair (compared to regular SG search), instead of triple chance had it been a quad sieve.
I know quoting oneself is bad form, but sheesh! I also outlined a proposal for fixing it (you can find it in this thread).
@Michael  Your understanding of quad sieve is wrong. A quad sieve (or a triple sieve, in this case) will eliminate a candidate if _any_ one of the 4 (resp, 3) forms has a factor. Why? Because, we're not looking to find all possible pairs, but merely trying to maximize the chance of a pair for a given candidate. Suppose you have two candidates k1 & k2. We know that all four of k1 has no small factor. But for k2, two of the side forms have small factor. Which would you test for central form? Answer: k1. Because if the central form turns out to be prime, k1 offers 3 potential chances of a pair, but k2 only offers 1 chance. So we're trying to maximize our LLR investment here.
All of this was discussed previously, in this very thread. 



[...]A quad sieve (or a triple sieve, in this case) will eliminate a candidate if _any_ one of the 4 (resp, 3) forms has a factor. Why? Because, we're not looking to find all possible pairs, but merely trying to maximize the chance of a pair for a given candidate. Suppose you have two candidates k1 & k2. We know that all four of k1 has no small factor. But for k2, two of the side forms have small factor. Which would you test for central form? Answer: k1. Because if the central form turns out to be prime, k1 offers 3 potential chances of a pair, but k2 only offers 1 chance. So we're trying to maximize our LLR investment here.
I agree.
We will never run out of candidates. But we want to make sure we only invest effort in candidates a such that if a is prime, we have a threefold chance with x(a), y(a), and z(a).
If we have two chances instead of three, I would say we find interesting matches (i.e. a is lower member of twin, or a is a safe prime, or a is a Sophie Germain prime) at a rate which is only 67% of the rate we would have otherwise.
/JeppeSN 



Sophie Germain Prime Search
...
We'll be searching the form k*2^n1. If it is prime, then we'll check k*2^n+1, k*2^(n1)1, & k*2^(n+1)1. We are able to do this because a quad sieve was performed for this search. This sieve ensured that k*2^n1, k*2^n+1, k*2^(n1)1, & k*2^(n+1)1 did not have any small prime divisors. The opportunity to find SG's and Twins in the same sieve file is appealing....
Have I understood this correctly please
You eliminated a k, n combo at the sieving stage if ANY ONE of the four targets was found to be composite?
I think this comes down to exaclt what is being aimed for.
If the aim is to maximise the number of Pairs found in a given amount of crunching, then to eliminate all four candidates as soon as any one of them is found composite makes sense.
If the aim is to generate a complete list of Twin Primes and of SG primes (of a given form, and up to some limit), then that strategy leaves "holes" in the series.
Neither strategy is wrong  it just depends what you hope to do. And just to clarify, I asked because I was curious, and not to support one interpretation as opposed to another. As I have decided to be doing a lot of SGS work over the coming 29 days, I simply wanted to know exactlly what I was doing.
In terms f the "competitive" side of the TdP, whatever the sieve does it is the same for everyone, so in that sense it is fair whatever the answer is.
Regards
River~~
(See my previous reply. This answers your question directly.)
Speculation (this is how it should work, but I don't know if it actually works this way): The a, k, n combo is removed from the sieve ONLY if that number has a factor and NONE of the other three have a factor.



HonzaVolunteer moderator Volunteer tester Project scientist Send message
Joined: 15 Aug 05 Posts: 1943 ID: 352 Credit: 5,939,210,715 RAC: 1,574,944

On a side note
n=666666, max k completed was 38 499 999 389 745
n=1290000, max k completed is 3 844 674 282 897
We are very close to 1/10 of previous range. But, according to stats, we have done about 3x more tests and found almost 2x more primes.
____________
My stats 



The SGS pair and twin prime badges may be even harder to get than the AP27 badge.
How can we discover an SGS pair?
Would calculation time be doubled if a prime is found because we run the test for k·2^1290000+1 too?
If yes, always when k·2^12900001 is prime or sometimes when another condition is true?
What other subprojects would give us the chance to discover twin primes? SGS pairs are twin primes, aren't?
Anyway looks like StarGate and/or SETI.Germany acronyms. LOL 


Scott BrownVolunteer moderator Project administrator Volunteer tester Project scientist
Send message
Joined: 17 Oct 05 Posts: 2359 ID: 1178 Credit: 17,586,559,455 RAC: 5,278,986

The SGS pair and twin prime badges may be even harder to get than the AP27 badge.
How can we discover an SGS pair?
Just by running work in the SGS project. All primes found in this project are checked to see if it is also an SG pair and a Twin prime.
Would calculation time be doubled if a prime is found because we run the test for k·2^1290000+1 too?
Yes.
If yes, always when k·2^12900001 is prime or sometimes when another condition is true?
Time is doubled only when a prime is found as that is the event that triggers the check for an SG pair or a Twin.
What other subprojects would give us the chance to discover twin primes? SGS pairs are twin primes, aren't?
SG pairs and Twin primes are only being looked for under the SGS project here at PrimeGrid. SG pairs and Twins are not the same as they have a different form. A twin has the form of 2996863034895*2^1290000+1, 2996863034895*2^12900001 for example. An SG pair has the form 2618163402417*2^12900001, 2618163402417*2^12900011 for example. 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

Would calculation time be doubled if a prime is found because we run the test for k·2^1290000+1 too?
Yes.
If yes, always when k·2^12900001 is prime or sometimes when another condition is true?
Always.
When k·2^12900001 is prime, your computer checks for the twin by testing k·2^1290000+1. When it's reported back to the server, the server will check for Sophie Germain pairs by testing k·2^12899991 and k·2^12900011.
What other projects let us discover twin primes?
In theory, any prime we test for could have a twin. In practice, only SGS is checked to see if it has a twin.
SGS pairs are twin primes, aren't?
No. A twin is when both p and p+2 are prime. A Sophie Germain pair is when both p and 2p+1 are prime. For practical purposes with a prime of the form k*2^n1, a twin changes the '1' to '+1' whereas a Sophie Germain pair adds or subtracts 1 to or from 'n'.
____________
My lucky number is 75898^{524288}+1 



So let me understand (about pairs)...
Scott discovered a Sophie Germain prime (=2618163402417*2^12900001) on 20160229 05:39:14 UTC.
The server did the test of 2p+1 (=2618163402417*2^12900011) for him and it was found to be prime.
The discoverer is still Scott.
Two primes for the price of one!
And the test of (p1)/2 (=2618163402417*2^12899991) was done too, but it was not prime. 



Would calculation time be doubled if a prime is found because we run the test for k·2^1290000+1 too?
Yes.
If yes, always when k·2^12900001 is prime or sometimes when another condition is true?
Always.
When k·2^12900001 is prime, your computer checks for the twin by testing k·2^1290000+1. When it's reported back to the server, the server will check for Sophie Germain pairs by testing k·2^12899991 and k·2^12900011.
What other projects let us discover twin primes?
In theory, any prime we test for could have a twin. In practice, only SGS is checked to see if it has a twin.
SGS pairs are twin primes, aren't?
No. A twin is when both p and p+2 are prime. A Sophie Germain pair is when both p and 2p+1 are prime. For practical purposes with a prime of the form k*2^n1, a twin changes the '1' to '+1' whereas a Sophie Germain pair adds or subtracts 1 to or from 'n'.
So one task may contain two primality tests sometimes...
What happens if cruncher A finds that k*2^n  1 is in fact prime, but finds that the neighbor k*2^n + 1 is composite; then his double checker, cruncher B, finds that both k*2^n  1 and k*2^n + 1 are prime? How would that be resolved?
If more tasks are created until agreement on both numbers is achieved, would either A (finder) or B (double checker) lose his (correct) discovery of k*2^n  1 because he failed (had hardware error) only on the additional test of k*2^n + 1?
/JeppeSN 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

JeppeSN wrote: So one task may contain two primality tests sometimes...
What happens if cruncher A finds that k*2^n  1 is in fact prime, but finds that the neighbor k*2^n + 1 is composite; then his double checker, cruncher B, finds that both k*2^n  1 and k*2^n + 1 are prime? How would that be resolved?
If more tasks are created until agreement on both numbers is achieved, would either A (finder) or B (double checker) lose his (correct) discovery of k*2^n  1 because he failed (had hardware error) only on the additional test of k*2^n + 1?
/JeppeSN
Correct.
Remember that the test for these numbers (the first test) produces a LOT of false primes when there's a hardware error. If the second test produced a bad result, the entire result is bad. Chances are there was a calculation error on the first test as well.
____________
My lucky number is 75898^{524288}+1 



Will the Sophie Germain primes be too small forever to reach the Top 5000 list or would they catchup if we put lots of CPU power on this project? 


dthononVolunteer tester
Send message
Joined: 6 Dec 17 Posts: 434 ID: 957147 Credit: 1,731,167,655 RAC: 188,963

Will the Sophie Germain primes be too small forever to reach the Top 5000 list or would they catchup if we put lots of CPU power on this project?
SGS climbed from 388,341 to 388,342 digits on 20150530, nearly 4 years ago.
GFN16 climbed from 506,357 to 507,330 in about 4 days. There is no way SGS could grow fast enough, given the speed difference.
But SGS is not about finding very large primes. It aims at finding twin primes. 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

Will the Sophie Germain primes be too small forever to reach the Top 5000 list or would they catchup if we put lots of CPU power on this project?
Short answer: SGS tasks grow at a much slower rate than other projects and it will never make it onto the T5K list no matter how many tasks are run.
Unless we resieve for a new n. We do not plan on doing this until we exhaust the current sieve file, which will take years.
____________
My lucky number is 75898^{524288}+1 



Hi all,
Is SGS one of the projects that DOESN'T use multithreading?
I have a config set but it doesn't seem to work with SGS and I remember someone saying during the PG challenge that one of the projects didn't use multithreading. Guessing its SGS?
<app>
<name>llrSGS</name>
<fraction_done_exact/>
<report_results_immediately/>
</app>
<app_version>
<app_name>llrSGS</app_name>
<cmdline>t 4</cmdline>
<avg_ncpus>4</avg_ncpus>
</app_version>
Does it make any difference if I have this in my app_config file and it's not needed?
Thx in advance.
____________
Слава Україні! 


LumiukkoVolunteer tester Send message
Joined: 7 Jul 08 Posts: 165 ID: 25183 Credit: 867,365,555 RAC: 58,426

Hi all,
Is SGS one of the projects that DOESN'T use multithreading?
I have a config set but it doesn't seem to work with SGS and I remember someone saying during the PG challenge that one of the projects didn't use multithreading. Guessing its SGS?
<app>
<name>llrSGS</name>
<fraction_done_exact/>
<report_results_immediately/>
</app>
<app_version>
<app_name>llrSGS</app_name>
<cmdline>t 4</cmdline>
<avg_ncpus>4</avg_ncpus>
</app_version>
Does it make any difference if I have this in my app_config file and it's not needed?
Thx in advance.
The application name for SGSproject is not llrSGS, it is llrTPS.
Try:
<app>
<name>llrTPS</name>
<fraction_done_exact/>
<report_results_immediately/>
</app>
<app_version>
<app_name>llrTPS</app_name>
<cmdline>t 4</cmdline>
<avg_ncpus>4</avg_ncpus>
</app_version>

Lumiukko 



Ohhhh ok. I didn't know that!
I'll give that a go. Thank you!
____________
Слава Україні! 



The application name for SGSproject is not llrSGS, it is llrTPS.
Yeah, it honors the notsofamous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN 


robishVolunteer moderator Volunteer tester
Send message
Joined: 7 Jan 12 Posts: 2182 ID: 126266 Credit: 7,179,596,591 RAC: 1,612,681

The application name for SGSproject is not llrSGS, it is llrTPS.
Yeah, it honors the notsofamous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN
🤣
____________
My lucky numbers 1059094^{1048576}+1 and 224584605939537911+81292139*23#*n for n=0..26 


Dave Send message
Joined: 13 Feb 12 Posts: 3149 ID: 130544 Credit: 2,214,615,859 RAC: 312,245

The application name for SGSproject is not llrSGS, it is llrTPS.
Yeah, it honors the notsofamous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN
Omg that's my sort of joke that is... 


CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 3188 ID: 50683 Credit: 122,490,922 RAC: 937,411

Ohhhh ok. I didn't know that!
I'll give that a go. Thank you!
Running 4 or 8 threads on such small candidate is awful waste of resources.
But it is yours machines...
____________
92*10^^{1439761}1 NEARREPDIGIT PRIME :) :) :)
4 * 650^^{498101}1 CRUS PRIME
2022202116^^{131072}+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! 



JeppeSN wrote: ...
Yeah, it honors the notsofamous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN
LOL
____________
"Accidit in puncto, quod non contingit in anno."
Something that does not occur in a year may, perchance, happen in a moment. 



Ohhhh ok. I didn't know that!
I'll give that a go. Thank you!
Running 4 or 8 threads on such small candidate is awful waste of resources.
But it is yours machines...
Yeah although I'm finishing a lot of tasks first, it's pretty slow going. I'm starting to think just running 1 task/thread might be better.
My goal is to get my gold badge, not find a prime via being first. Guess I'll have to try and crunch the numbers to see which way gives more credits/day.
410 sec/wu running across 8 threads or whatever the time is doing 8 wu's across 8 threads.
____________
Слава Україні! 


CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 3188 ID: 50683 Credit: 122,490,922 RAC: 937,411

Disable HT on all CPU you have and then take 1WU per core, or leave HT on and take 1WU with two threads. Tha is fastest way. YourCPU doesnot have 8 cores it have 4 real cores and 4 imaginary cores, or HT cores useless on LLR
____________
92*10^^{1439761}1 NEARREPDIGIT PRIME :) :) :)
4 * 650^^{498101}1 CRUS PRIME
2022202116^^{131072}+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! 



Disable HT on all CPU you have and then take 1WU per core, or leave HT on and take 1WU with two threads. Tha is fastest way. YourCPU doesnot have 8 cores it have 4 real cores and 4 imaginary cores, or HT cores useless on LLR
Thanks for the feedback.
Yes I'm aware of what HT is:D
Couldn't I just set my CPU to 50% in the BOINC settings also?
I'm now only using my old i5 3470 which doesn't have HT though. I will put my other PC's back on eventually.
____________
Слава Україні! 


CrunchiVolunteer tester
Send message
Joined: 25 Nov 09 Posts: 3188 ID: 50683 Credit: 122,490,922 RAC: 937,411

Thanks for the feedback.
Yes I'm aware of what HT is:D
Couldn't I just set my CPU to 50% in the BOINC settings also?
I'm now only using my old i5 3470 which doesn't have HT though. I will put my other PC's back on eventually.
I will never understand why is so hard to make 4 steps
1. restart computer
2.enter bios
3. disable HT
4. load windows and enjoy :)
Since you say you know what HT is, question is why you didnot disable it before :)
____________
92*10^^{1439761}1 NEARREPDIGIT PRIME :) :) :)
4 * 650^^{498101}1 CRUS PRIME
2022202116^^{131072}+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie! 


Dave Send message
Joined: 13 Feb 12 Posts: 3149 ID: 130544 Credit: 2,214,615,859 RAC: 312,245

Thanks for the feedback.
Yes I'm aware of what HT is:D
Couldn't I just set my CPU to 50% in the BOINC settings also?
I'm now only using my old i5 3470 which doesn't have HT though. I will put my other PC's back on eventually.
I will never understand why is so hard to make 4 steps
1. restart computer
2.enter bios
3. disable HT
4. load windows and enjoy :)
Since you say you know what HT is, question is why you didnot disable it before :)
Not possible on every BIOS. 



Thanks for the feedback.
Yes I'm aware of what HT is:D
Couldn't I just set my CPU to 50% in the BOINC settings also?
I'm now only using my old i5 3470 which doesn't have HT though. I will put my other PC's back on eventually.
I will never understand why is so hard to make 4 steps
1. restart computer
2.enter bios
3. disable HT
4. load windows and enjoy :)
Since you say you know what HT is, question is why you didnot disable it before :)
Not possible on every BIOS.
And I don't think setting BOINC to use 50% of processors will make it use the actual cores instead of threads all the time will it? Don't know, just asking. I know it helps.
If so, good.
If not, is there anything that can be done to automatically force tasks to run on the true cores only? Besides Process Lasso. For some reason it seemed to use more and more resources for itself on my main system the longer it ran until it was slowing everything down. I finally removed it.
I'm running two computers with 2nd gen Core i7 CPUs. One I can turn HT off, one I can't.
John T 



Can somebody please explain  if I look at list of found Sophie Germain Primes here and in column "Prime" I see for example number
p = 6438607821915*2^12900001
then what it means? It means that p ( 6438607821915*2^12900001 ) is prime and 2*p + 1 ( 6438607821915*2^12900011 ) (here exponent +1) is also prime?
I'm just confused if I have to subtract one (1) or to add one (+1) to exponent 1290000 to get second prime.
Because according to project description all three of 2^(n1)1, 2^n1, 2^(n+1)1 were checked, so I wonder if in that list above I see exponent n = 1290000, then do I have to do 1 or +1 to get second prime? Because both 1 and +1 were checked and any (or both) of those two can be prime. 


Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 210 ID: 1108183 Credit: 13,084,497 RAC: 6,049

Can somebody please explain  if I look at list of found Sophie Germain Primes here and in column "Prime" I see for example number
p = 6438607821915*2^12900001
then what it means? It means that p ( 6438607821915*2^12900001 ) is prime and 2*p + 1 ( 6438607821915*2^12900011 ) (here exponent +1) is also prime?
I'm just confused if I have to subtract one (1) or to add one (+1) to exponent 1290000 to get second prime.
Because according to project description all three of 2^(n1)1, 2^n1, 2^(n+1)1 were checked, so I wonder if in that list above I see exponent n = 1290000, then do I have to do 1 or +1 to get second prime? Because both 1 and +1 were checked and any (or both) of those two can be prime.
The list includes all primes found in the SGS project, regardless of whether any of k*2^(n1)1, k*2^n+1, k*2^(n+1)1 are prime. Almost always, none of the three are prime. (The SGS subproject finds lots of primes, but very few of them actually turn out to be Sophie Germain or twin primes.) One way to isolate the few cases where we did find either a Sophie Germain pair or a twin pair is to look for only the ones with an official announcement: link. There you can see that everything comes in pairs with the same value of k. 



One way to isolate the few cases where we did find either a Sophie Germain pair or a twin pair is to look for only the ones with an official announcement: link.
Thanks that helped a lot! So as I understand there was only one Sophie Germain of exponent size 1 290 000?
Does it mean that both 2618163402417*2^12900001 and 2618163402417*2^12900011 are prime? So I have to do +1 to 1 290 000 in this case to obtain second prime?
Also it was 2016 year when it was found. So for 5 years 20162021 there was no other Sophie Germain prime found for exponent 1 290 000? Right?
Do you know (is there a way to find out) how many exponents have been searched so far? And at this exponent size approximately how many exponents (or work units or years) should be searched through to find next Sophie Germain? For example to reach a chance 95% of finding next Sophie Germain how many exponents or work units or years should be searched through?
Also is the Krange searched incrementally? So 2618163402417 is the smallest K such that K * 2^12900001 is Sophie Germain? One can be sure that this is the smallest K? 



Does it mean that both 2618163402417*2^12900001 and 2618163402417*2^12900011 are prime? So I have to do +1 to 1 290 000 in this case to obtain second prime?
Yes. Links:
PrimeGrid search (has different links)
Sophie Germain Top Twenty
/JeppeSN 


Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 210 ID: 1108183 Credit: 13,084,497 RAC: 6,049

Thanks that helped a lot! So as I understand there was only one Sophie Germain of exponent size 1 290 000?
Does it mean that both 2618163402417*2^12900001 and 2618163402417*2^12900011 are prime? So I have to do +1 to 1 290 000 in this case to obtain second prime?
Also it was 2016 year when it was found. So for 5 years 20162021 there was no other Sophie Germain prime found for exponent 1 290 000? Right?
All correct. We've searched n=1290000 since 2012 and found one Sophie Germain pair and one twin pair. Prior to that we searched n=666666 from 2009 to 2012 and also found one Sophie Germain pair and one twin pair. (Some n=666666 primes show up with slightly larger exponents due to algebraic simplifications; e.g. 4000004 * 2^666666  1 = 1000001 * 2^666668  1.) In addition to JeppeSN's links, some of this information is in the subproject status for SGS.
Do you know (is there a way to find out) how many exponents have been searched so far? And at this exponent size approximately how many exponents (or work units or years) should be searched through to find next Sophie Germain? For example to reach a chance 95% of finding next Sophie Germain how many exponents or work units or years should be searched through?
Also is the Krange searched incrementally? So 2618163402417 is the smallest K such that K * 2^12900001 is Sophie Germain? One can be sure that this is the smallest K?
The current Sophie Germain Search has only searched n=666666 and n=1290000, although there was an earlier subproject called the Twin Prime Search (20072009, it appears) which searched n=195000 and then n=333333.
Before each range begins, there's a sieving phase where we isolate the k's most likely to produce what we're looking for; for the current search this meant finding the k's that have chances to produce both a SG pair and a twin pair. (In fact it's a bit more complicated than thatit was previously stated that we did a quad sieve, but JeppeSN realized some time ago that it was actually only a triple sieve.) Because of this, we can't guarantee what you ask about the smallest k; there are likely several smaller ones which were omitted because e.g. k*2^1290000 + 1 has a small factor. This has no bearing on whether k*2^1290000  1 is a Sophie Germain prime, but if it's obviously not a twin prime, then that makes it less worth the effort to test it.
I don't have the information on how far we'd have to search to likely find a second SG pair, but for what it's worth, we are only planning to search n=1290000 up to k=10^13. We're about 64.5% of the way there after 9 years, so there are still some years left, and it's entirely possibly that we won't find another in this range. 



Just a newbie question, and just to understand how do the projects progress:
Why did the search jump from n=666666 to n=1290000? Is there something special about these exponents? Are they more likely to produce SG primers than others?
Thanks a lot! 


Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 210 ID: 1108183 Credit: 13,084,497 RAC: 6,049

Why did the search jump from n=666666 to n=1290000? Is there something special about these exponents? Are they more likely to produce SG primers than others?
There's nothing mathematically special about them. We search with a fixed n and varying k in order to generate lots of candidates without the numbers getting significantly bigger. When we finished the range that was sieved with n=666666, we moved on to a larger n for a bigger challenge. Lennart was in charge of things in those days, and he coordinated some testing to decide the exact value of the next n. It turned out that computations got significantly slower between n=1290000 and n=1310000 (presumably because of an increase in FFT size), so 1290000 was the natural choice. 


Michael GoetzVolunteer moderator Project administrator
Send message
Joined: 21 Jan 10 Posts: 13899 ID: 53948 Credit: 384,585,761 RAC: 132,106

One characteristic of the exponents is that they're not near an FFT boundary, where some tests would have different FFT sizes, and thus significantly different execution times. This was part of the criteria for selecting the next exponent.
____________
My lucky number is 75898^{524288}+1 



Thanks Ravi and Michael! I need to refresh the maths behind all this tests to understand a lot of more things...
Best wishes. 

