mersenneforum.org k=1 thru k=12
 Register FAQ Search Today's Posts Mark Forums Read

2008-11-06, 04:14   #12
gd_barnes

May 2007
Kansas; USA

241058 Posts

Quote:
 Originally Posted by robert44444uk This k was generated from looking at (x^2)^n-1 factorisations -covering set is 3,5,17,257,641,65537,6700417 which I think is 32-cover. I do not think anyone has claimed it is the smallest k, it just comes from the smallest-cover.
Wouldn't this be a 64-cover?

3 covers 0mod2; 1mod2 remains
5 covers 3mod4; 1mod4 remains
17 covers 5mod8; 1mod8 remains
257 covers 9mod16; 1mod16 remains
65537 covers 17mod32; 1mod32 remains
641 covers 33mod64; 1mod64 remains
6700417 covers 1mod64; all covered

Hence factors repeat every 64 n.

I see that all factors except 641 and 6700417 were generated by the form 2^(2^q)+1 where q>=0. Two questions:

1. How do these factors of the form 2^(2^q)+1 relate to the (x^2)^n-1 factorizations that you are talking about?
2. How were 641 and 6700417 arrived at? Did they just happen to "pop out" as a result of looking for bases with covers that contained factors of the form in which you are talking about.

I know that 641 is a commonly occurring factor that pops out in GFN factorizations. I'm sure that has something to do with why it occurred here.

Here is what I need to understand what you mean: Put each factor here in the (x^2)^n-1 form that you described. That will help further research on this topic. For me, examples help the best.

Thanks,
Gary

Last fiddled with by gd_barnes on 2008-11-06 at 04:15

 2008-11-06, 07:24 #13 robert44444uk     Jun 2003 Oxford, UK 2·32·107 Posts Sorry for misleading if it is 64-cover - should have checked! There is unpublished work in this area, and for this reason I cannot really go into details on why these factorisations are key as it involves an unpublished theorem. But applying this to 128-cover, 256-cover etc has not been carried out to my knowledge. I will look into this a bit more this weekend
2008-11-06, 07:51   #14
gd_barnes

May 2007
Kansas; USA

132·61 Posts

Quote:
 Originally Posted by robert44444uk Somebody should also be looking at the theory - by checking higher (x^2)^2-1 factorisations, to see whether a smaller k is feasible, by running through bigcover.exe
Quote:
 Originally Posted by robert44444uk Sorry for misleading if it is 64-cover - should have checked! There is unpublished work in this area, and for this reason I cannot really go into details on why these factorisations are key as it involves an unpublished theorem. But applying this to 128-cover, 256-cover etc has not been carried out to my knowledge. I will look into this a bit more this weekend

It's definitely a 64-cover.

I'm confused now because you state one thing in one post and then imply the opposite in a follow-up post. At first, you say someone should be looking into the theory of (x^2)^2-1 factorizations but then you imply that we should not because there is unpublished work on the topic.

Two more questions:

1. What exactly is it that we can look into? A specific example or 2 would help.

2. I have a program called covering.exe. Where is the bigcover.exe program that you are referring to?

Thanks,
Gary

Last fiddled with by gd_barnes on 2008-11-06 at 07:54

 2008-11-06, 09:48 #15 kar_bon     Mar 2006 Germany 3×7×137 Posts don't know if your realized that the 5. Fermat number is F5 = 641 * 6700417 ! see here http://www.prothsearch.net/fermat.html Last fiddled with by kar_bon on 2008-11-06 at 09:49
2008-11-06, 10:09   #16
gd_barnes

May 2007
Kansas; USA

132·61 Posts

Quote:
 Originally Posted by kar_bon don't know if your realized that the 5. Fermat number is F5 = 641 * 6700417 ! see here http://www.prothsearch.net/fermat.html
Very interesting! I thought those factors looked familiar from somewhere. I had seen 641 many times when messing around with GFNs but I didn't specifically remember 6700417.

If you or Robert can tell me how that fact relates to what he is doing here, perhaps I can help find a smaller base with k=2 that has a covering set.

Gary

 2008-11-06, 10:11 #17 gd_barnes     May 2007 Kansas; USA 132·61 Posts Renamed thread to "k=1 and k=2" since discussion in this thread is related to both.
2008-11-06, 12:39   #18
robert44444uk

Jun 2003
Oxford, UK

2×32×107 Posts

Quote:
 Originally Posted by gd_barnes It's definitely a 64-cover. I'm confused now because you state one thing in one post and then imply the opposite in a follow-up post. At first, you say someone should be looking into the theory of (x^2)^2-1 factorizations but then you imply that we should not because there is unpublished work on the topic. Two more questions: 1. What exactly is it that we can look into? A specific example or 2 would help. 2. I have a program called covering.exe. Where is the bigcover.exe program that you are referring to? Thanks, Gary
Gary

Clumsy of me, the theory maintains that Fermat and GFN factors are key (not as stated), to find a specific, but not necessarily efficient b for any value of k, except k=1 or k=Mersenne.

The theory will be published in due course, but the key point is that if you find a fermat or GFN number with two primitive primes (fermat number wise) then a cover is possible. For k=2 we only look at Fermat numbers.

So if F6 has 2 new prime factors not in F1..F5 then that will provide a new cover. Each new Fermat number introduces at least 1 new odd prime as a factor.

Ex W. Keller

F5 = 641 . 6700417
F6 = 274177 . 67280421310721
F7 = 59649589127497217 . 5704689200685129054721
F8 = 1238926361552897 . P62
F9 = 2424833 . 7455602825647884208337395736200454918783366342657 . P99
F10 = 45592577 . 6487031809 . 4659775785220018543264560743076778192897 . P252
F11 = 319489 . 974849 . 167988556341760475137 . 3560841906445833920513 . P564

Will these produce a smaller b? The theorem only dealt with the fact that k=2=Sierpinski is possible, and did not look for the lowest b.

Bigcovering.exe is the big integer equivalent to covering.exe available from Robert Gerbicz's site.

2008-11-06, 12:40   #19
kar_bon

Mar 2006
Germany

3·7·137 Posts

Quote:
 Originally Posted by robert44444uk This k was generated from looking at (x^2)^n-1 factorisations -covering set is 3,5,17,257,641,65537,6700417 which I think is 32-cover. I do not think anyone has claimed it is the smallest k, it just comes from the smallest-cover.
BTW
the set are the first Fermat numbers F0 to F6 with their factors!!

PS
ok, Robert saw this!

Last fiddled with by kar_bon on 2008-11-06 at 12:41

 2008-11-11, 08:04 #20 gd_barnes     May 2007 Kansas; USA 132×61 Posts I have completed the "Riesel k=2 conjecture" up to n=10K for all bases <= 1024. 20 bases remain. See post 7. I have also completed the "Sierpinksi k=2 conjecture" up to n=10K for all bases <= 1024. Unlike the Riesel side where no bases could be removed with trivial factors, all b==(1 mod 3) were removed from the Sierp side with a trivial factor of 3. Despite this, the Sierp side is proving far more challenging with 30 vs. 20 bases remaining for the Riesels. Here are the 30 Sierpinski bases <= 1024 remaining that do NOT have a prime of the form 2*b^n+1 at n=10K: Code:  b 101 206 218 236 257 305 365 383 461 467 542 578 626 647 695 752 773 788 801 836 869 878 887 899 908 914 917 932 947 1004 Here are the primes for n>=1000 found for the effort: Code:  b (n) 758 (8309) 954 (8100) 368 (7045) 167 (6547) 287 (5467) 518 (4453) 38 (2729) 395 (2625) 635 (2535) 416 (2517) 353 (2313) 842 (1919) 698 (1885) 497 (1339) 867 (1280) 948 (1242) 104 (1233) 764 (1189) 992 (1179) 812 (1003) Interesting stats: Only 3 Riesel bases are remaining that are divisible by 3: 303, 522, 969 Only 1 Sierp base is remaining that is divisible by 3: 801 ZERO Riesel bases are remaining where b==(1 mod 3). Base 298 was the last to drop at n=4202. 3 bases are remaining on both Riesel and Sierp: 383, 578, 647 Base conjectures proofs: Riesel base 254 conjecture of k=4 is proven. The largest prime was 2*254^2866-1. Riesel base 669 conjecture of k=66 is proven. k=4 & 64 were eliminated with algebraic factors. The largest primes were 44*669^3132-1 and 2*669^2787-1. Sierp base 38 conjecture of k=14 is proven. The largest primes were 2*38^2729+1 and 9*38^21+1. Sierp base 167 conjecture of k=8 is proven. The largest primes were 2*167^6547+1 and 6*167^25+1. Below are bases where the only k remaining at n=10K is k=2 in order to prove the base conjecture. Note: While many lower bases have had all their k's tested to n=10K, a majority of the bases have only had other k-values (besides k=2) tested to n=2500. Riesel: Code:  b conjecture 278 14 515 44 704 4 845 46 969 96 (k=4 & 64 eliminated with algebraic factors) 989 4 1019 4 Sierpinski: Code:  b conjecture 101 16 206 22 305 16 461 8 626 10 752 16 869 4 899 4 914 4 917 16 1004 4 I'm still doing some testing on other k-values for these "difficult k=2 bases" up to n=10K. I will also be doing some testing up to n=25K for k=2 on some of the lower bases where k=2 is the only k remaining. Because they have been difficult to find a prime for the lowest possible k-value on a base, most of them are the hardest to find primes for many k-values and hence the most difficult to prove. Gary Last fiddled with by gd_barnes on 2008-11-11 at 08:16
 2009-12-26, 23:57 #21 Citrix     Jun 2003 1,579 Posts This was also discussed here: http://www.mersenneforum.org/showthread.php?t=6918 Anyway, A solution for k=2 Sierpinski is base 12576017419215635147 (This is not the smallest possible, just that I have not put enough effort into it.)
2009-12-27, 07:38   #22
gd_barnes

May 2007
Kansas; USA

132×61 Posts

Quote:
 Originally Posted by Citrix This was also discussed here: http://www.mersenneforum.org/showthread.php?t=6918 Anyway, A solution for k=2 Sierpinski is base 12576017419215635147 (This is not the smallest possible, just that I have not put enough effort into it.)
Nice work Citrix.

For clarification:

The covering set is:
{3, 5, 17, 257, 641, 65537, 6700417}

The period is n=64.

641 covers all n==(31 mod 64) and 6700417 covers all n==(63 mod 64) with the other 5 factors covering all of the rest.

Is that what you show?