mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2008-05-16, 11:34   #1
michaf
 
michaf's Avatar
 
Jan 2005

1DF16 Posts
Default 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)
michaf is offline   Reply With Quote
Old 2008-05-18, 06:47   #2
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

11·929 Posts
Default

Quote:
Originally Posted by michaf View Post
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
gd_barnes is offline   Reply With Quote
Old 2008-05-18, 23:08   #3
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by michaf View Post
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?
geoff is offline   Reply With Quote
Old 2008-05-18, 23:45   #4
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

11·929 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2008-05-19, 00:41   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2008-05-19, 04:19   #6
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

27EB16 Posts
Default

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
gd_barnes is offline   Reply With Quote
Old 2008-05-19, 05:03   #7
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

11·929 Posts
Default

Quote:
Originally Posted by michaf View Post
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
gd_barnes is offline   Reply With Quote
Old 2008-05-19, 05:46   #8
michaf
 
michaf's Avatar
 
Jan 2005

479 Posts
Default

There is indeed one square value of k: 16641

Quote:
Originally Posted by gd_barnes View Post
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
michaf is offline   Reply With Quote
Old 2008-05-19, 17:46   #9
michaf
 
michaf's Avatar
 
Jan 2005

479 Posts
Default

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 :)
michaf is offline   Reply With Quote
Old 2008-05-19, 21:31   #10
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
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.
geoff is offline   Reply With Quote
Old 2008-05-20, 03:45   #11
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

11×929 Posts
Default

Quote:
Originally Posted by geoff View Post
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
gd_barnes is offline   Reply With Quote
Reply

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 2018-03-26 15:59
primitive roots- when the base is a quadratic algebraic integer devarajkandadai Number Theory Discussion Group 0 2018-02-08 05:15
trial division over a factor base Peter Hackman Factoring 7 2009-10-26 18:27
GNFS - Factor Base Golem86 Factoring 11 2007-07-17 18:08
Quadratic Sieve - How large should the factor base be? hallstei Factoring 5 2005-04-19 11:58

All times are UTC. The time now is 06:47.

Wed Oct 21 06:47:36 UTC 2020 up 41 days, 3:58, 0 users, load averages: 1.04, 1.28, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.