Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Generalized Fermat Prime Search :
Primes b^N + 1 with 1 < b < N
Author 
Message 

Primes of the form b^{N} + 1 are not hard to come by. For example with exponent N=2, we have 1^{2} + 1, 2^{2} + 1, 4^{2} + 1, 6^{2} + 1, 10^{2} + 1, 14^{2} + 1, 16^{2} + 1, 20^{2} + 1, etc.
But what if we want 1 < b < N? Then only the following are known:

 2^{4} + 1
 2^{8} + 1 and 4^{8} + 1
 2^{16} + 1
 30^{32} + 1

 120^{128} + 1

 46^{512} + 1
 824^{1024} + 1
 150^{2048} + 1
 1534^{4096} + 1



 48594^{65536} + 1
 62722^{131072} + 1 and 130816^{131072} + 1
 24518^{262144} + 1 and 40734^{262144} + 1 and 145310^{262144} + 1
 75898^{524288} + 1 and 341112^{524288} + 1 and 356926^{524288} + 1 and 475856^{524288} + 1
 919444^{1048576} + 1
That's twentyone primes, where we have counted 65537 twice (2^{16} + 1 and 4^{8} + 1). I guess 65537 is the only prime that can be written as b^{N} + 1 with 1 < b < N in more than one way?
The next bullet in the list is unknown! Run GFN21 to help determine if there are any primes here. The bullet after that is going to be GFN22+DYFL.
To be explicit, GFN21 needs to reach b=2097152 to determine how many primes in bullet #21. And GFN22 needs to catch up with DYFL, and DYFL needs to reach incredible b=4194304, with no "holes" (if DYFL jumps because of a new World Record outside PrimeGrid, then GFN22 must fill the hole) to complete bullet #22.
There is my OEIS entry A277967 where I count the number of primes in each bullet. Help extend it.
0, 1, 2, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 2, 3, 4, 1, ?, ?, ...
Theoretical problem: Should A277967(n) tend to zero as n grows without bound? Can we give a qualified guess even if a proof is out of reach? See Yves Gallot's pages Results and Statistics.
/JeppeSN  


A very interesting sequence JeppeSN!
GFN19 seems to have been incredibly lucky to end up with 4 terms with b<524288. Only about a 2% chance of that based on Yves' calculator http://yves.gallot.pagespersoorange.fr/primes/stat.html.
GFN20 was SO close to being 2 rather than 1 as well. The second known prime is 1059094^{1048576}+1, which is only 10518 past the cutoff.
I love searches like this because the goal is reached whether we find one prime, ten primes, or no primes. As soon as we pass b=2097152 with all b below that complete the sequence can be updated. With the current sieve depth on GFN21, a rough estimate is that we have about 275000 terms left to check, which means about 550000 tasks. I propose a GFN21 challenge next year to help push that forward!  

Dave Send message
Joined: 13 Feb 12 Posts: 3062 ID: 130544 Credit: 2,120,364,724 RAC: 1,537,968

Gets my vote.  

robishVolunteer moderator Volunteer tester
Send message
Joined: 7 Jan 12 Posts: 2139 ID: 126266 Credit: 6,789,459,816 RAC: 2,894,624

Gets my vote.
Me too.
____________
My lucky numbers 1059094^{1048576}+1 and 224584605939537911+81292139*23#*n for n=0..26  


Theoretical problem: Should A277967(n) tend to zero as n grows without bound? Can we give a qualified guess even if a proof is out of reach? See Yves Gallot's pages Results and Statistics.
After having consulted Yves, I now believe A277967 is "balanced" in the sense that limsup A277967(n) = +∞, and liminf A277967(n) = 0. And the "expected" value of each term is near 1.0. Of course, this is a conjecture at most, not something we can prove. /JeppeSN  


Theoretical problem: Should A277967(n) tend to zero as n grows without bound? Can we give a qualified guess even if a proof is out of reach? See Yves Gallot's pages Results and Statistics.
After having consulted Yves, I now believe A277967 is "balanced" in the sense that limsup A277967(n) = +∞, and liminf A277967(n) = 0. And the "expected" value of each term is near 1.0. Of course, this is a conjecture at most, not something we can prove. /JeppeSN
To add a few examples to all of this, because I find examples easier to understand: It is expected that, on average, there will be 1 GFNN prime with a b value less than 2^{N}, but any value is possible from zero to 2^{N1}.
For example; for GFN16, referring to numbers of the form b^{216}+1 (b^{65536}+1), there will be 1 b value from 2 to 65534 (inclusive) that results in a prime, and you can see from JeppeSN's table that is the case, with b=48594 (48594^{65536}+1 is prime).
For GFN16 the minimum possible value was 0 (no primes) and the maximum possible value was 32768 (the number of even numbers less than 65536).
Another example, somewhat extreme, would be that For GFN30 we would expect 1 prime between 2^{230}+1 (2^{1073741824}+1) and (2^{30}2)^{230}+1 (1073741822^{1073741824}+1).
The expected number will not always be 1 for a given N, but it should average out that way and probably not deviate a whole lot moving forward. The true number will be variable too, but hopefully someday we can fill out at least a few of the next values, and fingers crossed that they are >1!  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 511 ID: 1241833 Credit: 408,507,731 RAC: 26,943

Very interesting way to look at GFN. That's what I like about PG, it's not just "the largest prime", but rather specific primes or general findings.
One more reason to finally get a real GPU for some crunching... :)
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000  


Very interesting way to look at GFN. That's what I like about PG, it's not just "the largest prime", but rather specific primes or general findings.
One more reason to finally get a real GPU for some crunching... :)
LOL
I'll move the discussion about a lowend GPU to another thread.
____________
My lucky number is 6219*2^3374198+1
 

Message boards :
Generalized Fermat Prime Search :
Primes b^N + 1 with 1 < b < N 