mersenneforum.org (https://www.mersenneforum.org/index.php)
-   sweety439 (https://www.mersenneforum.org/forumdisplay.php?f=137)
-   -   The reverse Sierpinski/Riesel problem (https://www.mersenneforum.org/showthread.php?t=21951)

 sweety439 2017-01-20 09:19

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}

 sweety439 2017-01-20 09:43

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

 sweety439 2017-01-21 14:51

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

 sweety439 2017-01-24 16:04

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

 sweety439 2017-01-24 16:05

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.

 sweety439 2017-02-20 17:47

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.

 sweety439 2017-02-20 17:54

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.

 sweety439 2017-02-20 18:00

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.

 sweety439 2017-02-23 09:07

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
[/CODE]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 [I]distinct odd[/I] 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.

 sweety439 2017-02-23 09:50

[QUOTE=sweety439;453522]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
[/CODE]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 [I]distinct odd[/I] 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.[/QUOTE]

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
[/CODE]

 sweety439 2017-03-08 17:17

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.

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