## Other

drummers-lowrise

Message boards : Sophie Germain Prime Search : Sophie Germain MEGA?

Author Message
Allen Paschke

Joined: 12 Nov 15
Posts: 29
ID: 428118
Credit: 41,323,601
RAC: 26,609

Message 157712 - Posted: 6 Nov 2022 | 19:53:43 UTC

Currently, there are no sub-projects searching for prime numbers in the 600,000 - 900,000 digit range.

From 2010 - 2012, Sophie Germain analyzed k*2^666666-1 - k*2^666670-1, and prime numbers with 200,700 digits were found. From 2012 to present, Sophie Germain is analyzing k*2^1290000-1, and prime numbers with 388,342 digits are being found.

Is a Sophie Germain MEGA possible with an exponent that would find prime numbers in the 600,000 - 800,000 digit range? They would be T5K primes.

There have been 3 different PPS' (PPS, PPSE and MEGA) and 2 different GFN-17's (GFN-17 and GFN-17 MEGA). If it is mathematically possible, why not a SGS MEGA?

If not a Sophie Germain MEGA, is there another project that would find prime numbers in the 600,000- 900,000 range?

Dave

Joined: 13 Feb 12
Posts: 3145
ID: 130544
Credit: 2,211,016,949
RAC: 142,531

Message 157713 - Posted: 6 Nov 2022 | 20:14:39 UTC - in response to Message 157712.

Is a Sophie Germain MEGA possible with an exponent that would find prime numbers in the 600,000 - 800,000 digit range?

They're not megaprimes so you can't call it "mega".

Allen Paschke

Joined: 12 Nov 15
Posts: 29
ID: 428118
Credit: 41,323,601
RAC: 26,609

Message 157717 - Posted: 6 Nov 2022 | 22:22:41 UTC - in response to Message 157713.

You are correct, MEGA is for over 1 million digits. How about SGS Extended or SGS Larger for searching for prime numbers in the 600,000 - 900,000 digit range, if my idea makes sense.

JeppeSN

Joined: 5 Apr 14
Posts: 1780
ID: 306875
Credit: 48,096,366
RAC: 14,202

Message 157720 - Posted: 7 Nov 2022 | 9:25:44 UTC

There is nothing technically stopping a Sophie-Germain and twin search from working on numbers sufficiently large to be eligible for the Top 5000. As you may know, when we started on exponent 1'290'000, these numbers were large enough to make the Top 5000.

While we have found thousands of primes with the SGS project, we have found very few that actually had the required companion prime to make them Sophie-Germain or twin. Of course, this would be even rarer if we moved to higher numbers. (We can improve the rate a bit by using a true quad sieve, including "safe primes" (whose companions are then Sophie-Germain) in the sieving.)

As far as I have heard, the plan is to complete the current sieve file for exponent 1'290'000, and then consider what would be the best Sophie-Germain project after that.

In any case, some sieving must be done first.

Note that if we started near 800'000 digits today, as you suggest, and used the same "system" where the exponent is fixed, then it would not take many years before 800'000 digits would no longer be big enough (just like it happened for 388'342 digits).

/JeppeSN

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 776
ID: 164101
Credit: 305,410,351
RAC: 3,917

Message 157721 - Posted: 7 Nov 2022 | 9:59:34 UTC

A mega-twin or mega-SG is a giant step (but feasible).
Today about 30,000 candidates are tested for one megaprime.
A twin-SG combined project searches for primes in the quadruples (k*2^{n-1} - 1, k*2^n - 1, k*2{n+1} - 1, k*2^n + 1). Then on average, 10,000 megaprimes are needed to find one twin or one SG.
This year, the MEGA project will find about 200 megaprimes.
The number of known megaprimes per year is about 1.4^(Y-2000) where Y is the year. This simple law is amazingly accurate:

Year Actual Estimate 2006 10 8 2007 13 11 2008 21 15 2009 26 21 2010 30 29 2011 41 40 2012 60 57 2013 73 79 2014 118 111 2015 147 156 2016 223 218 2017 310 305 2018 426 427 2019 600 598 2020 833 837 2021 1188 1171 2022 ≥ 1617 1640
That 's about 20,000/30,000 megaprimes in 2030. Then if the MEGA project is converted to a twin/SG search and find one third of megaprimes, it can find one solution around 2030.
But because the law 1.4^(Y-2000) is exponential, we can start the project in 2025. But at that time, the 5000th largest known prime will have more than one million digits!

Dave

Joined: 13 Feb 12
Posts: 3145
ID: 130544
Credit: 2,211,016,949
RAC: 142,531

Message 157725 - Posted: 7 Nov 2022 | 12:00:48 UTC

Where would the sieving be done? Would it reopen an old badge or be a new effort? I appreciate this is somewhat in the future, if ever.

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 776
ID: 164101
Credit: 305,410,351
RAC: 3,917

Message 157727 - Posted: 7 Nov 2022 | 13:04:05 UTC - in response to Message 157725.

Where would the sieving be done? Would it reopen an old badge or be a new effort? I appreciate this is somewhat in the future, if ever.

Sieving is a huge project, for PrimeGrid of course.
10k megaprimes * 30k candidates/prime = 300M candidates!
Since the sieve must be cut into pieces, both projects can run at the same time and the list of candidates is a FIFO, not a large list.
I have thought about the problem few months ago and wrote a prototype: qsieve

JeppeSN

Joined: 5 Apr 14
Posts: 1780
ID: 306875
Credit: 48,096,366
RAC: 14,202

Message 157728 - Posted: 7 Nov 2022 | 15:21:04 UTC - in response to Message 157725.

Where would the sieving be done? Would it reopen an old badge or be a new effort? I appreciate this is somewhat in the future, if ever.

There does not seem to be any [inactive] badge for SGS Sieve or TPS Sieve or similar, so no old badge to reopen. I cannot find any indication that this should have been part of manual sieving (once that existed) either.

You can use the Find functionality of your web browser in the long thread Sophie Germain Prime Search; look for "siev" to include both "sieve" and "sieving". It seems this was maybe sieved by legendary Lennart alone, somehow.

/JeppeSN

Allen Paschke

Joined: 12 Nov 15
Posts: 29
ID: 428118
Credit: 41,323,601
RAC: 26,609

Message 157739 - Posted: 8 Nov 2022 | 23:18:11 UTC - in response to Message 157728.

Let me do some clarification.

I have 3 very slow PCs, all with Intel GPUs. PPSE and GFN-16 tasks run in 1 hour. PPSE is no longer T5K and GFN-16 will no longer be T5K in the future. MEGA, PPS and GFN-17 tasks find mega prime numbers, and they require 5 - 7 hours to run. All the other sub-projects require days to run, even with multiple threads. I would very much like a new sub-project that finds T5K Prime Numbers in the 600,000 - 800,000 range, with a task run time of 2 hours or less. This new sub-project could be a version of SGS, a new version of another existing sub-project or a totally new sub-project.

What can be done for those people who run PrimeGrid tasks with slow PCs and Intel GPUs?

Michael Millerick
Volunteer tester

Joined: 4 Feb 09
Posts: 918
ID: 35074
Credit: 775,879,200
RAC: 1,081,107

Message 157740 - Posted: 9 Nov 2022 | 0:46:48 UTC - in response to Message 157739.

I have 3 very slow PCs, all with Intel GPUs. PPSE and GFN-16 tasks run in 1 hour. PPSE is no longer T5K and GFN-16 will no longer be T5K in the future. MEGA, PPS and GFN-17 tasks find mega prime numbers, and they require 5 - 7 hours to run. All the other sub-projects require days to run, even with multiple threads. I would very much like a new sub-project that finds T5K Prime Numbers in the 600,000 - 800,000 range, with a task run time of 2 hours or less. This new sub-project could be a version of SGS, a new version of another existing sub-project or a totally new sub-project.

I agree with the sentiment, as I would like similar projects to allow for CPUs to be able to contribute to the annual Tour de Primes without needing to search for megaprimes. That said, eventually PPSE will make its way back into T5K as it passes GFN16. Putting another project between GFN16 and the MEGA threshold will only serve to make it harder for PPSE to claw its way back, and if it has the same characteristics as SGS or the GFN projects, then it too will eventually be pushed off of the T5K.
____________

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13878
ID: 53948
Credit: 383,349,267
RAC: 117,744

Message 157748 - Posted: 9 Nov 2022 | 7:49:14 UTC - in response to Message 157725.

Where would the sieving be done? Would it reopen an old badge or be a new effort? I appreciate this is somewhat in the future, if ever.

It's impossible to predict what will happen with SGS in the future, but I can tell you how the sieving was done in the past.

The SGS sieving was done by a single admin (Lennart) off-line. The sieving wasn't a public project. That's why there's no badge for SGS sieving. Also, even if it was a public sieve, it likely would have been manual sieving, so it would be part of the PSA badge.

When it comes time to do another SGS range, the sieving is likely to be either private like its been in the past, or, if public, it will probably be done manually. I don't see it being worth setting up the automation to do it via BOINC, so the sieving credit would probably be applied to the PSA badge.
____________
My lucky number is 75898524288+1

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 776
ID: 164101
Credit: 305,410,351
RAC: 3,917

Message 157750 - Posted: 9 Nov 2022 | 8:36:56 UTC - in response to Message 157739.

I have 3 very slow PCs, all with Intel GPUs. PPSE and GFN-16 tasks run in 1 hour. PPSE is no longer T5K and GFN-16 will no longer be T5K in the future. MEGA, PPS and GFN-17 tasks find mega prime numbers, and they require 5 - 7 hours to run.

My oldest laptop is an i3-3217U: 1.8GHz, 2 cores, AVX, slowest than your mobile i5's. Running two threads, the computation time for GFN-16 is 30 minutes and for GFN-17 is 2 hours.

As I have written before, a mega-twin or mega-SG is a giant step and is not expected before 2030. A target at 600,000 digits for 2025-27 would seem desirable.

pawg

Joined: 12 Sep 11
Posts: 4
ID: 111682
Credit: 9,464,582
RAC: 204,395

Message 158415 - Posted: 8 Dec 2022 | 21:43:05 UTC

So after completing current SGS sieve file project will be suspended?

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13878
ID: 53948
Credit: 383,349,267
RAC: 117,744

Message 158427 - Posted: 9 Dec 2022 | 2:10:20 UTC - in response to Message 158415.

So after completing current SGS sieve file project will be suspended?

All that has been decided is that we'll run SGS to the end of the current sieve file.

It's a pretty large sieve, with several years to go. We have not given any thought to what comes next.
____________
My lucky number is 75898524288+1

Anthony Ayiomamitis

Joined: 19 Mar 15
Posts: 3014
ID: 386066
Credit: 1,132,493,147
RAC: 565,926

Message 158442 - Posted: 9 Dec 2022 | 12:55:29 UTC - in response to Message 158427.

Michael, thanks for the advance information.

I should start working on my Sapphire badge for SGS at the first opportunity so as to get it out of the way and well ahead of any possible suspension no matter how far away such an event may be.

Having the lowest credit per unit of time, it will take me quite a bit of effort to get it to Sapphire but time seems to be of paramount importance.

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13878
ID: 53948
Credit: 383,349,267
RAC: 117,744

Message 158444 - Posted: 9 Dec 2022 | 13:09:20 UTC - in response to Message 158442.

Michael, thanks for the advance information.

I should start working on my Sapphire badge for SGS at the first opportunity so as to get it out of the way and well ahead of any possible suspension no matter how far away such an event may be.

Having the lowest credit per unit of time, it will take me quite a bit of effort to get it to Sapphire but time seems to be of paramount importance.

Nobody is talking about suspending SGS. Nobody is saying ANYTHING about SGS. 30 other things will change at PrimeGrid before anything changes at SGS. You've got it all backwards.
____________
My lucky number is 75898524288+1

Message boards : Sophie Germain Prime Search : Sophie Germain MEGA?