## Other

drummers-lowrise

Message boards : Sophie Germain Prime Search : Sophie Germain Prime Search

 Post to thread Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
John
Honorary cruncher

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

Message 17454 - Posted: 16 Aug 2009 | 15:38:41 UTC
Last modified: 17 Aug 2009 | 14:31:54 UTC

Sophie Germain Prime Search
This is the next addition to PrimeGrid's ever expanding prime search projects. The Sophie Germain Prime search honors Marie-Sophie 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^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1, k*2^n+1, k*2^(n-1)-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 666666-666685)
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

http://primes.utm.edu/glossary/page.php?sort=SophieGermainPrime
http://mathworld.wolfram.com/SophieGermainPrime.html
http://en.wikipedia.org/wiki/Sophie_Germain_prime

http://en.wikipedia.org/wiki/Sophie_Germain
http://www.pbs.org/wgbh/nova/proof/germain.html
____________

Skligmund

Joined: 15 Sep 05
Posts: 230
ID: 765
Credit: 541,666,833
RAC: 0

Message 17459 - Posted: 16 Aug 2009 | 17:00:44 UTC - in response to Message 17454.

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

Thanks guys
____________

Michael (MooooMoo)

Joined: 26 Nov 06
Posts: 14
ID: 4039
Credit: 123
RAC: 0

Message 17470 - Posted: 16 Aug 2009 | 21:09:11 UTC - in response to Message 17459.

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.

Alan

Joined: 8 Oct 08
Posts: 88
ID: 30274
Credit: 19,927,031
RAC: 0

Message 17472 - Posted: 16 Aug 2009 | 21:35:37 UTC - in response to Message 17454.

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

Skligmund

Joined: 15 Sep 05
Posts: 230
ID: 765
Credit: 541,666,833
RAC: 0

Message 17473 - Posted: 16 Aug 2009 | 21:59:54 UTC - in response to Message 17472.

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

pschoefer
Volunteer developer
Volunteer tester

Joined: 20 Sep 05
Posts: 677
ID: 845
Credit: 2,865,160,764
RAC: 517,112

Message 17482 - Posted: 17 Aug 2009 | 7:44:43 UTC - in response to Message 17454.

We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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?
____________

[AF>Le_Pommier] Aillas
Volunteer moderator
Volunteer tester

Joined: 4 Jul 07
Posts: 1092
ID: 9587
Credit: 247,299,477
RAC: 39,469

Message 17484 - Posted: 17 Aug 2009 | 8:56:35 UTC

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

Lennart SM5YMT
Honorary cruncher

Joined: 7 May 07
Posts: 1125
ID: 7989
Credit: 694,692,344
RAC: 0

Message 17486 - Posted: 17 Aug 2009 | 11:34:18 UTC - in response to Message 17484.

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

Lennart SM5YMT
Honorary cruncher

Joined: 7 May 07
Posts: 1125
ID: 7989
Credit: 694,692,344
RAC: 0

Message 17487 - Posted: 17 Aug 2009 | 11:38:06 UTC - in response to Message 17482.
Last modified: 17 Aug 2009 | 11:45:03 UTC

We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1 and if prime you will also search k*2^n+1

We will search all primes externally on PG server for k*2^(n-1)-1, & k*2^(n+1)-1

Lennart

John
Honorary cruncher

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

Message 17495 - Posted: 17 Aug 2009 | 14:29:18 UTC - in response to Message 17472.

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

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.
____________

Alan

Joined: 8 Oct 08
Posts: 88
ID: 30274
Credit: 19,927,031
RAC: 0

Message 17498 - Posted: 17 Aug 2009 | 14:57:12 UTC - in response to Message 17495.

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

John
Honorary cruncher

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

Message 17500 - Posted: 17 Aug 2009 | 15:00:49 UTC - in response to Message 17498.

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.
____________

Alan

Joined: 8 Oct 08
Posts: 88
ID: 30274
Credit: 19,927,031
RAC: 0

Message 17505 - Posted: 17 Aug 2009 | 16:22:21 UTC - in response to Message 17500.

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
____________

Lennart SM5YMT
Honorary cruncher

Joined: 7 May 07
Posts: 1125
ID: 7989
Credit: 694,692,344
RAC: 0

Message 17506 - Posted: 17 Aug 2009 | 16:31:53 UTC - in response to Message 17505.
Last modified: 17 Aug 2009 | 19:36:57 UTC

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^450000-1 is not prime. LLR Res64: 41DC49206C003650 Time : 191.636 sec.
95*2^450000-1 is not prime. LLR Res64: B68A9B531D48CE4C Time : 237.690 sec.
207*2^450000-1 is not prime. LLR Res64: AFA085A93236BE97 Time : 237.702 sec.
509*2^450000-1 is not prime. LLR Res64: 2EF3E515DE834DC4 Time : 237.519 sec.
1049*2^450000-1 is not prime. LLR Res64: 84A3F5A1A834BDCC Time : 246.983 sec.
2019*2^450000-1 is not prime. LLR Res64: BB3B39FDAFE07AC4 Time : 247.371 sec.
5043*2^450000-1 is not prime. LLR Res64: 0289F1AE44813108 Time : 246.789 sec.
10007*2^450000-1 is not prime. LLR Res64: B8854C4D30576ABA Time : 246.766 sec.
20015*2^450000-1 is not prime. LLR Res64: D2BCF73F969CD087 Time : 324.821 sec.
50003*2^450000-1 is not prime. LLR Res64: F019BEEFDD7C3B7D Time : 324.970 sec.
100095*2^450000-1 is not prime. LLR Res64: F197B35F9F5626A9 Time : 324.837 sec.
200007*2^450000-1 is not prime. LLR Res64: 6CD221DB2CF8348E Time : 324.883 sec.
500015*2^450000-1 is not prime. LLR Res64: 5BB10EA4AB0C28CA Time : 432.913 sec.
1000023*2^450000-1 is not prime. LLR Res64: EDB3E49680CB449D Time : 432.925 sec.
2000049*2^450000-1 is not prime. LLR Res64: 954B92D0B4AEB21C Time : 432.858 sec.
5000019*2^450000-1 is not prime. LLR Res64: 26F59AB7C18268C7 Time : 432.948 sec.
10000133*2^450000-1 is not prime. LLR Res64: 9D18BDFB989F45A6 Time : 432.861 sec.
20000187*2^450000-1 is not prime. LLR Res64: 76E252A6FD6C5468 Time : 433.279 sec.
50000043*2^450000-1 is not prime. LLR Res64: 9C985D5E47C95E98 Time : 433.091 sec.
100000115*2^450000-1 is not prime. LLR Res64: EF7DC18C6E7A2327 Time : 433.043 sec.
200000007*2^450000-1 is not prime. LLR Res64: FF761C6F58717618 Time : 433.037 sec.
500000079*2^450000-1 is not prime. LLR Res64: F9C08E06DC2A8673 Time : 433.091 sec.
1000000029*2^450000-1 is not prime. LLR Res64: 7B38B46F5DB67F3C Time : 433.080 sec.
2000000033*2^450000-1 is not prime. LLR Res64: 74C2495548F72BAF Time : 433.048 sec.
5000000003*2^450000-1 is not prime. LLR Res64: C91CF9303119CAD7 Time : 433.055 sec.
10000000035*2^450000-1 is not prime. LLR Res64: 13B4B699DACA308D Time : 433.195 sec.
20000000015*2^450000-1 is not prime. LLR Res64: 899F0B4FA6EC82F2 Time : 433.144 sec.
50000000043*2^450000-1 is not prime. LLR Res64: 978694633A8690C9 Time : 433.132 sec.
100000000037*2^450000-1 is not prime. LLR Res64: 03C9FB78A347AAD2 Time : 433.056 sec.
200000000007*2^450000-1 is not prime. LLR Res64: 0B9ADAC5C06FEA0C Time : 432.996 sec.
500000000027*2^450000-1 is not prime. LLR Res64: 379E82A9C791FDD6 Time : 433.079 sec.
1000000000019*2^450000-1 is not prime. LLR Res64: 56B8861600FCA256 Time : 433.164 sec.
2000000000019*2^450000-1 is not prime. LLR Res64: C0CD98A1E30CC8CA Time : 432.979 sec.
5000000000049*2^450000-1 is not prime. LLR Res64: 87B31BF96B27584D Time : 432.948 sec.
10000000000025*2^450000-1 is not prime. LLR Res64: F64ABB39E393274E Time : 433.044 sec.
20000000000019*2^450000-1 is not prime. LLR Res64: 9C6FDC753594EEF8 Time : 432.945 sec.
50000000000027*2^450000-1 is not prime. LLR Res64: A16D2400005B0C90 Time : 432.945 sec.
100000000000025*2^450000-1 is not prime. LLR Res64: 6805EF4EB4BDBE07 Time : 433.010 sec.
200000000000063*2^450000-1 is not prime. LLR Res64: DACEA6688FC6DB99 Time : 432.972 sec.
500000000000085*2^450000-1 is not prime. LLR Res64: 23B5078C0925A196 Time : 432.970 sec.
1000000000000005*2^450000-1 is not prime. LLR Res64: D8229F3D187C8E6B Time : 1178.190 sec.

Alan

Joined: 8 Oct 08
Posts: 88
ID: 30274
Credit: 19,927,031
RAC: 0

Message 17507 - Posted: 17 Aug 2009 | 16:57:18 UTC - in response to Message 17506.

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^666670-1 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^666670-1. 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?
____________

rebirther

Joined: 10 Aug 05
Posts: 783
ID: 85
Credit: 175,774,608
RAC: 0

Message 17509 - Posted: 17 Aug 2009 | 17:46:44 UTC

Iam missing a server status for SGPS?!
____________

Skligmund

Joined: 15 Sep 05
Posts: 230
ID: 765
Credit: 541,666,833
RAC: 0

Message 17615 - Posted: 21 Aug 2009 | 6:40:51 UTC - in response to Message 17509.

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

Just wondering
____________

Rytis
Volunteer moderator

Joined: 22 Jun 05
Posts: 2653
ID: 1
Credit: 89,719,258
RAC: 51,571

Message 17616 - Posted: 21 Aug 2009 | 7:08:18 UTC - in response to Message 17615.

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 :)
____________

Alexander

Joined: 27 Dec 08
Posts: 1
ID: 33479
Credit: 234,787
RAC: 0

Message 17620 - Posted: 21 Aug 2009 | 11:06:14 UTC - in response to Message 17616.

Rytis,

I see the stats on http://www.primegrid.com/stats_sgs_llr.php

Question on the totals.

In the stats-page 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

Lennart SM5YMT
Honorary cruncher

Joined: 7 May 07
Posts: 1125
ID: 7989
Credit: 694,692,344
RAC: 0

Message 17622 - Posted: 21 Aug 2009 | 12:33:37 UTC - in response to Message 17620.

Rytis,

I see the stats on http://www.primegrid.com/stats_sgs_llr.php

Question on the totals.

In the stats-page 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

rebirther

Joined: 10 Aug 05
Posts: 783
ID: 85
Credit: 175,774,608
RAC: 0

Message 17629 - Posted: 21 Aug 2009 | 21:14:05 UTC

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

Bruno

Joined: 6 Feb 09
Posts: 1
ID: 35196
Credit: 860,354
RAC: 0

Message 18116 - Posted: 21 Sep 2009 | 15:43:56 UTC - in response to Message 17507.

@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 prime-testing of (2^n-1).

Alan

Joined: 8 Oct 08
Posts: 88
ID: 30274
Credit: 19,927,031
RAC: 0

Message 18121 - Posted: 21 Sep 2009 | 21:48:53 UTC - in response to Message 18116.

cool:) Thanks Bruno!
____________

Tom Philippart

Joined: 3 May 09
Posts: 5
ID: 39517
Credit: 158,736
RAC: 0

Message 20844 - Posted: 6 Feb 2010 | 10:20:41 UTC

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

Kevin D Puckett
Volunteer tester

Joined: 4 Aug 09
Posts: 61
ID: 44488
Credit: 5,675,896
RAC: 0

Message 22527 - Posted: 14 Apr 2010 | 20:04:50 UTC
Last modified: 14 Apr 2010 | 20:07:41 UTC

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.

thommy3

Joined: 7 Jan 08
Posts: 42
ID: 17265
Credit: 268,651
RAC: 0

Message 22531 - Posted: 14 Apr 2010 | 20:44:14 UTC - in response to Message 22527.

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

Kevin D Puckett
Volunteer tester

Joined: 4 Aug 09
Posts: 61
ID: 44488
Credit: 5,675,896
RAC: 0

Message 22532 - Posted: 14 Apr 2010 | 22:18:59 UTC - in response to Message 22531.

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

Pooh Bear 27

Joined: 10 May 09
Posts: 798
ID: 39821
Credit: 1,750,252,825
RAC: 1,581,947

Message 25783 - Posted: 22 Aug 2010 | 18:14:40 UTC

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^666666-1

____________
My lucky numbers are 121*2^4553899-1 and 3756801695685*2^666669±1
My movie https://vimeo.com/manage/videos/502242

John
Honorary cruncher

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

Message 25790 - Posted: 22 Aug 2010 | 19:35:44 UTC - in response to Message 25783.

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^666666-1

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^n-1 client-side
if prime, then the following
k*2^n+1 client-side
k*2^(n-1)-1 server-side
k*2^(n+1)-1 server-side

Using your prime above, the client tested:

7555140078885*2^666666-1
7555140078885*2^666666+1

and the server tested

7555140078885*2^666665-1
7555140078885*2^666667-1

____________

Pooh Bear 27

Joined: 10 May 09
Posts: 798
ID: 39821
Credit: 1,750,252,825
RAC: 1,581,947

Message 25791 - Posted: 22 Aug 2010 | 19:42:02 UTC

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

John
Honorary cruncher

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

Message 25794 - Posted: 22 Aug 2010 | 20:21:07 UTC - in response to Message 25791.

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^n-1 and k*2^n+1 must both be prime. If they are, you'll be notified in an email. :)
____________

rebirther

Joined: 10 Aug 05
Posts: 783
ID: 85
Credit: 175,774,608
RAC: 0

Message 26230 - Posted: 9 Sep 2010 | 14:39:16 UTC

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

bdodson*

Joined: 13 Nov 09
Posts: 104
ID: 50079
Credit: 170,522,809
RAC: 0

Message 32982 - Posted: 16 Feb 2011 | 20:17:28 UTC - in response to Message 17454.

Sophie Germain Prime Search
...
We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-1, & k*2^(n+1)-1.

I was happy at the report of having a prime k*2^n-1 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^n-1 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 any-old
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*

toms83

Joined: 17 Dec 09
Posts: 238
ID: 51975
Credit: 433,804,879
RAC: 0

Message 35273 - Posted: 14 Apr 2011 | 12:49:04 UTC

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

ardo

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

Message 35280 - Posted: 14 Apr 2011 | 15:20:34 UTC

I'm running this on a Intel i7 2600k with HT. :-)

What info are you looking for?

toms83

Joined: 17 Dec 09
Posts: 238
ID: 51975
Credit: 433,804,879
RAC: 0

Message 35297 - Posted: 14 Apr 2011 | 20:00:36 UTC
Last modified: 14 Apr 2011 | 20:05:17 UTC

What clock, stock or OC?

ardo

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

Message 35307 - Posted: 15 Apr 2011 | 1:17:58 UTC - in response to Message 35297.

stock with temps around 60C

I have not attempted to oc yet; might do that this weekend.

toms83

Joined: 17 Dec 09
Posts: 238
ID: 51975
Credit: 433,804,879
RAC: 0

Message 35322 - Posted: 15 Apr 2011 | 13:24:02 UTC

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

JFS

Joined: 30 Mar 11
Posts: 1
ID: 92873
Credit: 234,760
RAC: 0

Message 36544 - Posted: 30 May 2011 | 8:33:55 UTC

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 6k-1
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

gazzyk1ns

Joined: 2 Aug 11
Posts: 1329
ID: 107047
Credit: 367,379,246
RAC: 0

Message 45749 - Posted: 27 Dec 2011 | 20:34:42 UTC - in response to Message 36544.

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

Same here.

DaveB

Joined: 20 Jun 09
Posts: 351
ID: 42198
Credit: 11,898,570
RAC: 0

Message 45757 - Posted: 27 Dec 2011 | 22:25:40 UTC - in response to Message 36544.

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 :=a-1
d:=a+1
Is_primec :=1
Is_primed :=1
open primes
while not EOF repeat
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 a-1 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

Honza
Volunteer moderator
Volunteer tester
Project scientist

Joined: 15 Aug 05
Posts: 1943
ID: 352
Credit: 5,939,210,715
RAC: 1,574,944

Message 45820 - Posted: 28 Dec 2011 | 20:54:17 UTC
Last modified: 28 Dec 2011 | 20:59:04 UTC

Among Newly reported primes there are some 333333. How comes?
65516468355*2^333333+1
65516468355*2^333333-1

This is also listed under Other significant primes.
____________
My stats

Usucapio Libertatis

Joined: 21 Apr 10
Posts: 748
ID: 59072
Credit: 709,813,695
RAC: 114,987

Message 45854 - Posted: 29 Dec 2011 | 11:36:07 UTC - in response to Message 45820.

Among Newly reported primes there are some 333333. How comes?
65516468355*2^333333+1
65516468355*2^333333-1

This is also listed under Other significant primes.

They seem to be reported within "Twin Prime Search" sub-project. Old primes with a new twin counterpart found? Or is it the server having "flashbacks"?

John
Honorary cruncher

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

Message 45891 - Posted: 29 Dec 2011 | 21:33:51 UTC - in response to Message 45854.

Among Newly reported primes there are some 333333. How comes?
65516468355*2^333333+1
65516468355*2^333333-1

This is also listed under Other significant primes.

They seem to be reported within "Twin Prime Search" sub-project. 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.
____________

Michael

Joined: 22 Oct 12
Posts: 3
ID: 176259
Credit: 0
RAC: 0

Message 58599 - Posted: 22 Oct 2012 | 13:28:10 UTC

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!

[DPC]Charley

Joined: 15 Apr 11
Posts: 803
ID: 95137
Credit: 94,993,523
RAC: 0

Message 58601 - Posted: 22 Oct 2012 | 16:19:17 UTC - in response to Message 58599.

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)

Michael

Joined: 22 Oct 12
Posts: 3
ID: 176259
Credit: 0
RAC: 0

Message 58611 - Posted: 23 Oct 2012 | 1:31:05 UTC - in response to Message 58601.
Last modified: 23 Oct 2012 | 1:32:48 UTC

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.

axn
Volunteer developer

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

Message 58614 - Posted: 23 Oct 2012 | 4:01:40 UTC - in response to Message 58599.

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^32611-1 9825 CK 1999 Sophie Germain (p) 62470 847067781*2^30790-1 9278 L4 2003 Sophie Germain (p) 62708 415365*2^30052-1 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^27182-1 8190 g206 2001 Sophie Germain (p) 63979 22717075*2^26000+1 7835 x11 2001 Sophie Germain (p) 64316 161193945*2^25253-1 7611 g137 2001 Sophie Germain (p) 64461 121063995*2^25094-1 7563 g120 2001 Sophie Germain (p) 64462 120136023*2^25094-1 7563 g120 2001 Sophie Germain (p) 64540 1051054917*2^25000-1 7535 g52 2000 Sophie Germain (p) 64651 626711007*2^24712-1 7448 g144 2001 Sophie Germain (p) 64652 885817959*2^24711-1 7448 g217 2001 Sophie Germain (p) 64664 1392082887*2^24680-1 7439 g137 2000 Sophie Germain (p) 64940 14516877*2^24176-1 7285 CK 1999 Sophie Germain (p) 65097 471631965*2^24000-1 7234 g298 2002 Sophie Germain (p) 65300 72021*2^23630-1 7119 g0 1998 Sophie Germain (p) 65352 325034895*2^23472-1 7075 g205 2000 Sophie Germain (p) 65353 1297743285*2^23470-1 7075 g205 2001 Sophie Germain (p) 65372 1186447755*2^23457-1 7071 g144 2000 Sophie Germain (p) 65386 613702635*2^23457-1 7071 g144 2000 Sophie Germain (p) 65954 1354921707*2^23005-1 6935 g141 2001 Sophie Germain (p) 65961 224420829*2^23003-1 6933 g141 2000 Sophie Germain (p) 65962 1579278645*2^23000-1 6933 g141 2000 Sophie Germain (p) 65963 255346125*2^23002-1 6933 g141 2000 Sophie Germain (p) 66932 1654523577*2^20304-1 6122 g137 2000 Sophie Germain (p) 67297 29553033*2^19990-1 6026 g141 1999 Sophie Germain (p) 67337 184748277*2^19912-1 6003 g206 2000 Sophie Germain (p) 67393 31467345*2^19761-1 5957 g141 1999 Sophie Germain (p) 67556 2375063906985*2^19380-1 5847 IJ 1996 Sophie Germain (p) 67687 276311*2^19003+1 5726 g23 1998 Sophie Germain (p) 68901 3382599*2^17075-1 5147 g27 1999 Sophie Germain (p) 68910 757321845*2^17051-1 5142 g141 2000 Sophie Germain (p) 68911 454332273*2^17051-1 5142 g141 2000 Sophie Germain (p) 68913 338234883*2^17050-1 5142 g141 2000 Sophie Germain (p) 68924 421907295*2^17029-1 5135 g141 2000 Sophie Germain (p) 69006 48859797*2^17000-1 5126 g141 1999 Sophie Germain (p) 69029 92305*2^16998+1 5122 g14 1998 Sophie Germain (p) 69177 8069496435*10^5072-1 5082 D 1995 Sophie Germain (p) 69956 "2^16383-2^16319-1+2^63*(floor(2^16254*Pi)+50814484)" 4932 c9 2003 ECPP, Sophie Germain (p) (**) 70052 470943129*2^16352-1 4932 IJ 1995 Sophie Germain (p) 70144 157324389*2^16352-1 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^4526-1 4536 D 1994 Sophie Germain (p) 70974 48101037*2^15005-1 4525 g141 2000 Sophie Germain (p) 70975 28671705*2^15005-1 4525 g141 2000 Sophie Germain (p) 70983 44941785*2^14999-1 4523 g141 2000 Sophie Germain (p) 71633 10211*2^13491+1 4066 g122 2000 Sophie Germain (p) 71818 1468358892*10^4003-1 4013 D 1994 Sophie Germain (p) 71930 1883535*2^13133-1 3960 g141 1999 Sophie Germain (p) 72021 224529135*2^12648-1 3816 g2 1998 Sophie Germain (p) 72204 "2^12287-2^12223-1+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^3529-1 3540 D 1994 Sophie Germain (p) 73717 27692175*2^10409-1 3141 g141 1999 Sophie Germain (p) 73799 22155*2^10164-1 3065 g35 1998 Sophie Germain (p) 73818 5546061*2^10113-1 3052 g155 1999 Sophie Germain (p) 74523 47013511545*10^2999-1 3010 D 1993 Sophie Germain (p) 74635 4627755*2^9878-1 2981 g2 1998 Sophie Germain (p) 74676 196949037*2^9752-1 2944 g141 1999 Sophie Germain (p) 75031 15489885*2^8906-1 2689 g27 1999 Sophie Germain (p) 75362 1746052308*10^2581-1 2591 D 1993 Sophie Germain (p) 76938 22714209*2^8087-1 2442 g14 1998 Sophie Germain (p) 77053 9303607*2^8004+1 2417 g2 1998 Sophie Germain (p) 77069 10497687*2^8000-1 2416 g210 2001 Sophie Germain (p) 77900 4837*2^7574+1 2284 DM 1996 Sophie Germain (p) 78229 2667027*2^7389-1 2231 CK 1999 Sophie Germain (p) 78877 8980569*2^7179-1 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^2110-1 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^6194-1 1874 g95 1998 Sophie Germain (p) 82608 713851138*10^1854+1 1863 D 1990 Sophie Germain (p) 82771 337047945*2^5999-1 1815 g210 2001 Sophie Germain (p) 82796 39051*2^6001-1 1812 K 1986 Sophie Germain (p) 84026 89687295*2^5001-1 1514 g38 1998 Sophie Germain (p) 84031 6238665*2^5004-1 1514 g14 1998 Sophie Germain (p) 84032 67621539*2^5000-1 1513 g158 1999 Sophie Germain (p) 84033 61022115*2^5000-1 1513 g158 1999 Sophie Germain (p) 84034 110266875*2^4999-1 1513 g158 1999 Sophie Germain (p) 84037 9769767*2^5001-1 1513 g158 1999 Sophie Germain (p) 84041 5004615*2^5001-1 1513 g158 1999 Sophie Germain (p) 84043 4133481*2^5001-1 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^1300-1 1307 CR 1997 Sophie Germain (p) 88877 296385*2^4251-1 1286 Z 1989 Sophie Germain (p) 89731 53373*2^4203-1 1270 Z 1989 Sophie Germain (p)

Michael

Joined: 22 Oct 12
Posts: 3
ID: 176259
Credit: 0
RAC: 0

Message 58615 - Posted: 23 Oct 2012 | 4:49:26 UTC - in response to Message 58614.

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^32611-1 9825 CK 1999 Sophie Germain (p) 62470 847067781*2^30790-1 9278 L4 2003 Sophie Germain (p) 62708 415365*2^30052-1 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^27182-1 8190 g206 2001 Sophie Germain (p) 63979 22717075*2^26000+1 7835 x11 2001 Sophie Germain (p) 64316 161193945*2^25253-1 7611 g137 2001 Sophie Germain (p) 64461 121063995*2^25094-1 7563 g120 2001 Sophie Germain (p) 64462 120136023*2^25094-1 7563 g120 2001 Sophie Germain (p) 64540 1051054917*2^25000-1 7535 g52 2000 Sophie Germain (p) 64651 626711007*2^24712-1 7448 g144 2001 Sophie Germain (p) 64652 885817959*2^24711-1 7448 g217 2001 Sophie Germain (p) 64664 1392082887*2^24680-1 7439 g137 2000 Sophie Germain (p) 64940 14516877*2^24176-1 7285 CK 1999 Sophie Germain (p) 65097 471631965*2^24000-1 7234 g298 2002 Sophie Germain (p) 65300 72021*2^23630-1 7119 g0 1998 Sophie Germain (p) 65352 325034895*2^23472-1 7075 g205 2000 Sophie Germain (p) 65353 1297743285*2^23470-1 7075 g205 2001 Sophie Germain (p) 65372 1186447755*2^23457-1 7071 g144 2000 Sophie Germain (p) 65386 613702635*2^23457-1 7071 g144 2000 Sophie Germain (p) 65954 1354921707*2^23005-1 6935 g141 2001 Sophie Germain (p) 65961 224420829*2^23003-1 6933 g141 2000 Sophie Germain (p) 65962 1579278645*2^23000-1 6933 g141 2000 Sophie Germain (p) 65963 255346125*2^23002-1 6933 g141 2000 Sophie Germain (p) 66932 1654523577*2^20304-1 6122 g137 2000 Sophie Germain (p) 67297 29553033*2^19990-1 6026 g141 1999 Sophie Germain (p) 67337 184748277*2^19912-1 6003 g206 2000 Sophie Germain (p) 67393 31467345*2^19761-1 5957 g141 1999 Sophie Germain (p) 67556 2375063906985*2^19380-1 5847 IJ 1996 Sophie Germain (p) 67687 276311*2^19003+1 5726 g23 1998 Sophie Germain (p) 68901 3382599*2^17075-1 5147 g27 1999 Sophie Germain (p) 68910 757321845*2^17051-1 5142 g141 2000 Sophie Germain (p) 68911 454332273*2^17051-1 5142 g141 2000 Sophie Germain (p) 68913 338234883*2^17050-1 5142 g141 2000 Sophie Germain (p) 68924 421907295*2^17029-1 5135 g141 2000 Sophie Germain (p) 69006 48859797*2^17000-1 5126 g141 1999 Sophie Germain (p) 69029 92305*2^16998+1 5122 g14 1998 Sophie Germain (p) 69177 8069496435*10^5072-1 5082 D 1995 Sophie Germain (p) 69956 "2^16383-2^16319-1+2^63*(floor(2^16254*Pi)+50814484)" 4932 c9 2003 ECPP, Sophie Germain (p) (**) 70052 470943129*2^16352-1 4932 IJ 1995 Sophie Germain (p) 70144 157324389*2^16352-1 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^4526-1 4536 D 1994 Sophie Germain (p) 70974 48101037*2^15005-1 4525 g141 2000 Sophie Germain (p) 70975 28671705*2^15005-1 4525 g141 2000 Sophie Germain (p) 70983 44941785*2^14999-1 4523 g141 2000 Sophie Germain (p) 71633 10211*2^13491+1 4066 g122 2000 Sophie Germain (p) 71818 1468358892*10^4003-1 4013 D 1994 Sophie Germain (p) 71930 1883535*2^13133-1 3960 g141 1999 Sophie Germain (p) 72021 224529135*2^12648-1 3816 g2 1998 Sophie Germain (p) 72204 "2^12287-2^12223-1+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^3529-1 3540 D 1994 Sophie Germain (p) 73717 27692175*2^10409-1 3141 g141 1999 Sophie Germain (p) 73799 22155*2^10164-1 3065 g35 1998 Sophie Germain (p) 73818 5546061*2^10113-1 3052 g155 1999 Sophie Germain (p) 74523 47013511545*10^2999-1 3010 D 1993 Sophie Germain (p) 74635 4627755*2^9878-1 2981 g2 1998 Sophie Germain (p) 74676 196949037*2^9752-1 2944 g141 1999 Sophie Germain (p) 75031 15489885*2^8906-1 2689 g27 1999 Sophie Germain (p) 75362 1746052308*10^2581-1 2591 D 1993 Sophie Germain (p) 76938 22714209*2^8087-1 2442 g14 1998 Sophie Germain (p) 77053 9303607*2^8004+1 2417 g2 1998 Sophie Germain (p) 77069 10497687*2^8000-1 2416 g210 2001 Sophie Germain (p) 77900 4837*2^7574+1 2284 DM 1996 Sophie Germain (p) 78229 2667027*2^7389-1 2231 CK 1999 Sophie Germain (p) 78877 8980569*2^7179-1 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^2110-1 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^6194-1 1874 g95 1998 Sophie Germain (p) 82608 713851138*10^1854+1 1863 D 1990 Sophie Germain (p) 82771 337047945*2^5999-1 1815 g210 2001 Sophie Germain (p) 82796 39051*2^6001-1 1812 K 1986 Sophie Germain (p) 84026 89687295*2^5001-1 1514 g38 1998 Sophie Germain (p) 84031 6238665*2^5004-1 1514 g14 1998 Sophie Germain (p) 84032 67621539*2^5000-1 1513 g158 1999 Sophie Germain (p) 84033 61022115*2^5000-1 1513 g158 1999 Sophie Germain (p) 84034 110266875*2^4999-1 1513 g158 1999 Sophie Germain (p) 84037 9769767*2^5001-1 1513 g158 1999 Sophie Germain (p) 84041 5004615*2^5001-1 1513 g158 1999 Sophie Germain (p) 84043 4133481*2^5001-1 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^1300-1 1307 CR 1997 Sophie Germain (p) 88877 296385*2^4251-1 1286 Z 1989 Sophie Germain (p) 89731 53373*2^4203-1 1270 Z 1989 Sophie Germain (p)

Wow. Excellent. More than I expected. Thank you.

x3mEn

Joined: 21 Jul 10
Posts: 353
ID: 64131
Credit: 63,706,570
RAC: 0

Message 70693 - Posted: 6 Nov 2013 | 20:46:32 UTC - in response to Message 17487.
Last modified: 6 Nov 2013 | 20:54:01 UTC

We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1 and if prime you will also search k*2^n+1

We will search all primes externally on PG server for k*2^(n-1)-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^n-1 is composite?
Do we check k*2^(n+1)+1 primality if k*2^n+1 is prime?
____________

x3mEn

Joined: 21 Jul 10
Posts: 353
ID: 64131
Credit: 63,706,570
RAC: 0

Message 70695 - Posted: 6 Nov 2013 | 21:43:13 UTC

I've already found that the largest known primes of this form is
648309*2^148311+1 - Cunningham chain 2nd kind (2p-1)
648309*2^148310+1 - Cunningham chain 2nd kind (p)

44652 and 43058 digits only...
____________

JimB
Honorary cruncher

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

Message 70736 - Posted: 8 Nov 2013 | 13:33:56 UTC - in response to Message 70693.

John wrote:
You will check k*2^n-1 and if prime you will also search k*2^n+1
We will search all primes externally on PG server for k*2^(n-1)-1, & k*2^(n+1)-1

x3mEn wrote:
Do we check k*2^n+1 primality even if k*2^n-1 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^n-1 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^(n-1)-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^1290000-1 is prime! Time : 2542.378 sec.
1054899866865*2^1290000+1 is not prime. Proth RES64: B0CF6CED1998C23F Time : 2498.885 sec.
1054899866865*2^1289999-1 is not prime. LLR Res64: 32BFA46352FDCC7C Time : 2311.508 sec.
1054899866865*2^1290001-1 is not prime. LLR Res64: 21D0038F7A5148BA Time : 2277.467 sec.

x3mEn

Joined: 21 Jul 10
Posts: 353
ID: 64131
Credit: 63,706,570
RAC: 0

Message 70763 - Posted: 9 Nov 2013 | 15:48:58 UTC
Last modified: 9 Nov 2013 | 16:09:30 UTC

Okay, why the pair of primes (p; 2p+1) has its own name - Sophie Germain primes,
but the pair of primes (p; 2p-1) 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; 2p-1) 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,
2p-1 is the Proth number too: 2p-1 = k*2^(n+1)+1

I guess the pair of primes
648309*2^148311+1 - Cunningham chain 2nd kind (2p-1)
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?
____________

x3mEn

Joined: 21 Jul 10
Posts: 353
ID: 64131
Credit: 63,706,570
RAC: 0

Message 70764 - Posted: 9 Nov 2013 | 16:03:55 UTC - in response to Message 70736.

JimB wrote:

For every SGS prime, no matter whether the +1 form is prime or not we test both the k*2^(n-1)-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^1290000-1 is prime! Time : 2542.378 sec.
1054899866865*2^1290000+1 is not prime. Proth RES64: B0CF6CED1998C23F Time : 2498.885 sec.
1054899866865*2^1289999-1 is not prime. LLR Res64: 32BFA46352FDCC7C Time : 2311.508 sec.
1054899866865*2^1290001-1 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^n-1 is prime.
So k*2^(n+1)+1 will be checked only when/if we will find Twin primes, k*2^n-1 first and k*2^n+1 second, it happend in PrimeGrid only twice as I know.
____________

composite
Volunteer tester

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

Message 81540 - Posted: 22 Dec 2014 | 3:37:17 UTC - in response to Message 70764.

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^n-1 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 n-wise 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^n-1 can be be ignored where it was already tested by SGS, or it could kick off an early SGS WU for k*2^n-1 not already tested.

Volunteer moderator
Volunteer tester
Project scientist

Joined: 5 Feb 08
Posts: 1214
ID: 18646
Credit: 851,940,027
RAC: 111,695

Message 88500 - Posted: 28 Sep 2015 | 16:55:06 UTC

no available SGS llr tasks

as_of_now wrote:
3219 Sophie Germain Prime Search (LLR) 0 / 0

is this shortage planned for any reason?
____________
my current lucky number: 113856050^65536 + 1
PSA-PRPNet-Stats-URL: http://u-g-f.de/PRPNet/

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 88502 - Posted: 28 Sep 2015 | 17:54:34 UTC - in response to Message 88500.
Last modified: 28 Sep 2015 | 17:55:49 UTC

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 75898524288+1

Volunteer moderator
Volunteer tester
Project scientist

Joined: 5 Feb 08
Posts: 1214
ID: 18646
Credit: 851,940,027
RAC: 111,695

Message 88503 - Posted: 28 Sep 2015 | 17:58:19 UTC - in response to Message 88502.

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.

thanks a lot (helping me on my run to the gold badge)
thought, it could been in relation with some wrapper- or app-updates you let the work run out
____________
my current lucky number: 113856050^65536 + 1
PSA-PRPNet-Stats-URL: http://u-g-f.de/PRPNet/

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 92540 - Posted: 1 Mar 2016 | 9:58:17 UTC - in response to Message 17454.

We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1, k*2^n+1, k*2^(n-1)-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^(n-1)-1 has such a small factor (5 is small!)? See the above description of a "quad sieve".

/JeppeSN

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 783
ID: 164101
Credit: 305,458,910
RAC: 4,919

Message 92541 - Posted: 1 Mar 2016 | 10:47:13 UTC - in response to Message 92540.

2618163402417*2^1289999 - 1 has factor 5

[...] how is it possible that k*2^(n-1)-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*3-1 = 5

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 92550 - Posted: 1 Mar 2016 | 17:32:12 UTC - in response to Message 92541.

2618163402417*2^1289999 - 1 has factor 5

[...] how is it possible that k*2^(n-1)-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*3-1 = 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^n-1, k*2^n+1, k*2^(n-1)-1, & k*2^(n+1)-1 did not have any small prime divisors.", however in our case the second-last 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, (p-1)/2, and 2p+1. Since (p-1)/2 has a super-small factor (5), why did the sieve not remove p?

/JeppeSN

axn
Volunteer developer

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

Message 92551 - Posted: 1 Mar 2016 | 17:37:33 UTC
Last modified: 1 Mar 2016 | 17:43:03 UTC

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 k-ranges, and then the survivors would've been combined into a single file. It could be that only some k-ranges weren't quad sieved.

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 92552 - Posted: 1 Mar 2016 | 17:52:27 UTC

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 n-1 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 n-1 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, small-factor removal ARE very common in the server-side tests, and it makes far more sense for the sieve to work as an "OR" rather than an "AND".)

____________
My lucky number is 75898524288+1

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 92554 - Posted: 1 Mar 2016 | 18:28:48 UTC - in response to Message 92552.

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

serge

Joined: 21 Jun 12
Posts: 112
ID: 144858
Credit: 286,821,089
RAC: 0

Message 92559 - Posted: 1 Mar 2016 | 22:12:00 UTC

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(i-1),c(i+4); if one of them is prime use the last chance, and if both are prime, one already has a CC-6 and still a minuscule chance of CC-7 and CC-8.

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 92564 - Posted: 1 Mar 2016 | 23:03:45 UTC - in response to Message 92559.

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(i-1),c(i+4); if one of them is prime use the last chance, and if both are prime, one already has a CC-6 and still a minuscule chance of CC-7 and CC-8.

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

serge

Joined: 21 Jun 12
Posts: 112
ID: 144858
Credit: 286,821,089
RAC: 0

Message 92565 - Posted: 1 Mar 2016 | 23:32:52 UTC - in response to Message 92564.
Last modified: 1 Mar 2016 | 23:34:38 UTC

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/sparse-array 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 multi-sieve principles, and (I quote) "The decision criteria and discussion is more than can be easily typed into an introductory web page."

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 92566 - Posted: 2 Mar 2016 | 0:17:07 UTC - in response to Message 92564.

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 75898524288+1

axn
Volunteer developer

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

Message 92567 - Posted: 2 Mar 2016 | 3:15:23 UTC - in response to Message 92564.

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

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 92572 - Posted: 2 Mar 2016 | 12:47:24 UTC - in response to Message 92567.

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

axn
Volunteer developer

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

Message 92574 - Posted: 2 Mar 2016 | 13:16:58 UTC - in response to Message 92572.

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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 92575 - Posted: 2 Mar 2016 | 13:17:17 UTC

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 re-evaluate staying at 1290000 at that time.

There's about 10 years worth of work remaining at 1290000.
____________
My lucky number is 75898524288+1

axn
Volunteer developer

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

Message 92577 - Posted: 2 Mar 2016 | 13:24:06 UTC - in response to Message 92575.

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 re-evaluate 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).

Joined: 25 Aug 11
Posts: 61
ID: 109842
Credit: 110,654,752
RAC: 0

Message 98587 - Posted: 7 Sep 2016 | 0:10:34 UTC

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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 98589 - Posted: 7 Sep 2016 | 0:57:58 UTC - in response to Message 98587.

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 75898524288+1

Christian Keimer

Joined: 3 Jan 16
Posts: 9
ID: 434905
Credit: 14,944,072
RAC: 29

Message 98995 - Posted: 21 Sep 2016 | 12:39:58 UTC
Last modified: 21 Sep 2016 | 12:41:59 UTC

Hi,

is this the only project to search for twin-primes or are there other projects on PrimeGrid that specifically look for them?

Thanks and cheers,

Chris

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 98997 - Posted: 21 Sep 2016 | 14:01:09 UTC - in response to Message 98995.

Hi,

is this the only project to search for twin-primes 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 75898524288+1

Christian Keimer

Joined: 3 Jan 16
Posts: 9
ID: 434905
Credit: 14,944,072
RAC: 29

Message 99002 - Posted: 21 Sep 2016 | 14:41:05 UTC - in response to Message 98997.

Thank you Michael for the answer.

That is what I figured.

Thanks,

Chris

Joined: 25 Aug 11
Posts: 61
ID: 109842
Credit: 110,654,752
RAC: 0

Message 99184 - Posted: 27 Sep 2016 | 2:28:47 UTC - in response to Message 98587.

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

puh32

Joined: 2 Feb 09
Posts: 55
ID: 34980
Credit: 299,134,975
RAC: 34,145

Message 101864 - Posted: 7 Dec 2016 | 8:45:59 UTC - in response to Message 99184.

Out of curiosity:

All new (e.g.,) GFN-15 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.

Crun-chi
Volunteer tester

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

Message 101865 - Posted: 7 Dec 2016 | 11:07:58 UTC - in response to Message 101864.

Out of curiosity:

All new (e.g.,) GFN-15 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^1290000-1 (meteor); 3175204825947*2^1290000-1 (puh32); 3170617556925*2^1290000-1 (masumi hamada);
____________
92*10^1439761-1 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
2022202116^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

puh32

Joined: 2 Feb 09
Posts: 55
ID: 34980
Credit: 299,134,975
RAC: 34,145

Message 101868 - Posted: 7 Dec 2016 | 12:01:34 UTC - in response to Message 101865.

>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.)

Crun-chi
Volunteer tester

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

Message 101870 - Posted: 7 Dec 2016 | 12:39:16 UTC - in response to Message 101868.

>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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
2022202116^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 101881 - Posted: 7 Dec 2016 | 14:59:34 UTC - in response to Message 101864.

Out of curiosity:

All new (e.g.,) GFN-15 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 75898524288+1

puh32

Joined: 2 Feb 09
Posts: 55
ID: 34980
Credit: 299,134,975
RAC: 34,145

Message 101926 - Posted: 8 Dec 2016 | 17:13:39 UTC - in response to Message 101881.

OK, thanks guys, good to know.

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 104169 - Posted: 26 Jan 2017 | 21:07:06 UTC - in response to Message 17454.

Sophie Germain Prime Search
...
We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1, k*2^n+1, k*2^(n-1)-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?

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104194 - Posted: 27 Jan 2017 | 18:34:26 UTC - in response to Message 104169.

Sophie Germain Prime Search
...
We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1, k*2^n+1, k*2^(n-1)-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^1290000-1

which had clearly not been removed by the sieve. The three related numbers were:

x = 2618163402417*2^1290000+1 y = 2618163402417*2^1289999-1 z = 2618163402417*2^1290001-1

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

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104196 - Posted: 27 Jan 2017 | 18:50:04 UTC - in response to Message 104194.

Similarly, the last time a twin prime was found, it started from the number:

a = 2996863034895*2^1290000-1

which had clearly not been removed by the sieve. The three related numbers were:

x = 2996863034895*2^1290000+1 y = 2996863034895*2^1289999-1 z = 2996863034895*2^1290001-1

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

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104202 - Posted: 27 Jan 2017 | 20:36:06 UTC - in response to Message 104196.
Last modified: 27 Jan 2017 | 20:45:02 UTC

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 comma-separated 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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104203 - Posted: 27 Jan 2017 | 20:45:21 UTC

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 75898524288+1

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104204 - Posted: 27 Jan 2017 | 20:49:16 UTC - in response to Message 104169.

Sophie Germain Prime Search
...
We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1, k*2^n+1, k*2^(n-1)-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?

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 75898524288+1

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104205 - Posted: 27 Jan 2017 | 20:53:20 UTC - in response to Message 104203.

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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104206 - Posted: 27 Jan 2017 | 20:54:51 UTC - in response to Message 104205.

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 75898524288+1

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104207 - Posted: 27 Jan 2017 | 21:03:32 UTC - in response to Message 104205.

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 '%1289999-1 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 '%1289999-1 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 '%1289999-1 is not prime%'; +----------+ | count(*) | +----------+ | 882 | +----------+ 1 row in set (0.02 sec)

____________
My lucky number is 75898524288+1

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104209 - Posted: 27 Jan 2017 | 21:29:43 UTC - in response to Message 104207.

How often do '%1290000+1' and '%1290001-1' have small factors, in comparison?

/JeppeSN

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104224 - Posted: 28 Jan 2017 | 1:24:41 UTC - in response to Message 104209.

How often do '%1290000+1' and '%1290001-1' have small factors, in comparison?

/JeppeSN

Well, that's certainly an interesting question.

The answer is "None".

____________
My lucky number is 75898524288+1

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104237 - Posted: 28 Jan 2017 | 11:26:55 UTC - in response to Message 104224.

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

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104239 - Posted: 28 Jan 2017 | 12:02:30 UTC

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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104247 - Posted: 28 Jan 2017 | 14:51:19 UTC - in response to Message 104237.
Last modified: 28 Jan 2017 | 14:53:15 UTC

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 75898524288+1

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104261 - Posted: 28 Jan 2017 | 17:06:58 UTC - in response to Message 104247.

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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 104267 - Posted: 28 Jan 2017 | 18:45:13 UTC - in response to Message 104261.

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 75898524288+1

axn
Volunteer developer

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

Message 104299 - Posted: 29 Jan 2017 | 6:33:32 UTC - in response to Message 92567.

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 104307 - Posted: 29 Jan 2017 | 11:45:34 UTC - in response to Message 104299.

[...]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

River~~

Joined: 17 Mar 07
Posts: 342
ID: 6533
Credit: 15,792,075
RAC: 0

Message 104408 - Posted: 31 Jan 2017 | 16:34:18 UTC - in response to Message 104204.
Last modified: 31 Jan 2017 | 16:43:08 UTC

Sophie Germain Prime Search
...
We'll be searching the form k*2^n-1. If it is prime, then we'll check k*2^n+1, k*2^(n-1)-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^n-1, k*2^n+1, k*2^(n-1)-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~~

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.

Honza
Volunteer moderator
Volunteer tester
Project scientist

Joined: 15 Aug 05
Posts: 1943
ID: 352
Credit: 5,939,210,715
RAC: 1,574,944

Message 112768 - Posted: 29 Dec 2017 | 22:56:51 UTC
Last modified: 29 Dec 2017 | 22:59:33 UTC

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

Luigi R.

Joined: 11 Feb 14
Posts: 179
ID: 297455
Credit: 73,706,723
RAC: 21,794

Message 113619 - Posted: 20 Jan 2018 | 16:25:50 UTC - in response to Message 113313.
Last modified: 20 Jan 2018 | 16:29:45 UTC

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^1290000-1 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 Brown
Volunteer moderator
Volunteer tester
Project scientist

Joined: 17 Oct 05
Posts: 2359
ID: 1178
Credit: 17,586,559,455
RAC: 5,278,986

Message 113620 - Posted: 20 Jan 2018 | 16:40:26 UTC - in response to Message 113619.
Last modified: 20 Jan 2018 | 16:41:21 UTC

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^1290000-1 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^1290000-1 for example. An SG pair has the form 2618163402417*2^1290000-1, 2618163402417*2^1290001-1 for example.

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 113623 - Posted: 20 Jan 2018 | 16:53:41 UTC - in response to Message 113619.
Last modified: 20 Jan 2018 | 16:56:39 UTC

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^1290000-1 is prime or sometimes when another condition is true?

Always.

When k·2^1290000-1 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^1289999-1 and k·2^1290001-1.

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^n-1, a twin changes the '-1' to '+1' whereas a Sophie Germain pair adds or subtracts 1 to or from 'n'.
____________
My lucky number is 75898524288+1

Luigi R.

Joined: 11 Feb 14
Posts: 179
ID: 297455
Credit: 73,706,723
RAC: 21,794

Message 113624 - Posted: 20 Jan 2018 | 17:52:39 UTC
Last modified: 20 Jan 2018 | 17:57:39 UTC

So let me understand (about pairs)...

Scott discovered a Sophie Germain prime (=2618163402417*2^1290000-1) on 2016-02-29 05:39:14 UTC.
The server did the test of 2p+1 (=2618163402417*2^1290001-1) 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 (p-1)/2 (=2618163402417*2^1289999-1) was done too, but it was not prime.

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 127036 - Posted: 18 Feb 2019 | 18:11:16 UTC - in response to Message 113623.

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^1290000-1 is prime or sometimes when another condition is true?

Always.

When k·2^1290000-1 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^1289999-1 and k·2^1290001-1.

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^n-1, 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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 127076 - Posted: 19 Feb 2019 | 0:06:20 UTC - in response to Message 127036.

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 75898524288+1

vaughan

Joined: 11 Aug 05
Posts: 317
ID: 224
Credit: 10,140,588,470
RAC: 4,366,102

Message 127169 - Posted: 20 Feb 2019 | 6:02:31 UTC

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

dthonon
Volunteer tester

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

Message 127175 - Posted: 20 Feb 2019 | 8:55:18 UTC - in response to Message 127169.
Last modified: 20 Feb 2019 | 8:55:46 UTC

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

SGS climbed from 388,341 to 388,342 digits on 2015-05-30, nearly 4 years ago.
GFN-16 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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 127178 - Posted: 20 Feb 2019 | 10:37:50 UTC - in response to Message 127169.

Will the Sophie Germain primes be too small forever to reach the Top 5000 list or would they catch-up 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 re-sieve 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 75898524288+1

Chooka

Joined: 15 May 18
Posts: 290
ID: 1014486
Credit: 746,910,641
RAC: 690,336

Message 131081 - Posted: 14 Jul 2019 | 5:30:07 UTC

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?

____________

Слава Україні!

Lumiukko
Volunteer tester

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

Message 131082 - Posted: 14 Jul 2019 | 5:56:24 UTC - in response to Message 131081.

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?

The application name for SGS-project 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

Chooka

Joined: 15 May 18
Posts: 290
ID: 1014486
Credit: 746,910,641
RAC: 690,336

Message 131083 - Posted: 14 Jul 2019 | 6:00:52 UTC - in response to Message 131082.

Ohhhh ok. I didn't know that!
I'll give that a go. Thank you!
____________

Слава Україні!

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 131085 - Posted: 14 Jul 2019 | 10:09:51 UTC - in response to Message 131082.

The application name for SGS-project is not llrSGS, it is llrTPS.

Yeah, it honors the not-so-famous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN

robish
Volunteer moderator
Volunteer tester

Joined: 7 Jan 12
Posts: 2182
ID: 126266
Credit: 7,179,596,591
RAC: 1,612,681

Message 131086 - Posted: 14 Jul 2019 | 10:12:38 UTC - in response to Message 131085.

The application name for SGS-project is not llrSGS, it is llrTPS.

Yeah, it honors the not-so-famous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN

🤣
____________
My lucky numbers 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26

Dave

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

Message 131087 - Posted: 14 Jul 2019 | 10:59:25 UTC - in response to Message 131085.

The application name for SGS-project is not llrSGS, it is llrTPS.

Yeah, it honors the not-so-famous mathematician Tophie Permain who did research in Swin Grimes. /JeppeSN

Omg that's my sort of joke that is...

Crun-chi
Volunteer tester

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

Message 131088 - Posted: 14 Jul 2019 | 11:01:31 UTC - in response to Message 131083.

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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
2022202116^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Eudy Silva

Joined: 26 Aug 17
Posts: 2051
ID: 918937
Credit: 575,197,085
RAC: 273,734

Message 131089 - Posted: 14 Jul 2019 | 14:49:13 UTC - in response to Message 131085.

JeppeSN wrote:
...
Yeah, it honors the not-so-famous 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.

Chooka

Joined: 15 May 18
Posts: 290
ID: 1014486
Credit: 746,910,641
RAC: 690,336

Message 131148 - Posted: 16 Jul 2019 | 7:23:16 UTC - in response to Message 131088.
Last modified: 16 Jul 2019 | 7:34:58 UTC

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.
____________

Слава Україні!

Crun-chi
Volunteer tester

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

Message 131153 - Posted: 16 Jul 2019 | 18:51:28 UTC - in response to Message 131148.

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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
2022202116^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Chooka

Joined: 15 May 18
Posts: 290
ID: 1014486
Credit: 746,910,641
RAC: 690,336

Message 131190 - Posted: 17 Jul 2019 | 18:46:50 UTC - in response to Message 131153.
Last modified: 17 Jul 2019 | 18:54:27 UTC

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.
____________

Слава Україні!

Crun-chi
Volunteer tester

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

Message 131192 - Posted: 17 Jul 2019 | 19:48:50 UTC - in response to Message 131190.

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 NEAR-REPDIGIT PRIME :) :) :)
4 * 650^498101-1 CRUS PRIME
2022202116^131072+1 GENERALIZED FERMAT
Proud member of team Aggie The Pew. Go Aggie!

Dave

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

Message 131197 - Posted: 17 Jul 2019 | 21:01:50 UTC - in response to Message 131192.

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.

HighTech67

Joined: 5 Sep 05
Posts: 48
ID: 682
Credit: 140,769,591
RAC: 10,254

Message 131212 - Posted: 18 Jul 2019 | 7:38:27 UTC - in response to Message 131197.

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

Moytra

Joined: 30 Jul 21
Posts: 2
ID: 1399457
Credit: 2,808
RAC: 0

Message 151325 - Posted: 30 Aug 2021 | 13:01:54 UTC
Last modified: 30 Aug 2021 | 13:11:25 UTC

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^1290000-1
then what it means? It means that p ( 6438607821915*2^1290000-1 ) is prime and 2*p + 1 ( 6438607821915*2^1290001-1 ) (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^(n-1)-1, 2^n-1, 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 Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 210
ID: 1108183
Credit: 13,084,497
RAC: 6,049

Message 151326 - Posted: 30 Aug 2021 | 15:54:33 UTC - in response to Message 151325.
Last modified: 30 Aug 2021 | 15:55:00 UTC

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^1290000-1
then what it means? It means that p ( 6438607821915*2^1290000-1 ) is prime and 2*p + 1 ( 6438607821915*2^1290001-1 ) (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^(n-1)-1, 2^n-1, 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^(n-1)-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.

Moytra

Joined: 30 Jul 21
Posts: 2
ID: 1399457
Credit: 2,808
RAC: 0

Message 151364 - Posted: 3 Sep 2021 | 16:17:04 UTC - in response to Message 151326.
Last modified: 3 Sep 2021 | 16:22:06 UTC

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^1290000-1 and 2618163402417*2^1290001-1 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 2016-2021 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 K-range searched incrementally? So 2618163402417 is the smallest K such that K * 2^1290000-1 is Sophie Germain? One can be sure that this is the smallest K?

JeppeSN

Joined: 5 Apr 14
Posts: 1786
ID: 306875
Credit: 48,202,262
RAC: 12,999

Message 151365 - Posted: 3 Sep 2021 | 19:40:58 UTC - in response to Message 151364.

Does it mean that both 2618163402417*2^1290000-1 and 2618163402417*2^1290001-1 are prime? So I have to do +1 to 1 290 000 in this case to obtain second prime?

PrimeGrid search (has different links)
Sophie Germain Top Twenty
/JeppeSN

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 210
ID: 1108183
Credit: 13,084,497
RAC: 6,049

Message 151372 - Posted: 4 Sep 2021 | 7:04:56 UTC - in response to Message 151364.

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^1290000-1 and 2618163402417*2^1290001-1 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 2016-2021 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 K-range searched incrementally? So 2618163402417 is the smallest K such that K * 2^1290000-1 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 (2007-2009, 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 that--it 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.

arakelov

Joined: 3 Jun 21
Posts: 21
ID: 1375045
Credit: 71,113,174
RAC: 15,469

Message 155246 - Posted: 28 Apr 2022 | 13:51:05 UTC - in response to Message 151372.

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 Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 210
ID: 1108183
Credit: 13,084,497
RAC: 6,049

Message 155250 - Posted: 28 Apr 2022 | 18:23:03 UTC - in response to Message 155246.

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 Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13899
ID: 53948
Credit: 384,585,761
RAC: 132,106

Message 155254 - Posted: 29 Apr 2022 | 4:47:26 UTC

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 75898524288+1

arakelov

Joined: 3 Jun 21
Posts: 21
ID: 1375045
Credit: 71,113,174
RAC: 15,469

Message 155255 - Posted: 29 Apr 2022 | 5:12:27 UTC - in response to Message 155254.

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

Best wishes.

Message boards : Sophie Germain Prime Search : Sophie Germain Prime Search