 mersenneforum.org Algebraic factor issues base 24
 Register FAQ Search Today's Posts Mark Forums Read  2008-05-16, 11:34 #1 michaf   Jan 2005 479 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)   2008-05-18, 06:47   #2
gd_barnes

May 2007
Kansas; USA

19×541 Posts Quote:
 Originally Posted by michaf 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)
I'm not sure. There must be some k-value for Sierp base 24 that somehow reduces to a Generalized Fermat number, i.e. b^n+1, for all n-values but I can't figure out what it would be.

You might try and contact Geoff and see if he has an answer.

Gary   2008-05-18, 23:08   #3
geoff

Mar 2003
New Zealand

100100001012 Posts Quote:
 Originally Posted by michaf 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)
It probably means that one of the k values is a square and all of the corresponding n values are even.

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?   2008-05-18, 23:45 #4 gd_barnes   May 2007 Kansas; USA 19·541 Posts Interesting. Thanks for the info Geoff. Michaf, can you post the k-value that produced the message? Perhaps it can be analyzed as a GFN, which are not considered in the conjectures. Gary   2008-05-19, 00:41 #5 geoff   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.   2008-05-19, 04:19 #6 gd_barnes   May 2007 Kansas; USA 19·541 Posts It seems to me that we have yet another possibility for the elimination of k-values in some bases for the conjectures as follows: 1. Some of the n-values are removed by either algebraic factors or 'numeric' factors (as has happened on several bases already). 2. The remaining n-values make GFNs and as such, will not be considered. Essentially such bases that have k-values with the above 2 conditions could technically have THREE conditions (numeric factors, algebraic factors, and GFNs) that eliminate all of the k-values 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   2008-05-19, 05:03   #7
gd_barnes

May 2007
Kansas; USA

19·541 Posts Quote:
 Originally Posted by michaf afaik these are the ones that still need a prime: Mobs: 'normal': Code: 6*24^n-1 96*24^n-1 216*24^n-1 389*24^n-1 486*24^n-1 726*24^n-1 1176*24^n-1 1324*24^n-1 1536*24^n-1 1581*24^n-1 1711*24^n-1 1824*24^n-1 2144*24^n-1 2166*24^n-1 2606*24^n-1 2839*24^n-1 2844*24^n-1 3006*24^n-1 3456*24^n-1 3714*24^n-1 3754*24^n-1 4056*24^n-1 4239*24^n-1 5046*24^n-1 5356*24^n-1 5604*24^n-1 5766*24^n-1 5784*24^n-1 5791*24^n-1 6001*24^n-1 6116*24^n-1 6466*24^n-1 6781*24^n-1 6831*24^n-1 6936*24^n-1 7284*24^n-1 7321*24^n-1 7776*24^n-1 7809*24^n-1 7849*24^n-1 8021*24^n-1 8186*24^n-1 8266*24^n-1 8301*24^n-1 8759*24^n-1 8894*24^n-1 9039*24^n-1 9126*24^n-1 9234*24^n-1 9329*24^n-1 9419*24^n-1 9446*24^n-1 9519*24^n-1 10086*24^n-1 10171*24^n-1 10219*24^n-1 10399*24^n-1 10666*24^n-1 10701*24^n-1 10716*24^n-1 10869*24^n-1 10894*24^n-1 11101*24^n-1 11261*24^n-1 11516*24^n-1 11834*24^n-1 11906*24^n-1 12141*24^n-1 12326*24^n-1 12429*24^n-1 12696*24^n-1 13269*24^n-1 13311*24^n-1 13401*24^n-1 13661*24^n-1 13691*24^n-1 13869*24^n-1 14406*24^n-1 14566*24^n-1 14656*24^n-1 15019*24^n-1 15151*24^n-1 15606*24^n-1 15614*24^n-1 15819*24^n-1 16234*24^n-1 16616*24^n-1 16724*24^n-1 16876*24^n-1 17019*24^n-1 17436*24^n-1 17496*24^n-1 17879*24^n-1 17966*24^n-1 18054*24^n-1 18454*24^n-1 18504*24^n-1 18509*24^n-1 18789*24^n-1 18816*24^n-1 18891*24^n-1 18964*24^n-1 19116*24^n-1 19259*24^n-1 19644*24^n-1 20026*24^n-1 20122*24^n-1 20576*24^n-1 20611*24^n-1 20654*24^n-1 20699*24^n-1 20804*24^n-1 20879*24^n-1 20886*24^n-1 21004*24^n-1 21411*24^n-1 21464*24^n-1 21524*24^n-1 21639*24^n-1 21809*24^n-1 22279*24^n-1 22326*24^n-1 22604*24^n-1 22839*24^n-1 22861*24^n-1 23059*24^n-1 23549*24^n-1 24576*24^n-1 25046*24^n-1 25136*24^n-1 25349*24^n-1 25379*24^n-1 25389*24^n-1 25419*24^n-1 25509*24^n-1 25731*24^n-1 26136*24^n-1 26176*24^n-1 26229*24^n-1 26661*24^n-1 26721*24^n-1 27154*24^n-1 27199*24^n-1 27309*24^n-1 28001*24^n-1 28276*24^n-1 28354*24^n-1 28384*24^n-1 28554*24^n-1 28566*24^n-1 28849*24^n-1 28859*24^n-1 28891*24^n-1 29264*24^n-1 29531*24^n-1 29569*24^n-1 29581*24^n-1 30061*24^n-1 30279*24^n-1 30574*24^n-1 31071*24^n-1 31336*24^n-1 31466*24^n-1 31734*24^n-1 31751*24^n-1 31854*24^n-1 31996*24^n-1 32099*24^n-1

Micha,

It appears there are more algebraic factors than you originally anticipated. You originally were able to eliminate all k-values that were perfect squares because m^2*24^n-1 has a factor of 5 for odd n and where k=m^2 and n=2q, it has factors of (m*24^q-1)*(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=2q-1 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 k-values 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 k-values 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 k-values that are a multiple of the base if k / b equals a k-value that is already remaining. Since your 2 MOB listings reduce to a k-value that is already remaining, they will not be shown nor considered in the count of k's remaining.

Subtracting your 2 k-values that are MOB's and the 13 k-values that are 24*m^2, this leaves 155 k-values remaining for Riesel base 24 at n=25K. Please eliminate these 15 k-values 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 k-value 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 2008-05-19 at 05:30   2008-05-19, 05:46   #8
michaf

Jan 2005

1DF16 Posts There is indeed one square value of k: 16641

Quote:
 Originally Posted by gd_barnes Interesting. Thanks for the info Geoff. Michaf, can you post the k-value that produced the message? Perhaps it can be analyzed as a GFN, which are not considered in the conjectures. Gary   2008-05-19, 17:46 #9 michaf   Jan 2005 7378 Posts I agree with you, Gary, k*24^n-1 insert k=24*m^2 (k=base*perfect square) 24*m^2*24^n-1 insert n=2q-1 (n=uneven) 24*m^2*24^(2q-1)-1 = m^2*24^(2q)-1 which is exactly the same as we had with a perfect square. Wonderful :)   2008-05-19, 21:31   #10
geoff

Mar 2003
New Zealand

22058 Posts Quote:
 Originally Posted by gd_barnes 2. The remaining n-values make GFNs and as such, will not be considered.
I don't think there is any necessary reason to exclude these cases. For example in michaf's case for Sierpinski base 24:

Quote:
 Originally Posted by michaf there is There is indeed one square value of k: 16641
Since k=16641=129^2, and if all values of n are even, n=2m say, then each term of the sequence k*24^n+1 is equal to (129*2^m)^2+1, which is a generalised Fermat number.

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.   2008-05-20, 03:45   #11
gd_barnes

May 2007
Kansas; USA

1027910 Posts Quote:
 Originally Posted by geoff I don't think there is any necessary reason to exclude these cases. For example in michaf's case for Sierpinski base 24: Since k=16641=129^2, and if all values of n are even, n=2m say, then each term of the sequence k*24^n+1 is equal to (129*2^m)^2+1, which is a generalised Fermat number. 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.

That makes sense. I was referring to k-values 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 n-range 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post EdH Factoring 25 2018-03-26 15:59 devarajkandadai Number Theory Discussion Group 0 2018-02-08 05:15 Peter Hackman Factoring 7 2009-10-26 18:27 Golem86 Factoring 11 2007-07-17 18:08 hallstei Factoring 5 2005-04-19 11:58

All times are UTC. The time now is 07:55.

Tue Jan 19 07:55:14 UTC 2021 up 47 days, 4:06, 0 users, load averages: 2.87, 2.19, 1.93