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

 2010-01-01, 20:14 #23 Citrix     Jun 2003 30538 Posts Here is the smallest number with this covering set. b=201446503145165177 (18 digits)
2016-11-23, 19:18   #24
sweety439

Nov 2016

281910 Posts
k=1 and k=2

According to the CRUS link, some k=2 primes are known:

Riesel:
b (n)
107 (21910)
170 (166428)
278 (43908)
303 ?
383 (20956)
515 (58466)
522 ?
578 ?
581 ?
590 (15526)
647 (21576)
662 (16590)
698 (127558)
704 (62034)
845 (39406)
938 (40422)
969 (24096)
989 (26868)
992 ?
1019 ?

Sierpinski:
b (n)
101 (192275)
206 (46205)
218 ?
236 ?
257 (12183)
305 (16807)
365 ?
383 ?
461 ?
467 (126775)
542 ?
578 (44165)
626 (174203)
647 ?
695 (94625)
752 (26163)
773 ?
788 (72917)
801 ? (the only not-started base with k=2 remaining, what is the final test limit?)
836 ?
869 (49149)
878 ?
887 (27771)
899 (15731)
908 ?
914 ?
917 ?
932 (13643)
947 ?
1004 ?

Although I know exactly which bases have k=2 remaining (since we does not include GFN, no bases have k=1 remaining), I also want to know exactly which bases have k=3, k=4, k=5, k=6, ..., k=12 remaining (even including the not-started base and the bases which have conjectured k less than the k). e.g. I know some bases (like S718 and S912) have k=3 remaining, but how about a not-started base S358? I cannot find a k=3 prime for S358 (this is the first such Sierpinski base). Besides, I tests all Sierpinski bases b<=400 for k=10 and b<=600 for k=12, but I cannot find prime for some bases, see the test files.
Attached Files
 Least k such that 12k^n+1 is prime.txt (4.1 KB, 237 views) Least k such that 10k^n+1 is prime.txt (2.7 KB, 238 views)

 2016-11-23, 20:35 #25 gd_barnes     May 2007 Kansas; USA 2·7·739 Posts Long ago I undertook an effort to search all k=2, 3, 4, 5, 6, and 7 to n=25K for bases <= 1030 regardless of how far the project has searched them. Although I personally searched no further I have continued to maintain lists of them and update them periodically with the search depth of the project and with primes found by the project. In the lists, I specify the bases remaining for each k, the search depth for each k, the # of k's remaining in the project conjecture for each base in question, and a list of bigger primes found for each base that was eliminated. I also specify which bases should not be searched due to trivial and algebraic factors. I think you will find my lists interesting. I will post them in the next couple of days.
2016-11-23, 22:30   #26
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·37·127 Posts

There existed some unrelated interest from other researchers to k=2.

I came across it when I had an email conversation with David Broadhurst and W.Keller concerning the "Divides Phi(*,2)" UTM Top20 category.
It turns out that for b = 11 (mod 12), 2*b^n+1 may (frequently) divide a Phi(b^m,2). For other b values and other k values, the divisibility of this sort is more more rare.

There are a few bases b for which no 2*b^n+1 primes are yet known.
Here is an abbreviated quote from Keller (who did this work with Broadhurst & I.Buechel)
Quote:
 I wanted to compare your upper limits with those I had reached some years ago before stopping my whole search, and to add information about a few bases q > 131 (in the same category) which I had also investigated, particularly q = 383, 467, 647, 947 and 67607. These five bases continued having no known prime at all. ... I could verify that I had searched q = 47 as far as to 246k, and q = 71 up to 261k. ... Also, much effort had been invested in q = 383 (433k), 467 (347k), 647 (322k), 947 (much less: 105k), 60607 (412k). Now, examining the files, near the end of the last one corresponding to q = 467 I casually noted something "irregular" - which on a closer look appeared to be this surprising entry: [Thu Dec 07 10:45:01 2006] 2*467^126775+1 is a prime.

Last fiddled with by Batalov on 2016-11-23 at 22:34

2016-11-24, 09:02   #27
gd_barnes

May 2007
Kansas; USA

2·7·739 Posts

Attached are my files for searches of k=2, 3, 4, 5, 6, and 7 for bases <= 1030 undertaken about 5 years ago. Here are the steps that I took to create the lists:
1. Use a PFGW sript to search all Riesel and Sierp bases for all six k's to n=5K.
2. Do some analysis to remove bases with trivial and algebraic factors as well as GFN's.
3. Do some sieving and test remaining bases up to n=25K.
4. Use the CRUS project to continually update them.

I have made every effort to keep these updated and synced up with CRUS but I could have missed something so anyone is welcome to double-check them. The file names should be self-explanatory. Here is an explanation of the columns in each file:

1. The k and base remaining.
2. The search depth of the k for that base.
3. The conjecture for that base.
4. The # of CRUS k's remaining for that base.*

*If the CRUS search depth of the base is different than the search depth for the k shown then the CRUS search depth will be shown next to the k's remaining in parenthesis.

*If the conjecture is less than the applicable k (meaning that CRUS has done no searching on the k) then the k's remaining reflect what the CRUS pages show as remaining PLUS the applicable k. In such cases I have searched the k/base to n=25K. This would only apply to k=5, 6, and 7 where the base conjecture is 4 or 6. (There are no conjectures of k=2, 3, or 5.)

*If CRUS has not searched the base then "many" is shown in the k's remaining.

The following k's have bases with trivial or algebraic factors to make a full covering set -or- make GFN's and so are not included in the searches (similar to the CRUS conjectures):
Riesel k=2:
none
Riesel k=3:
b==(1 mod 2); factor of 2
Riesel k=4:
b==(1 mod 3); factor of 3
b==(4 mod 5): odd n, factor of 5; even n, algebraic factors (see CRUS pages)
b=m^2 proven composite by full algebraic factors
Riesel k=5:
b==(1 mod 2); factor of 2
Riesel k=6:
b==(1 mod 5); factor of 5
b==(34 mod 35); covering set [5, 7]
b=24, 54, 294, and 864: even n, factor of 5; odd n, algebraic factors (see CRUS pages)
Riesel k=7:
b==(1 mod 2); factor of 2
b==(1 mod 3); factor of 3
Sierp k=2:
b==(1 mod 3); factor of 3
b=512 is a GFN with no known prime
Sierp k=3:
b==(1 mod 2); factor of 2
Sierp k=4:
b==(1 mod 5); factor of 5
b==(14 mod 15); covering set [3, 5]
b=625 proven composite by full algebraic factors
b=32, 512, and 1024 are GFN's with no known prime
Sierp k=5:
b==(1 mod 2); factor of 2
b==(1 mod 3); factor of 3
Sierp k=6:
b==(1 mod 7); factor of 7
b==(34 mod 35); covering set [5, 7]
Sierp k=7:
b==(1 mod 2); factor of 2

See the files for the k's remaining and their search depth. In a synopsis, here are the number of bases <= 1030 remaining for each k that do not have a prime:
Riesel k=2: 6
Riesel k=3: 2
Riesel k=4: 12
Riesel k=5: 2
Riesel k=6: 12
Riesel k=7: 9
Sierp k=2: 16
Sierp k=3: 2
Sierp k=4: 19
Sierp k=5: 4
Sierp k=6: 9
Sierp k=7: 1*

*Sierp k=7 has only one base remaining, 1004. The conjecture for the base is k=4 and therefore k=7 was only searched by me to n=25K. It would be interesting if someone would like to undertake an effort to search 7*1004^n+1 to n=100K or 200K to see if we can eliminate all bases for k=7. :-)

Here is a list of all primes found for n>5000:
Code:
base (n-value)
Riesel k=2:
107 (21910)
170 (166428)
233 (8620)
278 (43908)
383 (20956)
515 (58466)
590 (15526)
618 (8610)
627 (7176)
647 (21576)
662 (16590)
698 (127558)
704 (62034)
785 (9670)
845 (39406)
872 (6036)
938 (40422)
969 (24096)
989 (26868)

Riesel k=3:
432 (16002)

Riesel k=4:
72 (1119849)
212 (34413)
218 (23049)
270 (89661)
422 (21737)
480 (93609)
527 (46073)
537 (7287)
566 (23873)
582 (5841)
686 (16583)
758 (15573)
783 (12507)
786 (8001)
800 (33837)
947 (10055)
965 (8755)
998 (8427)

Riesel k=5:
14 (19698)
68 (13574)
196 (9849)
254 (15450)
800 (20508)
986 (5580)

Riesel k=6:
258 (212134)
272 (148426)
307 (26262)
354 (25561)
433 (283918)
635 (36162)
678 (40858)
692 (45446)
719 (20551)
783 (5022)
857 (23082)
867 (61410)
972 (36702)
999 (8887)
1025 (8958)

Riesel k=7:
68 (25395)
332 (15221)
338 (42867)
362 (146341)
458 (9823)
488 (33163)
566 (164827)
866 (7227)
980 (50877)
986 (12505)
1016 (23335)

Sierp k=2:
101 (192275)
167 (6547)
206 (46205)
257 (12183)
287 (5467)
305 (16807)
368 (7045)
467 (126775)
578 (44165)
626 (174203)
695 (94625)
752 (26163)
758 (8309)
788 (72917)
869 (49149)
887 (27771)
899 (15731)
932 (13643)
954 (8100)

Sierp k=3:
358 (9560)
996 (6549)

Sierp k=4:
77 (6098)
83 (5870)
107 (32586)
227 (13346)
257 (160422)
264 (9647)
355 (10989)
410 (144078)
440 (56086)
452 (14154)
470 (5218)
482 (30690)
542 (15982)
579 (67775)
608 (20706)
635 (11722)
650 (96222)
679 (69449)
737 (269302)
740 (58042)
818 (7726)
934 (101403)
962 (84234)

Sierp k=5:
350 (20391)
536 (8789)
554 (10629)
662 (13389)
926 (40035)

Sierp k=6:
108 (16317)
129 (16796)
409 (369832)
587 (24119)
614 (7480)
643 (164915)
669 (5450)
704 (5282)
762 (11151)
789 (27296)
919 (5092)
929 (9148)
969 (5888)
977 (6404)
986 (21633)
1018 (9943)

Sierp k=7:
398 (17472)
632 (8446)
836 (5700)
What I initially found interesting about these efforts is that there are few bases remaining for most k's and very few remaining for almost all odd k's (mainly since odd bases have a trivial factor of 2 for such k's).

Theoretically someone could reverse this project and have k-values with conjectured bases. Such bases would be conjectured to be the lowest base with a full covering set of numeric factors for each k. Of course this would be extraordinarily difficult to determine for k=2 and 3. But then you would have k=4, which is trivial since base=14 would be the conjecture and would be easily proven on both sides to be the lowest such base since all lower bases have a prime for k=4 (or a trivial set of factors). But it would be an interesting mathematical excercise to attempt to determine such conjectures for some of the more difficult k's. The problem with such a project is that the bases for each k would get very large very quickly and so would yield fewer primes and take much longer to search. (Imagine searching base=12345 for a small k!) Hence the project would quickly become less interesting than CRUS.

I did not desire to search beyond k=7 because, (see Riesel k=6 and Sierp k=4 above), as the k's get higher there becomes more and more bases with trivial factors and complex arrangements of covering sets and algebraic factors. k=8 would have gotten difficult on both sides with many combinations of algebraic factors. Therefore k=7 was a natural stopping point.

Nice effort Sweety. Your bases remaining and primes shown exactly match what I show for k=2. The attached files and this post should give you additional info. for furthering such efforts. One problem that I see for your k=10 and 12 files: You are including n=0 in the searches. CRUS requires that primes be n>=1. The reason for this is that n=0 makes the k become trivial for all bases and hence not interesting. For example k=14 would be eliminated for all Riesel bases because 13 is prime and k=18 would be eliminated for all bases on both sides since both 17 and 19 are prime.

I have updated the thread title to show k=1 thru 12.
Attached Files
 remain riesel-sierp k.zip (3.3 KB, 199 views)

Last fiddled with by gd_barnes on 2016-11-25 at 07:50

 2016-11-24, 12:08 #28 sweety439   Nov 2016 2,819 Posts I don't include n=0 in the searches. In these files, n=0 means no such prime exists, e.g. in the k=12 file, since 12*14^n+1 is always divisible by 13, no primes are of the form 12*14^n+1, and 12*142^n+1 is always divisible by 11 or 13, no primes are of the form 12*142^n+1, and 12*296^n+1 is always divisible by 7, 11, 13, or 19, no primes are of the form 12*296^n+1. Thus, in the file, the n of k=14, 27, 40, ..., 142, ..., 296, etc. are 0. Last fiddled with by sweety439 on 2016-11-24 at 12:30
 2016-11-24, 12:17 #29 sweety439   Nov 2016 2,819 Posts Thank you, gd_barnes. However, your file still miss some primes, such as 4*737^269302+1 and 4*72^1119849-1. Besides, you only tested 2<=k<=7 for bases 2<=b<=1030, but I want the list of the primes with n>1000 (you only listed n>5000) for 2<=k<=12, 2<=b<=1728 = 12^3 and remain bases for 2<=k<=12 and 2<=b<=1728 = 12^3. I am curious that why you stopped at b=1030. I only want the k's <= 12, I will not have you give the list of the primes and remain bases for k=13, 14, 15, 16, ..., you don't need to search beyond k=12. Last fiddled with by sweety439 on 2016-11-24 at 13:16
2016-11-24, 12:55   #30
sweety439

Nov 2016

2,819 Posts

I want a list like this.
Attached Files
 Sierp k=10.txt (2.8 KB, 240 views)

 2016-11-24, 14:56 #31 sweety439   Nov 2016 2,819 Posts See http://mersenneforum.org/showthread.php?t=15188 for bases 1031<=b<=2048. For Sierp k=8, all perfect cube bases and all bases =(1 mod 3), =(20 mod 21) should not be searched. For Riesel k=8, all perfect cube bases and all bases =(1 mod 7), =(20 mod 21) should not be searched. For Sierp k=9, all bases =(1 mod 2) and all bases =(1 mod 5) should not be searched. For Riesel k=9, all perfect square bases and all bases =(1 mod 2) and all bases =(4 mod 5) should not be searched. For Sierp k=10, all bases =(1 mod 11) and all bases =(32 mod 33) should not be searched. For Riesel k=10, all bases =(1 mod 3) and all bases =(32 mod 33) should not be searched. For Sierp k=11, all bases =(1 mod 2) and all bases =(1 mod 3) and all bases =(14 mod 15) should not be searched. For Riesel k=11, all bases =(1 mod 2) and all bases =(1 mod 5) and all bases =(14 mod 15) should not be searched. For Sierp k=12, all bases =(1 mod 13) and all bases =(142 mod 143) should not be searched. For Riesel k=12, all bases =(1 mod 11) and all bases =(142 mod 143) should not be searched. Also, for Riesel k=4, all bases =(4 mod 5) can be proven composite for partial algebraic factors and should not be searched. Last fiddled with by sweety439 on 2016-11-24 at 15:46
2016-11-24, 17:46   #32
gd_barnes

May 2007
Kansas; USA

2×7×739 Posts

Quote:
 Originally Posted by sweety439 Thank you, gd_barnes. However, your file still miss some primes, such as 4*737^269302+1 and 4*72^1119849-1. Besides, you only tested 2<=k<=7 for bases 2<=b<=1030, but I want the list of the primes with n>1000 (you only listed n>5000) for 2<=k<=12, 2<=b<=1728 = 12^3 and remain bases for 2<=k<=12 and 2<=b<=1728 = 12^3. I am curious that why you stopped at b=1030. I only want the k's <= 12, I will not have you give the list of the primes and remain bases for k=13, 14, 15, 16, ..., you don't need to search beyond k=12.
I did see those primes and you can see that those bases are not remaining in the bases remaining files. But you are correct, I did miss listing them in my primes files. Thanks for pointing it out. I will add them. After I did the initial search 5 years ago I have just manually updated the primes files and bases remaining files so it doesn't surprise me that I missed posting some primes.

You are asking a lot. I have all of the primes but digging up the primes for n=1K-5K would take a while to organize them. I did not search beyond b=1030 because that is as far as the CRUS project decided to go. We had to stop at some point. The project is already huge. I did not search beyond k=7 because...well...I didn't want to. It was an interesting effort but it wasn't that interesting and I grew tired of determining bases with trivial and algebraic factors. I'll leave it up to you to search b>1030 and k>7.

Last fiddled with by gd_barnes on 2016-11-24 at 17:52

 2016-11-24, 18:18 #33 sweety439   Nov 2016 2,819 Posts I will search all 1<=k<=12 and 2<=b<=1728 to 400K, but not now. Last fiddled with by sweety439 on 2016-11-24 at 18:20