Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Proposed new formula
Author 
Message 

Hello! I am relatively new to primegrid and I want to run a formula not listed on here,
3^k + 2
So far I have not been able to see any documentation on it anywhere.
Should I ask to get it running or should I go somewhere else?
____________
My lucky number is 3^{504206}+2  


I'm not sure if you're prepared well enough, but you could get advice and start your own search here
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com
GFN14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1
 


Hello! I am relatively new to primegrid and I want to run a formula not listed on here,
3^k + 2
So far I have not been able to see any documentation on it anywhere.
Should I ask to get it running or should I go somewhere else?
Hi R. H. Alderton,
You have asked my favorite kind of question! The kind of question that starts with "I wonder..." I ask these quite often :)
Here are the first few values of k which result in 3^{k}+2 being prime:
1
2
3
4
8
10
14
15
24
26
36
63
98
110
123
126
139
235
243
315
363
386
391
494
1131
1220
1503
1858
These are pretty tiny primes, with the last one on the list having 887 digits, but unfortunately things really slow down past that point when searching for more (at least with PariGP) because there are no quick and special ways to test primality for a number of that form (to the best of my knowledge), like there are with other forms like k3^{n}+1 or any of the other prime forms searched here. You can read about the tests that can be performed when a candidate prime is of the "+1" variety here: https://primes.utm.edu/prove/prove3_1.html
It would be possible to keep searching for more, but it would be a painstaking search I think. Good luck if you do try though and keep us posted with any more finds!
Regards,
Kellen  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 144 ID: 1108183 Credit: 8,505,009 RAC: 158

Here is a list of all known primes (or probable primes) of this form. As Kellen said, we currently have no practical way to prove that a really large number of this form is actually prime, hence why these are only "probable primes" beyond k=10988.  


Hello, and thank you for the advice,
couldn't we just apply Fermat's little theorem to it?
I know the numbers would reach immense scales very quickly
2^[3^504207 + 2]  2 =~10^10^10^5.04
But hypothetically it could be done, right?
____________
My lucky number is 3^{504206}+2  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 144 ID: 1108183 Credit: 8,505,009 RAC: 158

We can certainly use Fermat's little theorembut Fermat's little theorem never tells us that something is guaranteed to be prime, only that if p is prime, then a^(p1) is congruent to 1 mod p for all integers a not divisible by p. The converse is usually true, but not always, because of Carmichael numbers (e.g. 561) and other pseudoprimes (e.g. 341 in base a=2).
So if we test Fermat's congruence for a candidate p with several different choices of a, we can be highly confident, but not 100% confident, that it's prime. In fact, when we call something a "probable prime", that usually means that we've done these tests, perhaps along with some trial factoring and a few soupedup versions of the same idea (e.g. MillerRabin or BPSW) for extra confidence.
One more note: since (as you said) these tests involve really large numbers, we have to be slightly careful when implementing them. The number 2^(3^504207 + 2)  1 has far more digits than there are atoms in the universe, so there is no hope of representing it in binary on any physical computer. But fortunately we don't need to: we only need its congruence class modulo the 240568digit number p = 3^504207 + 2. We can do all our calculations mod p, and some modular exponentiation tricks make it possible to compute 2^(3^504207 + 2)  1 mod p with only about a million multiplication steps. This is feasible on modern computers.  


And even if it turned out to not be prime but satisfied the tests, we have a new Carmichael number!
____________
My lucky number is 3^{504206}+2  


So it turns out the formula is not new. Ravi mentioned OEIS A051783 already. If you could find any new members, you could contribute to that sequence.
But there is also PRP Top. See PRP Top search for 3^n+2. If you found any new ones, you would submit them there.
Since you are not going to be able to prove these numbers prime, they are not going to be admitted into the Prime Pages lists.
/JeppeSN  


Just noticed this pop up on PrimePages: https://primes.utm.edu/primes/page.php?id=130986
Looks like someone is working to prove primality for these :)  


Just noticed this pop up on PrimePages: https://primes.utm.edu/primes/page.php?id=130986
Looks like someone is working to prove primality for these :)
This is our Gelly; was discussed on Discord. /JeppeSN  

GellyVolunteer tester
Send message
Joined: 13 Nov 16 Posts: 40 ID: 468732 Credit: 522,960,451 RAC: 95,438

Just noticed this pop up on PrimePages: https://primes.utm.edu/primes/page.php?id=130986
Looks like someone is working to prove primality for these :)
Oh hey, that's mine! Ravi Fernando recommended it as a nice way to break into the top 20 with a good ECPP machine, so I went with it.
As was discussed, the best chance does really seem to be ECPP for primes of this form. I was a little excited at the prospect of how factorizeable 3^k + 1 and 3^k + 3 were, and using an (N+1)(N1) method for proving them in general, but considering you get many factors in the thousand digit range that will likely never be factorized in our lifetime, it sort of died there.
Perhaps if you were superultralucky with a k that both is very factorizeable, leads to a PRP for 3^k +2, and you got extremely lucky with the factors of 3^k+1 and 3^k+3, you could eke out one superlucky proveable prime that doesn't need a general deterministic primality proof.
It'd be radical if that'd ever happen, but for now, ECPP does a treat on anything smaller than 40k digits with the right hardware.  

Post to thread
Message boards :
General discussion :
Proposed new formula 