## Other

drummers-lowrise

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

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
JeppeSN

Joined: 5 Apr 14
Posts: 1727
ID: 306875
Credit: 41,389,304
RAC: 13,476

Message 142789 - Posted: 29 Aug 2020 | 14:24:23 UTC

Primes of the form bN + 1 are not hard to come by. For example with exponent N=2, we have 12 + 1, 22 + 1, 42 + 1, 62 + 1, 102 + 1, 142 + 1, 162 + 1, 202 + 1, etc.

But what if we want 1 < b < N? Then only the following are known:

• 24 + 1
• 28 + 1 and 48 + 1
• 216 + 1
• 3032 + 1

• 120128 + 1

• 46512 + 1
• 8241024 + 1
• 1502048 + 1
• 15344096 + 1

• 4859465536 + 1
• 62722131072 + 1 and 130816131072 + 1
• 24518262144 + 1 and 40734262144 + 1 and 145310262144 + 1
• 75898524288 + 1 and 341112524288 + 1 and 356926524288 + 1 and 475856524288 + 1
• 9194441048576 + 1

That's twenty-one primes, where we have counted 65537 twice (216 + 1 and 48 + 1). I guess 65537 is the only prime that can be written as bN + 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

Kellen

Joined: 10 Jan 18
Posts: 484
ID: 967938
Credit: 1,600,003,090
RAC: 1

Message 142791 - Posted: 29 Aug 2020 | 15:47:47 UTC - in response to Message 142789.

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.pagesperso-orange.fr/primes/stat.html.

GFN20 was SO close to being 2 rather than 1 as well. The second known prime is 10590941048576+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

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

Message 142793 - Posted: 29 Aug 2020 | 16:22:46 UTC

Gets my vote.

robish
Volunteer moderator
Volunteer tester

Joined: 7 Jan 12
Posts: 2139
ID: 126266
Credit: 6,789,459,816
RAC: 2,894,624

Message 142799 - Posted: 29 Aug 2020 | 17:08:01 UTC - in response to Message 142793.

Gets my vote.

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

JeppeSN

Joined: 5 Apr 14
Posts: 1727
ID: 306875
Credit: 41,389,304
RAC: 13,476

Message 142801 - Posted: 29 Aug 2020 | 18:52:11 UTC - in response to Message 142789.

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

Kellen

Joined: 10 Jan 18
Posts: 484
ID: 967938
Credit: 1,600,003,090
RAC: 1

Message 142802 - Posted: 29 Aug 2020 | 19:16:44 UTC - in response to Message 142801.

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 GFN-N prime with a b value less than 2N, but any value is possible from zero to 2N-1.

For example; for GFN-16, referring to numbers of the form b216+1 (b65536+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 (4859465536+1 is prime).

For GFN-16 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 GFN-30 we would expect 1 prime between 2230+1 (21073741824+1) and (230-2)230+1 (10737418221073741824+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!

Bur
Volunteer tester

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

Message 142816 - Posted: 30 Aug 2020 | 9:10:51 UTC - in response to Message 142802.

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

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 966
ID: 1097922
Credit: 38,467,401
RAC: 176,493

Message 142818 - Posted: 30 Aug 2020 | 9:36:09 UTC - in response to Message 142816.

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