mersenneforum.org The reverse Sierpinski/Riesel problem
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-20, 09:19 #1 sweety439   Nov 2016 22·691 Posts The reverse Sierpinski/Riesel problem 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 {171, 173, 269, 293, 347, 432, 490, 659, 661, 695, 712, 738, 795, 830} 31 none {38, 74, 116, 152, 174, 182, 242, 248, 254, 272, 278, 332, 448, 454, 458, 486, 494, 570, 578, 584, 614, 620, 632, 662, 714, 722, 728, 734, 758, 786, 794, 812, 824, 828, 842, 898, 938, 1014, 1028, ...} 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 {193, 247, 254, 305, 495, 501, 514, 535, 537, 569, 654, 659, 661, 683, 753, 764, 774, 809, 869} 31 362 {80, 84, 122, 278, 350} 32 92 {54, 71, 77} Last fiddled with by sweety439 on 2019-03-01 at 18:10
 2017-01-20, 09:43 #2 sweety439   Nov 2016 22×691 Posts 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 Last fiddled with by sweety439 on 2017-01-20 at 12:52
 2017-01-21, 14:51 #3 sweety439   Nov 2016 22×691 Posts The known large primes (n>=1000) of the reverse Sierpinski/Riesel problems are: (not include k = 2, 3, 5, 7) (only for bases b<=1030) Sierpinski: k=1: 1*824^1024+1 k=10: 10*17^1356+1 k=12: 12*30^1023+1 12*68^656921+1 12*87^1214+1 12*102^2739+1 k=15: 15*496^44172+1 15*636^9850+1 15*752^1128+1 15*864^51510+1 k=18: 18*145^6555+1 18*157^3873+1 18*189^171175+1 k=24: 24*45^18522+1 k=30: 30*115^47376+1 30*136^?+1 30*236^2360+1 30*243^14109+1 30*315^?+1 30*336^?+1 30*386^225439+1 30*402^4637+1 30*409^3329+1 30*463^43298+1 30*577^2974+1 30*591^?+1 30*677^1744+1 30*706^2839+1 30*724^28548+1 30*774^1399+1 30*810^?+1 30*856^?+1 k=31: 31*122^1236+1 31*214^13468+1 31*308^1904+1 31*386^1010+1 31*416^23572+1 31*422^33728+1 31*438^27976+1 31*452^1516+1 31*488^30060+1 31*492^30359+1 31*518^3752+1 31*530^74898+1 31*572^15576+1 31*788^1588+1 31*904^19068+1 31*996^?+1 31*1010^2036+1 k=32: 32*26^318071+1 Riesel: k=12: 12*65^1193-1 12*98^3599-1 k=15: 15*774^1937-1 15*828^2308-1 k=17: 17*110^2598-1 17*724^1082-1 17*842^35640-1 17*988^1275-1 k=18: 18*72^1494-1 k=24: 24*45^153355-1 24*64^3020-1 24*72^2648-1 k=25: 25*30^34205-1 k=30: 30*23^1000-1 30*172^?-1 30*235^56835-1 30*298^10338-1 30*480^12864-1 30*520^?-1 30*542^?-1 30*550^10353-1 30*557^22290-1 30*802^?-1 30*897^?-1 k=31: 31*198^?-1 31*290^5025-1 k=32: 32*26^9812-1 Last fiddled with by sweety439 on 2017-02-13 at 13:51
 2017-01-24, 16:04 #4 sweety439   Nov 2016 22×691 Posts Also, for some k's: Sierpinski: k=65: unknown, continue to find... k=129: conjectured base b=802, covering set: {7, 13, 337}, period=3 k=257: conjectured base b=380, covering set: {3, 7, 43, 61}, period=6 k=513: unknown, continue to find... Riesel: k=127: conjectured base b=8672, covering set: {3, 5, 17, 137}, period=8 k=255: conjectured base b=4952, covering set: {41, 61, 127}, period=4 k=511: conjectured base b=185324, covering set: {3, 137, 953}, period=4 k=1023: conjectured base b=718, covering set: {7, 13, 61}, period=3
 2017-01-24, 16:05 #5 sweety439   Nov 2016 ACC16 Posts There is not a Sierpinski base if and only if k is of the form 2^r-1. There is not a Riesel base if and only if k is of the form 2^r+1.
 2017-02-20, 17:47 #6 sweety439   Nov 2016 22×691 Posts I reserved some reverse Sierpinski/Riesel problems with only <=3 bases remain and found those primes: 22*38^1579-1 27*34^3086-1 28*74^3369-1 Riesel k=27 and Riesel k=28 were proven!!! These forms have no primes found and likely tested to at least n=5000: 27*62^n+1 28*41^n+1 22*62^n-1 Reserving 18*174^n-1, 32*54^n-1, 32*71^n-1 and 32*77^n-1. Last fiddled with by sweety439 on 2017-02-20 at 18:00
 2017-02-20, 17:54 #7 sweety439   Nov 2016 22·691 Posts See CRUS, 12*12^n+1, 16*32^n+1 and 22*22^n+1 were tested to at least n=2^25-2, 17*68^n+1 and 32*87^n+1 were tested to n=1M, and 17*218^n+1 and 24*79^n+1 were tested to n=200K. Last fiddled with by sweety439 on 2017-02-20 at 17:56
 2017-02-20, 18:00 #8 sweety439   Nov 2016 22·691 Posts 32*54^1044-1 and 32*77^824-1 are primes! However, 32*71^n-1 has no prime found, it is likely tested to at least n=5000.
 2017-02-23, 09:07 #9 sweety439   Nov 2016 276410 Posts If b and k are of these forms, then k is a Brier number (i.e. both Sierpinski number and Riesel number) to base b. Code: b k = 14 mod 15 = 4 or 11 mod 15 = 20 mod 21 = 8 or 13 mod 21 = 32 mod 33 = 10 or 23 mod 33 = 34 mod 35 = 6 or 29 mod 35 = 38 mod 39 = 14 or 25 mod 39 = 50 mod 51 = 16 or 35 mod 51 = 54 mod 55 = 21 or 34 mod 55 = 56 mod 57 = 20 or 37 mod 57 = 64 mod 65 = 14 or 51 mod 65 = 68 mod 69 = 22 or 47 mod 69 = 76 mod 77 = 34 or 43 mod 77 = 84 mod 85 = 16 or 69 mod 85 = 86 mod 87 = 28 or 59 mod 87 = 90 mod 91 = 27 or 64 mod 91 = 92 mod 93 = 32 or 61 mod 93 = 94 mod 95 = 39 or 56 mod 95 = 110 mod 111 = 38 or 73 mod 111 = 114 mod 115 = 24 or 91 mod 115 = 118 mod 119 = 50 or 69 mod 119 = 122 mod 123 = 40 or 83 mod 123 = 128 mod 129 = 44 or 85 mod 129 = 132 mod 133 = 20 or 113 mod 133 = 140 mod 141 = 46 or 95 mod 141 = 142 mod 143 = 12 or 131 mod 143 Generally, if there is a prime p divides both k+1 and b+1, and a prime q divides both k-1 and b+1, then k is both Sierpinski number (if gcd(k+1,b-1) = 1) and Riesel number (if gcd(k-1,b-1) = 1) to base b. (the covering set is both {p, q}) Thus, for the original Sierpinski/Riesel problems, if b+1 has at least two distinct odd prime factors, then it is easy to find a Sierpinski/Riesel k. Besides, for the reverse Sierpinski/Riesel problems, if neither k+1 nor k-1 is a power of 2 ("power of 2" includes 1), then it is easy to find a Sierpinski/Riesel base b. Last fiddled with by sweety439 on 2017-02-23 at 09:15
2017-02-23, 09:50   #10
sweety439

Nov 2016

22·691 Posts

Quote:
 Originally Posted by sweety439 If b and k are of these forms, then k is a Brier number (i.e. both Sierpinski number and Riesel number) to base b. Code: b k = 14 mod 15 = 4 or 11 mod 15 = 20 mod 21 = 8 or 13 mod 21 = 32 mod 33 = 10 or 23 mod 33 = 34 mod 35 = 6 or 29 mod 35 = 38 mod 39 = 14 or 25 mod 39 = 50 mod 51 = 16 or 35 mod 51 = 54 mod 55 = 21 or 34 mod 55 = 56 mod 57 = 20 or 37 mod 57 = 64 mod 65 = 14 or 51 mod 65 = 68 mod 69 = 22 or 47 mod 69 = 76 mod 77 = 34 or 43 mod 77 = 84 mod 85 = 16 or 69 mod 85 = 86 mod 87 = 28 or 59 mod 87 = 90 mod 91 = 27 or 64 mod 91 = 92 mod 93 = 32 or 61 mod 93 = 94 mod 95 = 39 or 56 mod 95 = 110 mod 111 = 38 or 73 mod 111 = 114 mod 115 = 24 or 91 mod 115 = 118 mod 119 = 50 or 69 mod 119 = 122 mod 123 = 40 or 83 mod 123 = 128 mod 129 = 44 or 85 mod 129 = 132 mod 133 = 20 or 113 mod 133 = 140 mod 141 = 46 or 95 mod 141 = 142 mod 143 = 12 or 131 mod 143 Generally, if there is a prime p divides both k+1 and b+1, and a prime q divides both k-1 and b+1, then k is both Sierpinski number (if gcd(k+1,b-1) = 1) and Riesel number (if gcd(k-1,b-1) = 1) to base b. (the covering set is both {p, q}) Thus, for the original Sierpinski/Riesel problems, if b+1 has at least two distinct odd prime factors, then it is easy to find a Sierpinski/Riesel k. Besides, for the reverse Sierpinski/Riesel problems, if neither k+1 nor k-1 is a power of 2 ("power of 2" includes 1), then it is easy to find a Sierpinski/Riesel base b.
Thus, for all Sierpinski/Riesel bases b<=144 such that b+1 has at least two distinct odd prime factors:

Code:
base      the smallest Sierpinski/Riesel k we calculated       the truly smallest Sierpinski/Riesel k
14        4                                                    both 4
20        8                                                    both 8
29        4                                                    both 4
32        10                                                   both 10
34        6                                                    both 6
38        14                                                   14 / 13 (13 is also a Riesel k to base 38)
41        8                                                    both 8
44        4                                                    both 4
50        16                                                   both 16
54        21                                                   both 21
56        20                                                   both 20
59        4                                                    both 4
62        8                                                    both 8
64        14                                                   51 / 14 (14 is a trivial k in the Sierpinski case)
65        10                                                   both 10
68        22                                                   both 22
69        6                                                    both 6
74        4                                                    both 4
76        34                                                   43 / 120 (34 is a trivial k in the Sierpinski case, and all of 34, 43 and 111 are trivial k's in the Riesel case)
77        14                                                   both 14
83        8                                                    both 8
84        16                                                   both 16
86        28                                                   both 28
89        4                                                    both 4
90        27                                                   both 27
92        32                                                   both 32
94        39                                                   both 39
98        10                                                   both 10
101       16                                                   16 / 118 (all of 16, 35, 67 and 86 are trivial k's in the Riesel case)
104       4                                                    both 4
109       21                                                   34 / 144 (21 is a trivial k in the Sierpinski case, and all of 21, 34, 76, 89 and 131 are trivial k's in the Riesel case)
110       38                                                   both 38
113       20                                                   94 / 20 (all of 20, 37 and 77 are trivial k's in the Sierpinski case)
114       24                                                   both 24
116       14                                                   25 / 14 (14 is a trivial k in the Sierpinski case)
118       50                                                   69 / 50 (50 is a trivial k in the Sierpinski case)
119       4                                                    both 4
122       40                                                   40 / 14 (14 is also a Riesel k to base 122)
125       8                                                    both 8
128       44                                                   both 44
129       14                                                   both 14
131       10                                                   both 10
132       20                                                   13 / 20 (13 is also a Sierpinski k to base 132)
134       4                                                    both 4
137       22                                                   both 22
139       6                                                    both 6
140       46                                                   both 46
142       12                                                   both 12
144       59                                                   both 59

Last fiddled with by sweety439 on 2017-02-23 at 16:27

 2017-03-08, 17:17 #11 sweety439   Nov 2016 ACC16 Posts For Sierpinski k=18, I found 2 primes: 18*74^662+1 18*239^1990+1 Thus, there are only 3 bases remain for Sierpinski k=18: 18, 227, 293. b=18 was already tested to n=2^25-2 with no prime found, b=227 was already tested to n=1M with no prime found, for b=293, I found no prime, it is likely tested to at least n=5000.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 1183 2020-12-30 01:27 sweety439 sweety439 13 2020-12-23 23:56 sweety439 sweety439 11 2020-09-23 01:42 michaf Conjectures 'R Us 2 2007-12-17 05:04 michaf Conjectures 'R Us 49 2007-12-17 05:03

All times are UTC. The time now is 02:37.

Mon Jan 25 02:37:15 UTC 2021 up 52 days, 22:48, 0 users, load averages: 2.06, 2.09, 2.15