20080516, 11:34  #1 
Jan 2005
1DF_{16} Posts 
Algebraic factor issues base 24
When restarting the sieve for Sierpinski base 24 I noticed sr2sieve saying the following:
'Recognised Generalised Fermat sequence A^2+B^2' What does it mean, (it loaded only 143 of the 144 Legendre lookup tables) 
20080518, 06:47  #2  
May 2007
Kansas; USA
11·929 Posts 
Quote:
You might try and contact Geoff and see if he has an answer. Gary 

20080518, 23:08  #3  
Mar 2003
New Zealand
13·89 Posts 
Quote:
In that case all of the terms in that sequence will be of the form A^2+1 and sr2sieve can use an alternative to calculating Legendre symbols as all factors will be of the form 8x+1. (The gain will be very small since only one sequence out of 144 has that property). The reason that it only happend after restarting could be that there were still some odd terms when the sieve was first started but you removed them from the sieve file before restarting? 

20080518, 23:45  #4 
May 2007
Kansas; USA
11·929 Posts 
Interesting. Thanks for the info Geoff.
Michaf, can you post the kvalue that produced the message? Perhaps it can be analyzed as a GFN, which are not considered in the conjectures. Gary 
20080519, 00:41  #5 
Mar 2003
New Zealand
13×89 Posts 
The other possibility is if the k value is of the form 6*x^2 and all corresponding n values are odd, that would also result in all terms k*24^n+1 being of the form A^2+1.

20080519, 04:19  #6 
May 2007
Kansas; USA
27EB_{16} Posts 
It seems to me that we have yet another possibility for the elimination of kvalues in some bases for the conjectures as follows:
1. Some of the nvalues are removed by either algebraic factors or 'numeric' factors (as has happened on several bases already). 2. The remaining nvalues make GFNs and as such, will not be considered. Essentially such bases that have kvalues with the above 2 conditions could technically have THREE conditions (numeric factors, algebraic factors, and GFNs) that eliminate all of the kvalues below the conjectured Sierp number. THAT should be interesting to attempt to show on the web pages. lol This project gets more strange every day! Gary 
20080519, 05:03  #7  
May 2007
Kansas; USA
11·929 Posts 
Quote:
Micha, It appears there are more algebraic factors than you originally anticipated. You originally were able to eliminate all kvalues that were perfect squares because m^2*24^n1 has a factor of 5 for odd n and where k=m^2 and n=2q, it has factors of (m*24^q1)*(m*24^q+1) for even n. BUT...it appears that you can also eliminate THE BASE TIMES a perfect square because it has a factor of 5 for EVEN n and where k=24*m^2 and n=2q1 for odd n, it has the same factors as above for even n. I typed this fairly fast due to time restrictions so my algebra might not be perfect, but I was able to convince myself of it relatively easily. Please see if you can do the same. This allows the elimination of the following additional 13 kvalues with algebraic factors: 96, 216, 1176, 1536, 3456, 4056, 6936, 7776, 12696, 17496, 18816, 24576, and 26136. To more generalize the rule, on the Riesel conjectures, I THINK anytime you are able to eliminate kvalues that are perfect squares with algebraic factors, you should be able to eliminate perfect squares times the base. Of course this should always be checked before doing so. I will update the web pages accordingly with the exception of the algebraic factor listing. I need to make sure my algebra is perfect before showing it specifically. Note that I don't show kvalues that are a multiple of the base if k / b equals a kvalue that is already remaining. Since your 2 MOB listings reduce to a kvalue that is already remaining, they will not be shown nor considered in the count of k's remaining. Subtracting your 2 kvalues that are MOB's and the 13 kvalues that are 24*m^2, this leaves 155 kvalues remaining for Riesel base 24 at n=25K. Please eliminate these 15 kvalues from your searches. Edit: It appears that k=6 also has algebraic factors for odd n and a factor of 5 for even n. I don't have time to come up with the specific factors or a proof. See if you can and I'll also eliminate it. It would be very unusual for such a low kvalue to have no primes at this point if it was possible for it to have a prime. Thanks, Gary Last fiddled with by gd_barnes on 20080519 at 05:30 

20080519, 05:46  #8 
Jan 2005
479 Posts 

20080519, 17:46  #9 
Jan 2005
479 Posts 
I agree with you, Gary,
k*24^n1 insert k=24*m^2 (k=base*perfect square) 24*m^2*24^n1 insert n=2q1 (n=uneven) 24*m^2*24^(2q1)1 = m^2*24^(2q)1 which is exactly the same as we had with a perfect square. Wonderful :) 
20080519, 21:31  #10  
Mar 2003
New Zealand
13·89 Posts 
Quote:
Quote:
However there is no reason to expect any problem finding a prime for this sequence, because the terms are not increasing any faster than a normal sequence. In fact sieving for this sequence is more efficient than a normal sequence, so we are more likely to find a prime for a given abount of work. It is only for generalised Fermat sequences where the base is fixed, e.g. 6^n+1, where finding a prime is likely to be a big problem, because the terms that could possibly be prime (those where n is a power of 2) are increasing exponentially. 

20080520, 03:45  #11  
May 2007
Kansas; USA
11×929 Posts 
Quote:
That makes sense. I was referring to kvalues where, possibly odd n's result in algebraic factors and even n's result in GFN's. THAT would be an interesting situation to come across! Micha, you may just need to sieve k=16641 for a higher nrange for Sierp base 24 in order for it to have terms remaining to test for prime. It will likely be very low weight but not nearly as low as a true GFn! Does this sound like a correct recommendation Geoff? Thanks, Gary 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why can't I start factmsieve.py with a poly file, but no factor base?  EdH  Factoring  25  20180326 15:59 
primitive roots when the base is a quadratic algebraic integer  devarajkandadai  Number Theory Discussion Group  0  20180208 05:15 
trial division over a factor base  Peter Hackman  Factoring  7  20091026 18:27 
GNFS  Factor Base  Golem86  Factoring  11  20070717 18:08 
Quadratic Sieve  How large should the factor base be?  hallstei  Factoring  5  20050419 11:58 