Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Sophie Germain Prime Search :
Difference to Proth Prime Search etc.
Author |
Message |
Bur Volunteer tester
 Send message
Joined: 25 Feb 20 Posts: 515 ID: 1241833 Credit: 414,278,186 RAC: 40,609
                
|
Apparently, the main fundamental difference of SGS to other subprojects (those that aren't to proof a conjecture) is that after a prime is found, it is checked whether it's a SG prime.
So why is it a dedicated project? Why not just implement a SG-check in every other subproject? | |
|
|
I don't know the exact reason, but I do know that twin and SG primes are more common in the smaller range.
____________
My lucky number is 6219*2^3374198+1
| |
|
streamVolunteer moderator Project administrator Volunteer developer Volunteer tester Send message
Joined: 1 Mar 14 Posts: 1022 ID: 301928 Credit: 543,195,386 RAC: 1
                        
|
Why not just implement a SG-check in every other subproject?
It's possible, but a pair which just worth testing is very rare. Theoretically, everybody could download a list of known primes from T5K or PG and check their possible pairs manually. But I doubt that anything will left there to test even after minor sieving.
SGS subproject uses specially sieved set of candidates, maximizing probability to find a paired prime. Unlike other projects, we're not testing all possible candidates in this sequence, but only those who have highest probability of pair - those where 2 of 3 possible pairs do not have small factors.
| |
|
|
Stream is right, the difference is in this subproject the sieve was prepared specifically to give a higher chance of twin and Sophie Germain.
Note about other subprojects:
Twins in other projects: In projects where we already search both the +1 and the -1 form (for same series), like 321 and all four (current) subprojects on PRPNet, a twin prime would be found automatically, you would just have to notice it.
Sophie Germains in other projects: In base 2 projects where we use the -1 form, like The Riesel Problem, these would be found automatically. This is because for each k we do, we do all n. So if k*2^n - 1 and k*2^{n+1} - 1 were both primes, we would find both; you would just have to notice it.
In base 2 projects where we use the +1 form, we could find a pair of nearly doubled primes, k*2^n + 1 and k*2^{n+1} + 1. These are similar to Sophie Germains and would go to Caldwell's Cunningham Chains (2nd kind) page as chains of length two.
So while such finds could theoretically be found in (some) of the other subprojects, it is unlikely because the sieving there was not designed to boost the chance of that.
Addition: Note that for some projects or some k values, divisibility by 3 alone is enough to exclude the possibility of twins and/or Sophie Germains.
/JeppeSN | |
|
Crun-chi Volunteer tester
 Send message
Joined: 25 Nov 09 Posts: 3208 ID: 50683 Credit: 135,132,479 RAC: 57,320
                         
|
I run initially scan and so far found five pairs on plus and minus side :)
So those pairs and included in PG -1 sieve data.
____________
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! | |
|
|
I run initially scan and so far found two pairs on plus and minus side :)
Scan for what?
Two pairs of twins?!
____________
My lucky number is 6219*2^3374198+1
| |
|
Crun-chi Volunteer tester
 Send message
Joined: 25 Nov 09 Posts: 3208 ID: 50683 Credit: 135,132,479 RAC: 57,320
                         
|
I run initially scan and so far found two pairs on plus and minus side :)
Scan for what?
Two pairs of twins?!
I take plus side primes and try to find does those k and minus side exist in sieve files from PG.
From about 170 candidates ( 170 primes on plus side) five of them have pair with same exponent on minus side
____________
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! | |
|
|
Crun-chi, but what data are you scanning? From what subproject? /JeppeSN | |
|
|
Let b be a fixed base not divisible by 3. Let k be a multiplier.
Twin: If for one exponent n, both k*b^n + 1 and k*b^n - 1 are primes, then k must be divisible by 3.
Sophie Germain: If there are two consecutive exponents that give primes k*b^n - 1 and k*b^{n+1} - 1, then k must be divisible by 3.
Cunningham chain 2nd kind: If there are two consecutive exponents that give primes k*b^n + 1 and k*b^{n+1} + 1, then k must be divisible by 3.
So in most of our subprojects, we must have k divisible by 3, in order for a discovered prime to be able to be twin (to the side we can test deterministically), be Sophie Germain/safe, or be in a Cunningham chain of the 2nd kind.
Our GFN primes may be in a Cunningham chain of the 2nd kind when b is divisible by 3.
/JeppeSN | |
|
Crun-chi Volunteer tester
 Send message
Joined: 25 Nov 09 Posts: 3208 ID: 50683 Credit: 135,132,479 RAC: 57,320
                         
|
Crun-chi, but what data are you scanning? From what subproject? /JeppeSN
I take all know base 2 megaprimes. Since PG released base 2 -1 sieve on public it was easy to find and eliminate any k with specific n .
____________
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! | |
|
robish Volunteer moderator Volunteer tester
 Send message
Joined: 7 Jan 12 Posts: 2197 ID: 126266 Credit: 7,323,343,059 RAC: 3,133,740
                               
|
Twin: If for one exponent n, both k*b^n + 1 and k*b^n - 1 are primes, then k must be divisible by 3.
All 5 k's were divisible by 3, but not prime :(
____________
My lucky numbers 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26 | |
|
|
Let b be a fixed base not divisible by 3. Let k be a multiplier.
Twin: If for one exponent n, both k*b^n + 1 and k*b^n - 1 are primes, then k must be divisible by 3.
Sophie Germain: If there are two consecutive exponents that give primes k*b^n - 1 and k*b^{n+1} - 1, then k must be divisible by 3.
Cunningham chain 2nd kind: If there are two consecutive exponents that give primes k*b^n + 1 and k*b^{n+1} + 1, then k must be divisible by 3.
So in most of our subprojects, we must have k divisible by 3, in order for a discovered prime to be able to be twin (to the side we can test deterministically), be Sophie Germain/safe, or be in a Cunningham chain of the 2nd kind.
(EDITED!)
In fact you can also have a Cunningham chain of the 2nd kind where the two primes are found with the N+1 method, or a Sophie Germain and a safe prime found by the N-1 method. In that untraditional situation, what I said about k being divisible by 3, is no longer true.
Here is an example with Cunningham 2nd:
40931485*2^53123 - 1, clearly proved with the N+1 method
40931485*2^53124 - 3, proved with the N+1 method using the previous prime!
Here is an example with Sophie Germain and safe:
64670473*2^74146 + 1, clearly proved with the N-1 method
64670473*2^74147 + 3, proved with the N-1 method using the previous prime!
Such examples were not covered by my post, and indeed 40931485 and 64670473 are not divisible by 3.
/JeppeSN | |
|
Bur Volunteer tester
 Send message
Joined: 25 Feb 20 Posts: 515 ID: 1241833 Credit: 414,278,186 RAC: 40,609
                
|
Thanks for the explanations. | |
|
Message boards :
Sophie Germain Prime Search :
Difference to Proth Prime Search etc. |