mersenneforum.org - Algebraic factor issues base 24

mersenneforum.org (https://www.mersenneforum.org/index.php)

- Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)

- - Algebraic factor issues base 24 (https://www.mersenneforum.org/showthread.php?t=10279)

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)

[quote=michaf;133492]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)[/quote]

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

[QUOTE=michaf;133492]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)[/QUOTE]

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?

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

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.

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! :smile:

Gary

[quote=michaf;133357]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
[/code][/quote]

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

There is indeed one square value of k: 16641

[QUOTE=gd_barnes;133618]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[/QUOTE]

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 :)

[QUOTE=gd_barnes;133625]2. The remaining n-values make GFNs and as such, will not be considered.[/QUOTE]

I don't think there is any necessary reason to exclude these cases. For example in michaf's case for Sierpinski base 24:

[QUOTE=michaf]there is There is indeed one square value of k: 16641[/QUOTE]

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.

[quote=geoff;133705]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.[/quote]

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

[quote=michaf;133684]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 :)[/quote]

Very good. Now see if you can come up with the specific algebraic factors for k=6, which, I think, clearly has algebraic factors but doesn't fit the definitions that we've come up with so far.

Riesel base 24 is turning out to be a VERY strange base! :smile:

Gary

[QUOTE=gd_barnes;133729]Very good. Now see if you can come up with the specific algebraic factors for k=6, which, I think, clearly has algebraic factors but doesn't fit the definitions that we've come up with so far.

Riesel base 24 is turning out to be a VERY strange base! :smile:

Gary[/QUOTE]

For even n:

[TEX]6*24^n-1 = 2*3 * 8^n*3^n - 1 = 2*3 * 2^{3n} * 3^n - 1
= 2^{(3n+1)} * 3^{(n+1)} -1
[/TEX]

insert n=2q for even n:

[TEX]2^{(3*2q+1)} * 3^{(2q+1)} -1 = 2^{(6q+1)} * 3^{(2q+1)} -1[/TEX]

[TEX]2^{(6q+1)}[/TEX] is always even
[TEX]3^{(2q+1)}[/TEX] is always uneven
[TEX]2^{(6q+1)} * 3^{(2q+1)}[/TEX] is always uneven
[TEX]2^{(6q+1)} * 3^{(2q+1)} -1 [/TEX] is always even

But I can't get a grip on the uneven n's yet :)

[quote=michaf;133797]For even n:

[tex]6*24^n-1 = 2*3 * 8^n*3^n - 1 = 2*3 * 2^{3n} * 3^n - 1
= 2^{(3n+1)} * 3^{(n+1)} -1
[/tex]

insert n=2q for even n:

[tex]2^{(3*2q+1)} * 3^{(2q+1)} -1 = 2^{(6q+1)} * 3^{(2q+1)} -1[/tex]

[tex]2^{(6q+1)}[/tex] is always even
[tex]3^{(2q+1)}[/tex] is always uneven
[tex]2^{(6q+1)} * 3^{(2q+1)}[/tex] is always uneven
[tex]2^{(6q+1)} * 3^{(2q+1)} -1 [/tex] is always even

But I can't get a grip on the uneven n's yet :)[/quote]

I have more time tonight then I did the last couple of nights. I have to disagree here:

If 2^(6q+1) is always even and 3^(2q+1) is always uneven, then:

2^(6q+1)*3^(2q+1) should be always even (not uneven)

hence 2^(6q+1)*3^(2q+1) should always be uneven, i.e. odd

What we DO know about even n, even though it is always odd, is that it ALWAYS has a factor of 5!

So, like you said, it's the uneven (odd) n that we are concerned about. For me, when all else fails, then try reverse engineering, which is how I came up with quite a few of the algebraic factors that I did on the bases. Here goes:

6*24^1-1 = 11 * 13
6*24^3-1 = 287 * 289
6*24^5-1 = 6911 * 6913
6*24^7-1 = 165887 * 165889

Notice a pattern here? How about this:

(2^0*12^1-1)*(2^0*12^1+1)
(2^1*12^2-1)*(2^1*12^2+1)
(2^2*12^3-1)*(2^2*12^3+1)
(2^3*12^4-1)*(2^3*12^4+1)

-or- to generalize it:
{2^[(n-1)/2]*12^[(n+1)/2]-1}*{2^[(n-1)/2]*12^[(n+1)/2]+1}

-or- to make it easier, let n=2m+1 and you have:

[2^m*12^(m+1)-1]*[2^m*12^(m+1)+1]

Therefore k=6 can be eliminated as follows:

For even n: factor of 5

For odd n, let n=2m+1; factors to:
[2^m*12^(m+1)-1]*[2^m*12^(m+1)+1]

This makes me wonder if there are other k-values with this type of unusual algebraic factors. If you have any other k-values that ONLY have numeric factors of 2 and 3 in them, you might check Alperton's site [URL="http://www.alpertron.com.ar/ECM.HTM"]here[/URL] and look for patterns in the factors for each n-value.

k=6 will be removed from the web pages and the count remaining dropped by one.

:smile: Gary

I have renamed this thread to be "algebraic factor issues base 24". It includes all posts in this thread originally titled "sr2sieve / sierpinksi base 24" by Micha about Sierp base 24 issues and all posts in the primes thread related to Riesel base 24 issues that I moved here.

Gary

[QUOTE=gd_barnes;133812]
With THREE different sets of algebraic factors, this base has been some kind of challenge! :smile:
Gary[/QUOTE]

In short: WOW :smile:

In removing all the k's with algebraic factors, I noticed they were also very low weight, about 200-300 terms per k (as compared to about 2000-4000 for others

Well Micha, you're not going to believe this, but I've generalized the algebraic factors even further and was able to eliminate 11 more k-values in addition to what I've already listed!! :smile:

I erred when I jumped the gun by saying that k=24*m^2 gives k's with algebraic factors. That is true but I didn't take it far enough. Here are the conditions that not only eliminate all 13 of those k-values but they also eliminate the 2 k-values of 6 and 486 as stated in the last post plus 11 more. It technically eliminates a total of 26 k-values so my original k=24*m^2 condition was only half of the 'puzzle'. Here are the generalized conditions and algebraic factors:

All k=6*m^2 where k==(6 mod 10) contain factors as follows and can be eliminated from your search:

even n; factor of 5

odd n; let k=6*m^2 and let n=2*q-1; factors to:

[m*3^q*2^(3q-1) - 1] *
[m*3^q*2^(3q-1) + 1]

It seems so easy in retrospect but I got started on the wrong path to begin with and made it hard.

So now, in addition to the 13 previous k-values that I listed for k=24*m^2, these conditions also eliminate the following k-values:

6, 486, 726, 2166, 5046, 5766, 9126, 10086, 14406, 15606, 20886, 22326, and 28566.

This now drops us down to 142 k-values remaining at n=25K and also simplifies things quite a bit. Now, there are technically only 2 separate conditions that have algebraic factors. The web pages will be updated shortly.

Now you know why so many were so low weight. They actually had ZERO weight! :smile:

I've now closely inspected many of the remaining 142 k-values. There should be no more with algebraic factors.

OK, I'm done with this now! :smile:

Gary

Gee :smile:

That's a load of elimination in a short time now!
I'll be sieving the rest to an optimum level for n=50k, and then continue prp-ing.