|
Sierpinski and Riesel number (Fixed k, Variable base)
Has there been any work done to find S/R for fixed k and variable base?
eg. What is the lowest base=b for k=2 such that 2*b^n+1 is never prime? What k's can never be sierpinski numbers? Is there any proof to this. How does one generate the sierpinski base for a given k? (The same questions for Riesel side) |
[quote=Citrix;95709]What is the lowest base=b for k=2 such that 2*b^n+1 is never prime?[/quote]
b=4, as 2*1^1+1 and 2*2^1+1 and 2*3^1+1 are prime For all n : 2*4^n+1=2*1^n+1=2*1+1=3=0 (mod 3), so every number divisible by 3. Those questions seem not that interesting. |
The alternative Sierpinski/ Riesel works off b^n+/-k. Numbers of this form have the same properties as k*b^n+/-1. (trust me, this is the case!!) It is not so popular because you cannot prove the numbers prime, only prp.
But there is a whole community of people out there interested in finding just that... numbers that are prp but not prime. Check [url]http://www.primenumbers.net/prptop/prptop.php[/url] Henri lists the top 10000 prps and therefore it is easy to get into this list. But first you need to work out the probable Sierpinski/ Riesels for b^n+/-k, and then look at eliminating all k up to the chosen value. In this way you will find prps of some other k value such as L in b^n+/-L which Henri will be pleased to list |
[QUOTE=thommy;95721]b=4, as 2*1^1+1 and 2*2^1+1 and 2*3^1+1 are prime
For all n : 2*4^n+1=2*1^n+1=2*1+1=3=0 (mod 3), so every number divisible by 3. Those questions seem not that interesting.[/QUOTE] Thommy. 2 is not considered a sierpinski number for base 4, since the solution is trivial and no covering set is involved. |
For k=2 base=512 will never produce a prime! (2*512^n+1)
The following numbers below it remain The following values remain. 38 101 104 122 167 206 218 236 257 263 287 305 353 365 368 383 395 416 461 467 497 Will try to eliminate some. |
Found another lowest number =1307. 512 is a trivial solution, this is not.
All below checked to n=1000. 101 -->done to 4500 167 206 218 236 257 287 305 353 365 368 383 395 416 461 467 497 512 --> Can be removed trivially 518 542 578 626 635 647 695 698 752 758 764 773 788 801 812 836 842 867 869 878 887 899 908 914 917 932 947 948 954 992 1004 1052 1058 1073 1079 1082 1097 1112 1139 1142 1187 1193 1232 1262 1277 1286 Primes:xmastree: 2*104^1233+1 2*122^755+1 2*263^957+1 2*38^2729+1 2*821^945+1 2*845^877+1 2*926^765+1 2*968^917+1 2*1022^727+1 2*1028^669+1 2*1181^789+1 2*1253^697+1 2*1283^765+1 Will continue to prove 1307 is the smallest such number. Have not found a -1 number upto 250,000. Not sure if there is one. may be the same covering set as +1 can be used. Need help here, if anyone can offer.:surrender |
Here is the updated list. I would like to share the numbers with everyone, I am only working on a few, the rest are available. Could the moderators keep this thread clean.
:xmastree: :curtisc: [code] base n weight reserved by 101 4500 903 167 4000 235 206 4000 614 218 4000 465 236 4000 497 257 4000 187 Citrix 287 4000 260 305 4000 1049 365 4000 616 368 4000 379 383 10000 76 Citrix 461 4000 535 467 4000 288 518 4000 227 542 2500 158 Citrix 578 2500 472 626 2500 519 635 2500 669 647 2500 370 695 2500 655 752 2500 169 Citrix 758 2500 422 773 10000 83 Citrix 788 2500 665 801 2500 1440 836 2500 831 869 2500 818 878 2500 435 887 2500 495 899 2500 449 908 2500 451 914 2500 982 917 2500 297 932 2500 693 947 2500 547 954 3000 1697 1004 2000 394 1052 2000 232 1058 2000 606 1073 2000 413 1079 2000 631 1082 2000 606 1097 2000 407 1139 2000 567 1142 2000 370 1187 2000 362 1193 2000 311 1232 2000 528 1262 2000 372 1277 2000 187 Citrix 1286 2000 721 [/code] :help: |
Some recent primes!!!
2*497^1339+1 2*698^1885+1 2*764^1189+1 2*812^1003+1 2*842^1919+1 2*867^1280+1 2*867^1367+1 2*867^1856+1 2*948^1242+1 2*992^1179+1 2*1112^1091+1 2*353^2313+1 2*395^2625+1 2*416^2517+1 2*518^4453+1 2*635^2535+1 2*635^2937+1 2*1187^2907+1 2*1262^2575+1 2*1286^2145+1 [code] 101 5000 903 167 5000 235 206 5000 614 218 5000 465 236 5000 497 257 5000 187 Citrix 287 5000 260 305 5000 1049 365 5000 616 368 5000 379 383 10000 76 Citrix 461 5000 535 467 5000 288 542 5000 158 Citrix 578 3000 472 626 3000 519 647 3000 370 695 3000 655 752 5000 169 Citrix 758 3000 422 773 10000 83 Citrix 788 3000 665 801 3000 1440 836 3000 831 869 3000 818 878 3000 435 887 3000 495 899 3000 449 908 3000 451 914 3000 982 917 3000 297 932 3000 693 947 3000 547 954 5000 1697 1004 3000 394 1052 3000 232 1058 3000 606 1073 3000 413 1079 3000 631 1082 3000 606 1097 3000 407 1139 3000 567 1142 3000 370 1193 3000 311 1232 3000 528 1277 5000 187 Citrix Average wt=521.826087 Total wt=24004 [/code] |
[QUOTE=Citrix;96835]Found another lowest number =1307. 512 is a trivial solution, this is not.
Will continue to prove 1307 is the smallest such number. Have not found a -1 number upto 250,000. Not sure if there is one. may be the same covering set as +1 can be used. Need help here, if anyone can offer.:surrender[/QUOTE] Citrix, what is yor covering set for 1307? Obvioulsy there are not many n for which small factors cannot be found but there are 708 n values in the first 100,000 n which have no factors smaller than 50 million. For example, my NewPgen file reads (for the "Sierpinski": 51763650:P:0:1307:257 2 123 2 387 2 435 2 723 2 891 2 1131 2 1155 2 1443 2 1491 2 1515 2 1803 2 1947 2 1971 2 1995..... None of these are prime up to n=4731 |
[QUOTE=robert44444uk;96970]Citrix, what is yor covering set for 1307? Obvioulsy there are not many n for which small factors cannot be found but there are 708 n values in the first 100,000 n which have no factors smaller than 50 million.
For example, my NewPgen file reads (for the "Sierpinski": 51763650:P:0:1307:257 2 123 2 387 2 435 2 723 2 891 2 1131 2 1155 2 1443 2 1491 2 1515 2 1803 2 1947 2 1971 2 1995..... None of these are prime up to n=4731[/QUOTE] You are correct. Some error occured on my end. Thanks for pointing it out. But when I tried use Srsieve, it said all the numbers were eliminated. So I assumed it was a Sierpinksi number of this type. Though now when I run Srsieve it says some numbers are left. I will stick to values under 512 then. I don't think that 2 can be a sierpinki/riesel number for any base. Nor can any of the low k values. [code] 101 5000 903 167 5000 235 206 5000 614 218 5000 465 236 5000 497 257 5000 187 Citrix 287 5000 260 305 5000 1049 365 5000 616 368 5000 379 383 10000 76 Citrix 461 5000 535 467 5000 288 [/code] So if someone was to plot the sierpinski numbers (Y axis) and use the count (x axis) does the slope of the curve eventually become almost 0. If yes then it means that low k values are more likely to produce primes than high k values. Does anyone have enough data to plot this. Any thoughts on why low k's like 2, 3 can never be sierpinski numbers to any base... Thanks! :smile: |
[QUOTE=Citrix;96991]But when I tried use Srsieve, it said all the numbers were eliminated. So I assumed it was a Sierpinksi number of this type. Though now when I run Srsieve it says some numbers are left.[/QUOTE]
There was a bug, hopefully fixed in version 0.6.4, that could cause this problem. |
Approach to solution
Thinking a bit about this:
The simplest covering set comprises 2 primes with order base b of 2. One provides cover for n 1,3,5,7... and the other for 2,4,6,8... It is simple to prove that there are no two such primes. Covering n=1 implies that (2.i^1+1)modp == 0modp and (2.i^3+1)modp==0modp or 0modp == (2i^3-2i)modp 0modp == 2.i.(i-1).(i+1)modp therefore i=1 and (2.1^2+1)modp==3mod(p)==0mod(p) which is only solvable for p=3, which is only 1 prime, and in position 1,3,5... this is base=1mod3 and position 2,4,6... is 2mod3 A second covering set can be described using 3 and two other primes q and r which cover either position 1 and 5 or 2 and 6, with 3 covering 2,4,6.. or 1,3,5.. . Such q,r are of the form 4j+1, where j is an integer. Let us look at 3 covering positions 2,4,6.. and q covering 1,5,9... Then (2.b^1+1)modq==(2.b^5+1)modq is solvable for 5, in position 1 as 2mod5 and position 2 as 3mod5 Trying to find prime r of the form 4j+1 requires a solution to the equation A 4th root of unity modr equals either (r-1)/2 or the solution to (2.x^3+1)modr == 0modr I checked the first few 4j+1 primes and found no solutions except 5: 1. r 2. a 4th root of unity modr 3. another 4th root of unity modr 4. (r-1)/2 5. solution to (2.x^3+1)modr==0modr **= no solution 5 2 3 2 3 13 5 8 6 ** 17 4 13 8 2 29 12 17 14 10 37 6 31 18 ** 41 9 32 20 8 53 23 30 26 50 61 11 50 30 ** 73 27 46 36 ** 89 34 55 44 50 97 22 75 48 ** 101 10 91 50 66 109 33 76 54 62 113 15 98 56 53 137 37 100 68 130 149 44 105 74 83 157 28 129 78 15 173 80 93 86 101 181 19 162 90 ** 193 81 112 96 ** 197 14 183 98 75 229 107 122 114 7 233 89 144 116 195 241 64 177 120 ** 257 16 241 128 225 269 82 187 134 19 Makes me think that there may be no r that can satisfy the criteria, and that any covering set (if one exists) has to be more complex. Perhaps someone can find an r or prove that I am comparing apples and oranges. |
[QUOTE=Citrix;96991] I don't think that 2 can be a sierpinki/riesel number for any base. Nor can any of the low k values.
[/QUOTE] 4 is the lowest k I have found, which is sierpinski and riesel quite frequently for bases where b^2-1 produces two primitive prime factors. For example 4*14^n+/-1 never prime. Primitive primes factors of 14^2-1 are 3 and 5. Maybe k=1 can be sierpinski/ riesel. May have a look at that. |
For fixed k, find the smallest base b such that all numbers of the form k*b^n+1 (k*b^n-1) are composite.
If k is of the form 2^n-1 (2^n+1), except k=1 (k=9), it is conjectured for every nontrivial base b, there is a prime of the form k*b^n+1 (k*b^n-1). However, for all other k's, there is a base b such that all numbers of the form k*b^n+1 (k*b^n-1) are composite. S = conjectured smallest base b such that k is a Sierpinski number. k S remaining bases b with no known primes 1 none {38, 50, 62, 68, 86, 92, 98, 104, 122, 144, 168, 182, 186, 200, 202, 212, 214, 218, 244, 246, 252, 258, 286, 294, 298, 302, 304, 308, 322, 324, 338, 344, 354, 356, 362, 368, 380, 390, 394, 398, 402, 404, 410, 416, 422, 424, 446, 450, 454, 458, 468, 480, 482, 484, 500, 514, 518, 524, 528, 530, 534, 538, 552, 558, 564, 572, 574, 578, 580, 590, 602, 604, 608, 620, 622, 626, 632, 638, 648, 650, 662, 666, 668, 670, 678, 684, 692, 694, 698, 706, 712, 720, 722, 724, 734, 744, 746, 752, 754, 762, 766, 770, 792, 794, 802, 806, 812, 814, 818, 836, 840, 842, 844, 848, 854, 868, 870, 872, 878, 888, 896, 902, 904, 908, 922, 924, 926, 932, 938, 942, 944, 948, 954, 958, 964, 968, 974, 978, 980, 988, 994, 998, 1002, 1006, 1014, 1016, 1026, ...} (b=m^r with odd r>1 proven composite by full algebraic factors) 2 201446503145165177 (?) {218, 236, 365, 383, 461, 512, 542, 647, 773, 801, 836, 878, 908, 914, 917, 947, 1004, ...} 3 none {718, 912, ...} 4 14 proven 5 140324348 {308, 326, 512, 824, ...} 6 34 proven 7 none {1004, ...} 8 20 proven (b=8 proven composite by full algebraic factors) 9 177744 {592, 724, 884, ...} 10 32 proven 11 14 proven 12 142 {12} 13 20 proven 14 38 proven 15 none {398, 650, 734, 874, 876, 1014, ...} 16 38 {32} 17 278 {68, 218} 18 322 {18, 74, 227, 239, 293} 19 14 proven 20 56 proven 21 54 proven 22 68 {22} 23 32 proven 24 114 {79} 25 38 proven 26 14 proven 27 90 {62} 28 86 {41} 29 20 proven 30 898 31 none 32 92 {87} (b=32 proven composite by full algebraic factors) R = conjectured smallest base b such that k is a Riesel number. k R remaining bases b with no known primes 1 none proven 2 none {303, 522, 578, 581, 992, 1019, ...} 3 none {588, 972, ...} 4 14 proven (b=9 proven composite by full algebraic factors) 5 none {338, 998, ...} 6 34 proven (b=24 proven composite by partial algebraic factors) 7 9162668342 {308, 392, 398, 518, 548, 638, 662, 848, 878, ...} 8 20 proven 9 none {378, 438, 536, 566, 570, 592, 636, 688, 718, 808, 830, 852, 926, 990, 1010, ...} (b=m^2 proven composite by full algebraic factors, b=4 mod 5 proven composite by partial algebraic factors) 10 32 proven 11 14 proven 12 142 proven 13 20 proven 14 8 proven 15 8241218 {454, 552, 734, 856, ...} 16 50 proven (b=9 proven composite by full algebraic factors, b=33 proven composite by partial algebraic factors) 17 none {98, 556, 650, 662, 734, ...} 18 203 {174} (b=50 proven composite by partial algebraic factors) 19 14 proven 20 56 proven 21 54 proven 22 68 {38, 62} 23 32 proven 24 114 proven 25 38 proven (b=36 proven composite by full algebraic factors, b=12 proven composite by partial algebraic factors) 26 14 proven 27 90 {34} (b=8 and 64 proven composite by full algebraic factors, b=12 proven composite by partial algebraic factors) 28 86 {74} 29 20 proven 30 898 31 362 {80, 84, 122, 278, 350} 32 92 {54, 71, 77} |
S = conjectured smallest base b such that k is a Sierpinski number.
k S cover set 1 none 2 201446503145165177 (?) {3, 5, 17, 257, 641, 65537, 6700417} period=64 3 none 4 14 {3, 5} period=2 5 140324348 {3, 13, 17, 313, 11489} period=16 6 34 {5, 7} period=2 7 none 8 20 {3, 7} period=2 9 177744 {5, 17, 41, 193} period=8 10 32 {3, 11} period=2 11 14 {3, 5} period=2 12 142 {11, 13} period=2 13 20 {3, 7} period=2 14 38 {3, 13} period=2 15 none 16 38 {3, 5, 17} period=4 17 278 {3, 5, 29} period=4 18 322 {17, 19} period=2 19 14 {3, 5} period=2 20 56 {3, 19} period=2 21 54 {5, 11} period=2 22 68 {3, 23} period=2 23 32 {3, 11} period=2 24 114 {5, 23} period=2 25 38 {3, 13} period=2 26 14 {3, 5} period=2 27 90 {7, 13} period=2 28 86 {3, 29} period=2 29 20 {3, 7} period=2 30 898 {29, 31} period=2 31 none 32 92 {3, 31} period=2 33 5592 {5, 17, 109} period=4 34 14 {3, 5} period=2 35 50 {3, 17} period=2 36 68 {5, 7, 13, 31, 37} period=12 37 56 {3, 19} period=2 38 98 {3, 5, 17} period=4 39 94 {5, 19} period=2 40 122 {3, 41} period=2 41 14 {3, 5} period=2 42 1762 {41, 43} period=2 43 32 {3, 11} period=2 44 128 {3, 43} period=2 45 252 {11, 23} period=2 46 140 {3, 47} period=2 47 8 {3, 5, 13} period=4 48 328 {7, 47} period=2 49 14 {3, 5} period=2 50 20 {3, 7} period=2 51 64 {5, 13} period=2 52 158 {3, 53} period=2 53 38 {3, 13} period=2 54 264 {5, 53} period=2 55 20 {3, 7} period=2 56 14 {3, 5} period=2 57 202 {7, 29} period=2 58 176 {3, 59} period=2 59 144 {5, 29} period=2 60 3598 {59, 61} period=2 61 92 {3, 31} period=2 62 182 {3, 61} period=2 63 none 64 29 {3, 5} period=2 R = conjectured smallest base b such that k is a Riesel number. k R cover set 1 none 2 none 3 none 4 14 {3, 5} period=2 5 none 6 34 {5, 7} period=2 7 9162668342 {3, 5, 17, 1201, 169553} period=16 8 20 {3, 7} period=2 9 none 10 32 {3, 11} period=2 11 14 {3, 5} period=2 12 142 {11, 13} period=2 13 20 {3, 7} period=2 14 8 {3, 5, 13} period=4 15 8241218 {7, 17, 113, 1489} period=8 16 50 {3, 17} period=2 17 none 18 203 {5, 13, 17} period=4 19 14 {3, 5} period=2 20 56 {3, 19} period=2 21 54 {5, 11} period=2 22 68 {3, 23} period=2 23 32 {3, 11} period=2 24 114 {5, 23} period=2 25 38 {3, 13} period=2 26 14 {3, 5} period=2 27 90 {7, 13} period=2 28 86 {3, 29} period=2 29 20 {3, 7} period=2 30 898 {29, 31} period=2 31 362 {3, 7, 13, 37, 331} period=12 32 92 {3, 31} period=2 33 none 34 14 {3, 5} period=2 35 50 {3, 17} period=2 36 184 {5, 37} period=2 37 56 {3, 19} period=2 38 110 {3, 37} period=2 39 94 {5, 19} period=2 40 122 {3, 41} period=2 41 14 {3, 5} period=2 42 1762 {41, 43} period=2 43 32 {3, 11} period=2 44 128 {3, 43} period=2 45 252 {11, 23} period=2 46 140 {3, 47} period=2 47 68 {3, 23} period=2 48 328 {7, 47} period=2 49 14 {3, 5} period=2 50 20 {3, 7} period=2 51 64 {5, 13} period=2 52 158 {3, 53} period=2 53 38 {3, 13} period=2 54 264 {5, 53} period=2 55 20 {3, 7} period=2 56 14 {3, 5} period=2 57 202 {7, 29} period=2 58 176 {3, 59} period=2 59 86 {3, 29} period=2 60 3598 {59, 61} period=2 61 68 {3, 7, 13, 31} period=6 62 182 {3, 61} period=2 63 36858 {5, 31, 397} period=4 64 14 {3, 5} period=2 |
See [URL]http://mersenneforum.org/showthread.php?t=21951[/URL] for more information.
|
[QUOTE=Citrix;95709]Has there been any work done to find S/R for fixed k and variable base?
eg. What is the lowest base=b for k=2 such that 2*b^n+1 is never prime? What k's can never be sierpinski numbers? Is there any proof to this. How does one generate the sierpinski base for a given k? (The same questions for Riesel side)[/QUOTE] This base is probably 201446503145165177. |
| All times are UTC. The time now is 09:29. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.