 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Conjectures 'R Us (https://www.mersenneforum.org/forumdisplay.php?f=81)
-   -   Riesel/Sierp base 2 even-k/even-n/odd-n testing (https://www.mersenneforum.org/showthread.php?t=9830)

 gd_barnes 2008-01-08 06:27

Riesel/Sierp base 2 even-k/even-n/odd-n testing

[quote=Jean Penné;122412]

About the second question, when the base is a power of two, there may be MOB k values which are also power of two, and then the candidates are not only Generalized Fermat Numbers, but very Fermat Numbers, so, I think these k's should be excluded (It is conjectured that there are a finite number of Fermat primes, and most of the mathematicians believe that F4 = 65537 is the largest one...).
As I remarked in another thread, proving that F4 is the largest Fermat prime is equivalent to proving that 65536 is an even Sierpinski number...
But, if so, the covering set would be infinite, because it is well known that Fermat numbers are pairwise coprime...

Regards,
Jean[/quote]

(Edit note: MOB = multiples of base)

Robert, Citrix, Axn, Geoff, Masser, or other people with intimate knowledge of the math's behind the conjectures, here is what I would propose (if it has not been proposed already) that Jean agrees with:

In order to prove the Sierpinski conjecture for any base, all Generalized Fermat #'s as well as very Fermat #'s, i.e. any form that reduces to 2^n+1, should be excluded from those conjectures.

In a nutshell, here is what I'm working towards as determining the Riesel/Sierpinski conjecture proofs on the "Conjectures 'R Us" web pages:

1. All generalized Fermat #'s (18*18^n+1) and very Fermat #'s (65536*4^n+1 or 65536*16^n+1) will be excluded from the conjectures.

2. Any k that obtains a full covering set in any manner from ALGEBRAIC factors will be excluded. In many instances, this includes k's where there is a partial covering set of numeric factors (or a single numeric factor) and a partial covering set of algebraic factors that combine to make a full covering set.

3. All k below the lowest k found to have a NUMERIC covering set must have a prime including multiples of the base (MOB) but excluding the conditions in #1 and #2 above. I will add MOB and exclude GFn's in the near future on the pages. There are very few MOB if GFNs are excluded.

4. All n must be >= 1.

All input and opinions are welcome.

Citrix, if you think this is misplaced, feel free to move it around somewhere.

Thanks,
Gary

 Jean Penné 2008-01-08 20:33

Liskovets-Gallot numbers are beautiful for us!

Hi,

[URL]http://www.primepuzzles.net/problems/prob_036.htm[/URL]

To be short, the Liskovets assertion is :

There are some k values such that k*2^n+1 is composite for all n values of certain fixed parity, and some k values such that k*2^n-1 is composite for all n values of certain fixed parity.

It is almost evident that these k values must be searched only amongst the multiples of 3 (the assertion is trivial if 3 does not divide k) :

If k == 1 mod 3, then 3 | k*2^n-1 if n is even, and 3 | k*2^n+1 if n is odd.
If k == 2 mod 3, then 3 | k*2^n+1 if n is even, and 3 | k*2^n-1 if n is odd.

Almost immediately after, Yves Gallot discovered the first four Liskovets-Gallot numbers ever produced :

k*2^n+1=composite for all n=even: k=66741
k*2^n+1=composite for all n=odd: k=95283
k*2^n-1=composite for all n=even: k=39939
k*2^n-1=composite for all n=odd: k=172677

And Yves said that "I conjecture that 66741, 95283, 39939, ... and 172677 are the smallest solutions for the forms - having no algebraic factorization (such as 4*2^n-1 or 9*2^-1) - but I can't prove it."

For several reasons, I think it would be interesting for us to coordinate the search in order to prove these four conjectures :

1) They involve only k values that are multiples of 3, so the success will no more be depending of the SoB or Rieselsieve one.

2) For the n even Sierpinski case, only k = 23451 and k = 60849 are remaining, with n up to more than 1,900,000 that is to say there are only two big primes to found, then the conjecture is proven!

3) For the n even Riesel (third line above) there are only four k values remaining : 9519, 14361, 19401 and 20049, although the search is only at the beginning!

4) For the two remaining n odd Sierpinski / Riesel (which can be tranlated as
base 4, k even, and doubling the Gallot values : 190566 for k*4^n+1, 345354 for k*4^n-1) I began to explore the problem, by eliminating all k's yielding a prime for n < 4096, eliminating the perfect square k values for Riesel, eliminating the MOB that are redondant, etc...

Finally, there were 42 k values remaining for +1, 114 for -1, and after sieving rapidly with NewPGen, and LLRing up to ~32K, I have now 21 values remaining for +1 and 37 values for -1.

Regards,
Jean

 gd_barnes 2008-01-10 19:15

[quote=Jean Penné;122480]Hi,

[URL]http://www.primepuzzles.net/problems/prob_036.htm[/URL]

To be short, the Liskovets assertion is :

There are some k values such that k*2^n+1 is composite for all n values of certain fixed parity, and some k values such that k*2^n-1 is composite for all n values of certain fixed parity.

It is almost evident that these k values must be searched only amongst the multiples of 3 (the assertion is trivial if 3 does not divide k) :

If k == 1 mod 3, then 3 | k*2^n-1 if n is even, and 3 | k*2^n+1 if n is odd.
If k == 2 mod 3, then 3 | k*2^n+1 if n is even, and 3 | k*2^n-1 if n is odd.

Almost immediately after, Yves Gallot discovered the firt four Liskovets-Gallot numbers ever produced :

k*2^n+1=composite for all n=even: k=66741
k*2^n+1=composite for all n=odd: k=95283
k*2^n-1=composite for all n=even: k=39939
k*2^n-1=composite for all n=odd: k=172677

And Yves said that "I conjecture that 66741, 95283, 39939, ... and 172677 are the smallest solutions for the forms - having no algebraic factorization (such as 4*2^n-1 or 9*2^-1) - but I can't prove it."

For several reasons, I think it would be interesting for us to coordinate the search in order to prove these four conjectures :

1) They involve only k values that are multiples of 3, so the success will no more be depending of the SoB or Rieselsieve one.

2) For the n even Sierpinski case, only k = 23451 and k = 60849 are remaining, with n up to more than 1,900,000 that is to say there are only two big primes to found, then the conjecture is proven!

3) For the n even Riesel (third line above) there are only four k values remaining : 9519, 14361, 19401 and 20049, although the search is only at the beginning!

4) For the two remaining n odd Sierpinski / Riesel (which can be tranlated as
base 4, k even, and doubling the Gallot values : 190566 for k*4^n+1, 345354 for k*4^n-1) I began to explore the problem, by eliminating all k's yielding a prime for n < 4096, eliminating the perfect square k values for Riesel, eliminating the MOB that are redondant, etc...

Finally, there were 42 k values remaining for +1, 114 for -1, and after sieving rapidly with NewPGen, and LLRing up to ~32K, I have now 21 values remaining for +1 and 37 values for -1.

Regards,
Jean[/quote]

I responded in the "Conjecture 'R Us" thread to this.

Gary

 japelprime 2008-01-10 21:44

I will probably reserve more of 2036 base 9 number (if no prime will be in my range) but can then slow down on LLR testing to free upp
one older AMD PC to help on Liskovets-Gallot numbers. Maybe not wery fast PC for LLR but will do its job 24/7.
Back to this later.

 Citrix 2008-01-13 04:21

Jean,

I looked at the parity thing you mentioned. It sounds interesting, perhaps we can go to higher bases once we are done with 256.

I also looked at all k's 1-32, that are supper fast for all possible parities up to 2^100. There were some really low weight sequences and some high weight sequences. Do you think we might have similar luck like RPS or 15K with some of these high weight or low weight sequences and possibly find a 10M prime?

What do you think? If you or any one else is interested please let me know.

Thanks:smile:

 Citrix 2008-01-13 05:08

Low weight Reisel
K=29 not included as it is already low weight.
[code]
k*2^m*(2^i)^n-1 // last column is the candidates left, approx estimate of weight
19 9 17 163
19 9 34 332
15 8 35 244
15 28 35 243
19 9 51 496
21 15 55 480
19 2 63 549
21 45 65 416
23 39 65 554
19 43 68 664
21 47 69 613
27 15 69 623
15 1 70 456
15 7 70 384
15 15 70 481
15 21 70 453
15 29 70 483
15 35 70 483
15 43 70 482
15 49 70 483
15 57 70 388
15 63 70 485
15 31 74 457
[/code]

 Jean Penné 2008-01-13 07:26

[QUOTE=Citrix;122746]Jean,

I looked at the parity thing you mentioned. It sounds interesting, perhaps we can go to higher bases once we are done with 256.

I also looked at all k's 1-32, that are supper fast for all possible parities up to 2^100. There were some really low weight sequences and some high weight sequences. Do you think we might have similar luck like RPS or 15K with some of these high weight or low weight sequences and possibly find a 10M prime?

What do you think? If you or any one else is interested please let me know.

Thanks:smile:[/QUOTE]

Harsh,

Presently, I am more interested in trying to prove one or more of these four mathematical conjectures, than to find large primes (although it may be a subproduct).
Moreover, I hope we will not need to find a 10M prime before proving at least one of them!
So, perhaps it would be better to restrict this project to base 4 for now, and not to dissipate our efforts too much...
But, indeed there is place for other similar projects!

Regards,
Jean

 gd_barnes 2008-01-14 19:19

[quote=Jean Penné;122480]Hi,

[URL]http://www.primepuzzles.net/problems/prob_036.htm[/URL]

To be short, the Liskovets assertion is :

There are some k values such that k*2^n+1 is composite for all n values of certain fixed parity, and some k values such that k*2^n-1 is composite for all n values of certain fixed parity.

It is almost evident that these k values must be searched only amongst the multiples of 3 (the assertion is trivial if 3 does not divide k) :

If k == 1 mod 3, then 3 | k*2^n-1 if n is even, and 3 | k*2^n+1 if n is odd.
If k == 2 mod 3, then 3 | k*2^n+1 if n is even, and 3 | k*2^n-1 if n is odd.

Almost immediately after, Yves Gallot discovered the firt four Liskovets-Gallot numbers ever produced :

k*2^n+1=composite for all n=even: k=66741
k*2^n+1=composite for all n=odd: k=95283
k*2^n-1=composite for all n=even: k=39939
k*2^n-1=composite for all n=odd: k=172677

And Yves said that "I conjecture that 66741, 95283, 39939, ... and 172677 are the smallest solutions for the forms - having no algebraic factorization (such as 4*2^n-1 or 9*2^-1) - but I can't prove it."

For several reasons, I think it would be interesting for us to coordinate the search in order to prove these four conjectures :

1) They involve only k values that are multiples of 3, so the success will no more be depending of the SoB or Rieselsieve one.

2) For the n even Sierpinski case, only k = 23451 and k = 60849 are remaining, with n up to more than 1,900,000 that is to say there are only two big primes to found, then the conjecture is proven!

3) For the n even Riesel (third line above) there are only four k values remaining : 9519, 14361, 19401 and 20049, although the search is only at the beginning!

4) For the two remaining n odd Sierpinski / Riesel (which can be tranlated as
base 4, k even, and doubling the Gallot values : 190566 for k*4^n+1, 345354 for k*4^n-1) I began to explore the problem, by eliminating all k's yielding a prime for n < 4096, eliminating the perfect square k values for Riesel, eliminating the MOB that are redondant, etc...

Finally, there were 42 k values remaining for +1, 114 for -1, and after sieving rapidly with NewPGen, and LLRing up to ~32K, I have now 21 values remaining for +1 and 37 values for -1.

Regards,
Jean[/quote]

Jean,

Is there any reason that we are not testing even k's (i.e. multiples of the base) with these conjectures? If a k is even but is not divisible by 4, it yields a different set of factors and prime than any other odd k.

I am testing the Sierp odd-n conjecture of k=95283. Can you tell me how you arrived at 21 k-values remaining at n=32K? I have now tested up to n=56K. I just now finished sieving up to n=200K and am starting LLRing now.

At n=56K, I show 22 odd k's and 8 even k's remaining that are not redundant with other k's remaining; for a total of 30 k's.

At n=32K, I showed 26 odd k's and 9 even k's remaining; for a total of 35 k's.

I checked the top-5000 site for previous smaller primes and there were none for these k's so I wonder why you have less k's remaining than me.

Here are the k's that I show remaining at n=32K, both odd and even, and primes that I found for n=32K-56K for the Sierp odd-n conjecture:

[code]
2943
9267
17937 prime n=53927
24693
26613
29322 even
32247
35787 prime n=36639
37953
38463
39297
43398 even
46623
46902 even
47598 even
50433
53133
60357
60963
61137
61158 even; prime n=48593
62307 prime n=44559
67542 even
67758 even
70467
75183 prime n=35481
78753
80463
83418 even
84363
85287
85434 even
91437
93477
93663
[/code]

Thanks,
Gary

 Jean Penné 2008-01-14 21:17

[QUOTE=gd_barnes;122833]Jean,

Is there any reason that we are not testing even k's (i.e. multiples of the base) with these conjectures? If a k is even but is not divisible by 4, it yields a different set of factors and prime than any other odd k.

I am testing the Sierp odd-n conjecture of k=95283. Can you tell me how you arrived at 21 k-values remaining at n=32K? I have now tested up to n=56K. I just now finished sieving up to n=200K and am starting LLRing now.

At n=56K, I show 22 odd k's and 8 even k's remaining that are not redundant with other k's remaining; for a total of 30 k's.

At n=32K, I showed 26 odd k's and 9 even k's remaining; for a total of 35 k's.

I checked the top-5000 site for previous smaller primes and there were none for these k's so I wonder why you have less k's remaining than me.

Here are the k's that I show remaining at n=32K, both odd and even, and primes that I found for n=32K-56K for the Sierp odd-n conjecture:

[code]
2943
9267
17937 prime n=53927
24693
26613
29322 even
32247
35787 prime n=36639
37953
38463
39297
43398 even
46623
46902 even
47598 even
50433
53133
60357
60963
61137
61158 even; prime n=48593
62307 prime n=44559
67542 even
67758 even
70467
75183 prime n=35481
78753
80463
83418 even
84363
85287
85434 even
91437
93477
93663
[/code]

Thanks,
Gary[/QUOTE]

In the definitions of these four conjectures, the k multipliers must be odd!
For example : 46902*2^n+1 is the same as 23451*2^(n+1)=+1 and if n is odd, n+1 is even, so, you are testing an even exponents candidate!
So, the 8 even k's remaining are relevant to the even n conjecture, and not to the odd n one...

Also, I tested k = 46623 up to n = 79553 and found a prime, so me are almost matching now... I am terminating to gather my results, and will send them to this thread as soon as possible.
Regards,
Jean

 gd_barnes 2008-01-14 22:42

[quote=Jean Penné;122841]In the definitions of these four conjectures, the k multipliers must be odd!
For example : 46902*2^n+1 is the same as 23451*2^(n+1)=+1 and if n is odd, n+1 is even, so, you are testing an even exponents candidate!
So, the 8 even k's remaining are relevant to the even n conjecture, and not to the odd n one...

Also, I tested k = 46623 up to n = 79553 and found a prime, so me are almost matching now... I am terminating to gather my results, and will send them to this thread as soon as possible.
Regards,
Jean[/quote]

Well, DUH!! :blush: I will remove the even k's that obviously go with the even-n conjecture from my LLRing. :rolleyes:

Gary

 gd_barnes 2008-01-15 18:37

I have now run the Sierp odd-n conjectures up to n=115K and will be continuing on to n=200K sometime next week after completing some sieving for conjectures team drive #1 and a couple of other things. Below are the k's left at n=32K with primes found for n=32K-115K.

I decided to leave the even k's in because in effect it is testing the even conjecture for all k < 95282/2=47641 and I had already sieved them. That should save a lot of effort on that side.

[code]
2943 prime n=108041
9267
17937 prime n=53927
24693
26613 prime n=89749
29322 even; prime n=91367
32247
35787 prime n=36639
37953
38463 prime n=58753
39297
43398 even; prime n=72873
46623 prime n=79553
46902 even
47598 even; prime n=105899
50433
53133
60357
60963 prime n=73409
61137
61158 even; prime n=48593
62307 prime n=44559
67542 even
67758 even
70467
75183 prime n=35481
78753 prime n=63761
80463
83418 even; prime n=80593
84363
85287
85434 even
91437
93477 prime n=63251
93663 prime n=82317
[/code]

Total of 14 odd k's and 4 even k's remaining.

So...based on this effort by itself, here are the statuses of the base 2 Sierp odd-n and even-n cojectures:

Odd-n:
14 k's remaining at n=115K from odd k's above. k's remaining:
9267
24693
32247
37953
39297
50433
53133
60357
61137
70467
80463
84363
85287
91437

Even-n:
47641<k<66741: still needs to be tested.
k<=47641: 4 k's remaining at n=115K from even k's above. k's remaining converted to odd-k:
23451
33771
33879
42717

Edit: I just now realized that it was already stated that only k=23451 and 60849 are remaining on the even-n side as a result of the Sierp base 4 project. OK, NEXT time I'll remove the even k's from my testing. Ergh!

Gary

All times are UTC. The time now is 22:27.