Extended Sierpinski problem:

Finding and proving the smallest k such that (k*b^n+1)/gcd(k+1,b-1) is not prime for all integers n>=1.

Extended Riesel problem:

Finding and proving the smallest k such that (k*b^n-1)/gcd(k-1,b-1) is not prime for all integers n>=1.

Notes:

All n must be >= 1.

k-values that make a full covering set with all or partial algebraic factors are excluded from the conjectures.

k-values that are a multiple of base (b) and where (k+-1)/gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) is not prime are included in the conjectures but excluded from testing.
Such k-values will have the same prime as k / b.

These are the CK for Sierpinski/Riesel bases 2<=b<=2048 (searched up to 10^6)

In Riesel conjectures, if k=m^2 and m and b satisfy at least one of these conditions, then this k should be excluded from the Riesel base b problem, since it has algebraic factors for even n and it has a single prime factor for odd n, thus proven composite by partial algebraic factors

list all such mod <= 2048

[CODE]
m b
= 2 or 3 mod 5 = 4 mod 5
= 5 or 8 mod 13 = 12 mod 13
= 3 or 5 mod 8 = 9 mod 16
= 4 or 13 mod 17 = 16 mod 17
= 12 or 17 mod 29 = 28 mod 29
= 7 or 9 mod 16 = 17 mod 32
= 6 or 31 mod 37 = 36 mod 37
= 9 or 32 mod 41 = 40 mod 41
= 23 or 30 mod 53 = 52 mod 53
= 11 or 50 mod 61 = 60 mod 61
= 15 or 17 mod 32 = 33 mod 64
= 27 or 46 mod 73 = 72 mod 73
= 34 or 55 mod 89 = 88 mod 89
= 22 or 75 mod 97 = 96 mod 97
= 10 or 91 mod 101 = 100 mod 101
= 33 or 76 mod 109 = 108 mod 109
= 15 or 98 mod 113 = 112 mod 113
= 31 or 33 mod 64 = 65 mod 128
= 37 or 100 mod 137 = 136 mod 137
= 44 or 105 mod 149 = 148 mod 149
= 28 or 129 mod 157 = 156 mod 157
= 80 or 93 mod 173 = 172 mod 173
= 19 or 162 mod 181 = 180 mod 181
= 81 or 112 mod 193 = 192 mod 193
= 14 or 183 mod 197 = 196 mod 197
= 107 or 122 mod 229 = 228 mod 229
= 89 or 144 mod 233 = 232 mod 233
= 64 or 177 mod 241 = 240 mod 241
= 63 or 65 mod 128 = 129 mod 256
= 16 or 241 mod 257 = 256 mod 257
= 82 or 187 mod 269 = 268 mod 269
= 60 or 217 mod 277 = 276 mod 277
= 53 or 228 mod 281 = 280 mod 281
= 138 or 155 mod 293 = 292 mod 293
= 25 or 288 mod 313 = 312 mod 313
= 114 or 203 mod 317 = 316 mod 317
= 148 or 189 mod 337 = 336 mod 337
= 136 or 213 mod 349 = 348 mod 349
= 42 or 311 mod 353 = 352 mod 353
= 104 or 269 mod 373 = 372 mod 373
= 115 or 274 mod 389 = 388 mod 389
= 63 or 334 mod 397 = 396 mod 397
= 20 or 381 mod 401 = 400 mod 401
= 143 or 266 mod 409 = 408 mod 409
= 29 or 392 mod 421 = 420 mod 421
= 179 or 254 mod 433 = 432 mod 433
= 67 or 382 mod 449 = 448 mod 449
= 109 or 348 mod 457 = 456 mod 457
= 48 or 413 mod 461 = 460 mod 461
= 208 or 301 mod 509 = 508 mod 509
= 127 or 129 mod 256 = 257 mod 512
= 235 or 286 mod 521 = 520 mod 521
= 52 or 489 mod 541 = 540 mod 541
= 118 or 439 mod 557 = 556 mod 557
= 86 or 483 mod 569 = 568 mod 569
= 24 or 553 mod 577 = 576 mod 577
= 77 or 516 mod 593 = 592 mod 593
= 125 or 476 mod 601 = 600 mod 601
= 35 or 578 mod 613 = 612 mod 613
= 194 or 423 mod 617 = 616 mod 617
= 154 or 487 mod 641 = 640 mod 641
= 149 or 504 mod 653 = 652 mod 653
= 106 or 555 mod 661 = 660 mod 661
= 58 or 615 mod 673 = 672 mod 673
= 26 or 651 mod 677 = 676 mod 677
= 135 or 566 mod 701 = 700 mod 701
= 96 or 613 mod 709 = 708 mod 709
= 353 or 380 mod 733 = 732 mod 733
= 87 or 670 mod 757 = 756 mod 757
= 39 or 722 mod 761 = 760 mod 761
= 62 or 707 mod 769 = 768 mod 769
= 317 or 456 mod 773 = 772 mod 773
= 215 or 582 mod 797 = 796 mod 797
= 318 or 491 mod 809 = 808 mod 809
= 295 or 526 mod 821 = 820 mod 821
= 246 or 583 mod 829 = 828 mod 829
= 333 or 520 mod 853 = 852 mod 853
= 207 or 650 mod 857 = 856 mod 857
= 151 or 726 mod 877 = 876 mod 877
= 387 or 494 mod 881 = 880 mod 881
= 324 or 605 mod 929 = 928 mod 929
= 196 or 741 mod 937 = 936 mod 937
= 97 or 844 mod 941 = 940 mod 941
= 442 or 511 mod 953 = 952 mod 953
= 252 or 725 mod 977 = 976 mod 977
= 161 or 836 mod 997 = 996 mod 997
= 469 or 540 mod 1009 = 1008 mod 1009
= 45 or 968 mod 1013 = 1012 mod 1013
= 374 or 647 mod 1021 = 1020 mod 1021
= 255 or 257 mod 512 = 513 mod 1024
= 355 or 678 mod 1033 = 1032 mod 1033
= 426 or 623 mod 1049 = 1048 mod 1049
= 103 or 958 mod 1061 = 1060 mod 1061
= 249 or 820 mod 1069 = 1068 mod 1069
= 530 or 563 mod 1093 = 1092 mod 1093
= 341 or 756 mod 1097 = 1096 mod 1097
= 354 or 755 mod 1109 = 1108 mod 1109
= 214 or 903 mod 1117 = 1116 mod 1117
= 168 or 961 mod 1129 = 1128 mod 1129
= 140 or 1013 mod 1153 = 1152 mod 1153
= 243 or 938 mod 1181 = 1180 mod 1181
= 186 or 1007 mod 1193 = 1192 mod 1193
= 49 or 1152 mod 1201 = 1200 mod 1201
= 495 or 718 mod 1213 = 1212 mod 1213
= 78 or 1139 mod 1217 = 1216 mod 1217
= 597 or 632 mod 1229 = 1228 mod 1229
= 546 or 691 mod 1237 = 1236 mod 1237
= 585 or 664 mod 1249 = 1248 mod 1249
= 113 or 1164 mod 1277 = 1276 mod 1277
= 479 or 810 mod 1289 = 1288 mod 1289
= 36 or 1261 mod 1297 = 1296 mod 1297
= 51 or 1250 mod 1301 = 1300 mod 1301
= 257 or 1064 mod 1321 = 1320 mod 1321
= 614 or 747 mod 1361 = 1360 mod 1361
= 668 or 705 mod 1373 = 1372 mod 1373
= 366 or 1015 mod 1381 = 1380 mod 1381
= 452 or 957 mod 1409 = 1408 mod 1409
= 620 or 809 mod 1429 = 1428 mod 1429
= 542 or 891 mod 1433 = 1432 mod 1433
= 497 or 956 mod 1453 = 1452 mod 1453
= 465 or 1016 mod 1481 = 1480 mod 1481
= 225 or 1264 mod 1489 = 1488 mod 1489
= 432 or 1061 mod 1493 = 1492 mod 1493
= 88 or 1461 mod 1549 = 1548 mod 1549
= 339 or 1214 mod 1553 = 1552 mod 1553
= 610 or 987 mod 1597 = 1596 mod 1597
= 40 or 1561 mod 1601 = 1600 mod 1601
= 523 or 1086 mod 1609 = 1608 mod 1609
= 127 or 1486 mod 1613 = 1612 mod 1613
= 166 or 1455 mod 1621 = 1620 mod 1621
= 316 or 1321 mod 1637 = 1636 mod 1637
= 783 or 874 mod 1657 = 1656 mod 1657
= 220 or 1449 mod 1669 = 1668 mod 1669
= 92 or 1601 mod 1693 = 1692 mod 1693
= 414 or 1283 mod 1697 = 1696 mod 1697
= 390 or 1319 mod 1709 = 1708 mod 1709
= 473 or 1248 mod 1721 = 1720 mod 1721
= 410 or 1323 mod 1733 = 1732 mod 1733
= 59 or 1682 mod 1741 = 1740 mod 1741
= 713 or 1040 mod 1753 = 1752 mod 1753
= 775 or 1002 mod 1777 = 1776 mod 1777
= 724 or 1065 mod 1789 = 1788 mod 1789
= 824 or 977 mod 1801 = 1800 mod 1801
= 61 or 1800 mod 1861 = 1860 mod 1861
= 737 or 1136 mod 1873 = 1872 mod 1873
= 137 or 1740 mod 1877 = 1876 mod 1877
= 331 or 1558 mod 1889 = 1888 mod 1889
= 218 or 1683 mod 1901 = 1900 mod 1901
= 712 or 1201 mod 1913 = 1912 mod 1913
= 598 or 1335 mod 1933 = 1932 mod 1933
= 589 or 1360 mod 1949 = 1948 mod 1949
= 259 or 1714 mod 1973 = 1972 mod 1973
= 834 or 1159 mod 1993 = 1992 mod 1993
= 412 or 1585 mod 1997 = 1996 mod 1997
= 229 or 1788 mod 2017 = 2016 mod 2017
= 992 or 1037 mod 2029 = 2028 mod 2029
= 511 or 513 mod 1024 = 1025 mod 2048
[/CODE]

If there is an r>1 such that both k and b are perfect r-th powers, then this k should be excluded from the Riesel base b problem. Besides, if there is an odd r>1 such that both k and b are perfect r-th powers, then this k should be excluded from the Sierpinski base b problem. Besides, if k is of the form 4*m^4 and b is a perfect 4th power, then this k should be excluded from the Sierpinski base b problem.

Since these k's proven composite by full algebraic factors.

Conjecture 1 (the strong Sierpinski conjecture): For b>=2, k>=1, if there [B][I]is an n[/I][/B] such that:

(1) k*b^n is neither a perfect odd power (i.e. k*b^n is not of the form m^r with odd r>1) nor of the form 4*m^4.
(2) gcd((k*b^n+1)/gcd(k+1,b-1),(b^(9*2^s)-1)/(b-1)) = 1 for all s, i.e. for all s, every prime factor of (k*b^n+1)/gcd(k+1,b-1) does not divide (b^(9*2^s)-1)/(b-1). (i.e. ord_p(b) is not of the form 2^r (r>=0 if p = 2 or p = 3, r>=1 if p>=5), 3*2^r (r>=0) or 9*2^r (r>=0) for every prime factor p of (k*b^n+1)/gcd(k+1,b-1)).
(3) this k is not excluded from this Sierpinski base b by the post [URL="http://mersenneforum.org/showpost.php?p=459405&postcount=265"]#265[/URL]. (the first 6 Sierpinski bases with k's excluded by the post [URL="http://mersenneforum.org/showpost.php?p=459405&postcount=265"]#265[/URL] are 128, 2187, 16384, 32768, 78125 and 131072)

Then there are infinitely many primes of the form (k*b^n+1)/gcd(k+1,b-1).

Conjecture 2 (the strong Riesel conjecture): For b>=2, k>=1, if there [B][I]is an n[/I][/B] such that:

(1) k*b^n is not a perfect power (i.e. k*b^n is not of the form m^r with r>1).
(2) gcd((k*b^n-1)/gcd(k-1,b-1),(b^(9*2^s)-1)/(b-1)) = 1 for all s, i.e. for all s, every prime factor of (k*b^n-1)/gcd(k-1,b-1) does not divide (b^(9*2^s)-1)/(b-1). (i.e. ord_p(b) is not of the form 2^r (r>=0 if p = 2 or p = 3, r>=1 if p>=5), 3*2^r (r>=0) or 9*2^r (r>=0) for every prime factor p of (k*b^n-1)/gcd(k-1,b-1)).

Then there are infinitely many primes of the form (k*b^n-1)/gcd(k-1,b-1).

In this case, although (k*b^n+1)/gcd(k+1,b-1) has neither covering set nor algebra factors, but this form still cannot have a prime, thus this case is also excluded in the conjectures. (this situation only exists in the Sierpinski side)

b = q^m, k = q^r, where q is not of the form t^s with odd s>1, and m and r have no common odd prime factor, and the exponent of highest power of 2 dividing r >= the exponent of highest power of 2 dividing m, and the equation 2^x = r (mod m) has no solution.

Examples:

b = q^7, k = q^r, where r = 3, 5, 6 (mod 7).
b = q^14, k = q^r, where r = 6, 10, 12 (mod 14).
b = q^15, k = q^r, where r = 7, 11, 13, 14 (mod 15).
b = q^17, k = q^r, where r = 3, 5, 6, 7, 10, 11, 12, 14 (mod 17).
b = q^21, k = q^r, where r = 5, 10, 13, 17, 19, 20 (mod 21)
b = q^23, k = q^r, where r = 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 (mod 23)
b = q^28, k = q^r, where r = 12, 20, 24 (mod 28)
b = q^30, k = q^r, where r = 14, 22, 26, 28 (mod 30)
b = q^31, k = q^r, where r = 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 (mod 31)
b = q^33, k = q^r, where r = 5, 7, 10, 13, 14, 19, 20, 23, 26, 28 (mod 33)
etc.

(these are all examples for m<=33)

A large probable prime n can be proven to be prime if and only if at least one of n-1 and n+1 can be trivially written into a product.

Thus, if n is large, a probable prime (k*b^n+-1)/gcd(k+-1,b-1) can be proven to be prime if and only if gcd(k+-1,b-1) = 1.

R36 searched to n=10K

file attached.

Currently status for R36:

[CODE]
k n
251 1504
260 1315
924 2126
1148
1356 1230
1555
1923 2120
2110
2133
2443 5987
2753 7310
2776 5057
3181 1476
3590 4593
3699
3826 1834
3942 1425
4241 3528
4330 2939
4551
4635 1330
4737
4865 1181
5027 1119
5196 2235
5339 1310
5483 1479
5581 2618
5615 2456
5791 3878
5853 1163
6069 4353
6236
6542 2387
6581 1900
6873 1134
6883
7101 3048
7253
7316 4182
7362
7399
7445 4785
7617 1946
7631 1471
7991
8250
8259 6371
8321 1610
8361
8363
8472
8696 1117
9140 1109
9156 1030
9201 3153
9469 2950
9491
9582
10695 6672
10913 4118
11010 2766
11014
11143 1872
11212 6403
11216 7524
11434 1231
11568 1570
11904 1279
12174 1645
12320
12653
12731 1354
12766 1359
13641
13800 9790
14191 2462
14358
14503 2340
14540
14799 1454
14836
14973
14974
15228
15578 2733
15656 6611
15687
15756
15909
16168
16908 4132
17013 1539
17107 3264
17354
17502
17648 1630
17749 4275
17881 5205
17946
18203
18342 1045
18945 3993
19035
19315 6319
19389 9119
19572 4896
19646
19907 8439
20092
20186
20279 4042
20485 9140
20630
20684 8627
21162 1320
21415 3236
21880
22164
22312
22793 1419
23013 2934
23126 6343
23182 1320
23213
23441 4950
23482 5314
23607 1627
23621 2240
23792 1027
23901
23906
23975 1290
24125 1557
24236
24382
24556 3870
24645
24731
24887
24971 1132
25011
25052 1421
25159
25161
25204
25679
25788
25831 1633
26107 5574
26160
26355
26382 2087
26530 1101
26900 2271
27161
27262 1043
27296 7115
27342 1974
27680 2913
27901 1289
28416 7315
28846 1252
28897 2125
29199 1180
29266 1510
29453
29741 1838
29748 1314
29847
30031 3896
30161 1445
30970
31005
31190 5320
31326 3222
31414 4817
31634
31673 1225
31955 6185
32154 1703
32302
32380 7190
32411 1736
32451 1913
32522 1634
32668 1061
32811 4462
33047
33516 4038
33627
33686 3520
33762 1052
[/CODE]

Added missing (probable) primes for S22, S28, R36, R105

See github page [URL="https://github.com/xayahrainie4793/Extended-Sierpinski-Riesel-conjectures"]https://github.com/xayahrainie4793/Extended-Sierpinski-Riesel-conjectures[/URL] for the text files, I created a github account.