Come join us!

[gd_barnes]

I thought that everyone might find a list of GFN primes for bases <= 1024 up to n=131072 (2^17) somewhat interesting:

http://www.noprimeleftbehind.net/crus/GFN-primes.htm

I now use the list for showing (or not showing) "k=x is a GFN with no known prime" on the web pages.

Of interest is the "not possible" bases as opposed to the bases where a prime has not been found and is highly unlikely to ever be found. There are a total of 8 of them. Clearly there is a difference. If it's not possible, we can prove that there will never be a prime. If there is no prime shown, then it is possible because we cannot currently prove that there will never be one.

Regardless, there is a very strong chance that no more primes will ever be found on these bases; at least with mathematics as we currently know it. The largest prime found was 150^2048+1.

I realize that other projects have done such a search but I could not easily find a comprehensive list of them starting from n=1. Although they have all likely been contiguously searched to n=2^17, I wanted to doublecheck them all myself. It took about ~3 weeks on one core and I'm fairly certain that I was not using anywhere near the fastest method for sieving and testing. I suspect that other projects have likely pushed these bases to at least n=2^18 and possibly 2^19. Iirc, base 2 has been pushed to n=2^32 with no more primes found.

I have added a reference link to this list at the bottom of the 1st post here because it gives some idea of why we exclude them from the conjectures.


Gary

[kar_bon]

Originally Posted by gd_barnes

I realize that other projects have done such a search but I could not easily find a comprehensive list of them starting from n=1.

Take a look at here and the links under the table!

A paper of distribution of generalized Fermat prime numbers here (Download-link right hand).

[gd_barnes]

Originally Posted by kar_bon

Take a look at here and the links under the table!

A paper of distribution of generalized Fermat prime numbers here (Download-link right hand).

Interesting reading. It doesn't put it in order by base like we need here nor does it show an extension of the search to n>2^17 but I was able to glance at several of the larger primes for bases<=1024 and confirmed the listing that I made. I did look in the table for the GFN project and I see that as of 2004, there were still many holes for bases <= 1024 for n>=2^18.

I see that there is one GFN prime on the top-5000 for n=2^18 for base 24518. That tells me that likely someone has searched all bases up that high for n=2^18 so it appears that my search almost completely covered searches done for bases <= 1024. The one main exception is for bases <= 12, which have had large-scale factorization done on them on the ProthSearch pages up to a much higher limit.

It would be interesting to see something more up-to-date on the search status since 2004.

Thanks for the reference,

[__HRB__]

If we use Proth's theorem to search for primes of the form (k*2^n)^(2^m)+1 with k<2^n, and if (k*2^n)^2+m<2^m, we could do the required negacyclic convolution with Schoenhage-Strassen in base k*2^n.

Choosing k<2^24 gives us 16M candidates for every (n,m) combination, involves much less arithmetic than irrational base DWTs and is suitable for GPUs.

[gd_barnes]

Originally Posted by __HRB__

If we use Proth's theorem to search for primes of the form (k*2^n)^(2^m)+1 with k<2^n, and if (k*2^n)^2+m<2^m, we could do the required negacyclic convolution with Schoenhage-Strassen in base k*2^n.

Choosing k<2^24 gives us 16M candidates for every (n,m) combination, involves much less arithmetic than irrational base DWTs and is suitable for GPUs.

The last part of the 1st para. and the entire 2nd para. is over my head. Would some of our higher math and programming folks clarify how it might assist CRUS?

From what I could understand of it, since we search the forms k*b^n-1 and k*b^n+1, it appears that the forms referred to here only allow for exponents (n-values in our forms) that are powers of 2, which would only help in the search for GFNs, i.e. of the form b^(2^m)+1 where b=(k*2^n in your form). That wouldn't really help us much.

To clarify my last para., it appears to me that in the form (k*2^n)^(2^m)+1, (k*2^n) is the base (the b-value in our forms) and (2^m) is the exponent (the n-value in our forms).

[__HRB__]

Originally Posted by gd_barnes

[...]which would only help in the search for GFNs, i.e. of the form b^(2^m)+1 where b=(k*2^n in your form).[...]

Hm, it appears that I forgot to mention that it would only work for generalized Fermats!

Originally Posted by gd_barnes

[...]That wouldn't really help us much.[...]

Really? The idea would be to search for very large primes, for instance among the numbers that have 20*2^24 bits ~ 100M-digits. With m=13 and k*2^n slightly less than 5*2^13 bits, we can do a negacyclic convolution of length 2^13 using 2^10 as a 2^13th root of -1 (mod 2^(5*2^14)+1).

[gd_barnes]

Originally Posted by __HRB__

Hm, it appears that I forgot to mention that it would only work for generalized Fermats!



Really? The idea would be to search for very large primes, for instance among the numbers that have 20*2^24 bits ~ 100M-digits. With m=13 and k*2^n slightly less than 5*2^13 bits, we can do a negacyclic convolution of length 2^13 using 2^10 as a 2^13th root of -1 (mod 2^(5*2^14)+1).

CRUS does not formally search for GFN primes. I do it on the side just to see if the Sierpinski (+1) bases have a GFN that is a prime but that is not necessary to prove (or disprove) a conjecture. Even then, we only go up to base 1024. Much higher bases would need to be searched to find a gargantuan prime of the size that you are talking about.

Edit: I see where the confusion comes from: A few posts ago where I posted all of the GFN primes for bases <= 1024 up to n=2^17. That was for my own reference as much as anything to see which bases <= 1024 did not have a GFN prime. It also helps our co-admin determine whether or not to put this statement on the web pages: "k=1 is a GFN with no known prime". But GFN primes are not needed to prove/disprove the conjectures. Therefore our list of GFN primes up to n=2^17 is sufficient for our purposes.

You might post this in the GIMPS / math forums here. I think you'll get better response. I for one am interested in reading about faster ways to test GFNs for primes because for the # of candidates that need to be searched, they are very prime heavy. But I would do such a search outside of the scope of this project.

[henryzz]

I think what he was refering to is similar to what jean outlined here.

[gd_barnes]

I have added a new small subproject for CRUS. It is now reflected in the 1st post here as "subproject #2" and shown on the main web pages.

The subproject is to test the even k's for the Sierp base 2 2nd conjecture of k=271129. 3 projects have already extensively tested all odd k's < 271129. I have now tested all even k's. There are 3 k's remaining at n=100K. I will be testing them up to n=1M before releasing them for public sieving and testing.

See the 1st post here for more info. All applicable info. including links for all of the projects involved in testing the Sierp 2nd conjecture is shown on the main powers-of-2 page and a new Sierp base 2 reservations page.

I will be changing the "base 2 even-n and odd-n" thread to include "base 2 even-k" and statuses will be reported there. I'm currently at n=100K on the k's and am doublechecking ALL remaining 77 k's for 78557<k<271129 at n=100K up to n=250K to make sure that nothing has fallen through the cracks of the 2 projects that are testing in that range except for the even k's. I should be at n=250K in ~2 weeks. After that, I'll just be testing the even k's so should go quickly.

Interestingly, CRUS is already testing 2 Riesel base 2 even k's. If I find 1 of the 3 k's as prime by n=1M for Sierp base 2, we'll have 2 even k's on each side to search.


Gary

[henryzz]

I don't understand. (k*2)*2^n+1=k*2^(n+1)+1 so all even ks have been tested as k/2. Do you mean for even ns as well or something?
An example I found of conversion: 55816*2^14536+1 = 6977*2^14539+1.

[gd_barnes]

Originally Posted by henryzz

I don't understand. (k*2)*2^n+1=k*2^(n+1)+1 so all even ks have been tested as k/2. Do you mean for even ns as well or something?
An example I found of conversion: 55816*2^14536+1 = 6977*2^14539+1.

As opposed to explaining the math, you might try testing one of the 3 even k's remaining and see if you can find a prime. Just a simple test starting at n=1 and going up to n=1000 or 2500 is sufficient. Then divide the k by 2 or 4 to get down to an odd k and do the test again. I think you will be surprised.

You could also do the same test on the 2 Riesel base 2 even k's that are remaining and have been tested to n>1M.

Think: MOBs that we test all the time here.

It has nothing to do with even n's.

Bottom line: The base 2 conjectures that were originally proposed back in the 50s and 60s omitted a simple bit of mathematical reasoning in stating that the proof only needed primes for odd k's. They apparently assumed that even k's could always be "absorbed" into the exponent, which is not always the case. The Sierp base 4, Riesel/Sierp 5, and CRUS projects as well as Prof. Caldwell in his now published math paper on the Sierp conjectures have taken into account the testing of MOBs. This reasoning was confirmed and actually suggested/implied by Jean Penne early on in this project as well as Prof. Caldwell; both of whom have far more mathematical knowledge than me.

Interestingly this did not come about until earlier this year when PrimeGrid decided to start fully "filling in" the Sierp base 2 2nd conjecture where PSP had only done prime k's and PrimeGrid was only doing the remaining odd k's. For the 1st conjecture of k=78557, there are no even k's remaining. Strangely, the highest first prime found for even k<78557 was, you guessed it, for k=55816 at n=14536. Was that just coincidence that you came up with k=55816 to use as an example?

BTW reference your example, k=6977*2^3+1 is prime so k=6977 did not need searching further. But k=55816 could not claim such a small prime and so was not eliminated until n=14536.