A Sierpinski/Riesel-like problem

[sweety439]

S13:

2 (2)
8 (4)
11 (564)
29 (10574)
281? (>5000)

S14:

2 (1)
6 (6)
22 (16)
29 (23)
61 (126)
73 (1182)
208 (>5000)

S15:

2 (1)
5 (2)
13 (10)
29 (30)
49 (112)
189 (190)
197 (464)
219 (1129)
341 (>5000)

S16:

2 (1)
3 (2)
5 (3)
18 (4)
23 (1074)
89 (>20000)

R13:

1 (5)
20 (10)
25 (15)
43 (77)
127 (95)
154 (469)
288 (109217)
337? (>5000)

R14:

1 (3)
2 (4)
5 (19698)
617? (>5000)

R15:

1 (3)
14 (14)
39 (16)
47 (>5000)

R16:

2 (1)
11 (2)
18 (3)
31 (12)
48 (15)
74 (638)
322 (4624)
443 (>1500000)

[sweety439]

Sierpinski k=2:

3 (1)
12 (3)
17 (47)
38 (2729)
101 (192275)
218 (333925)
365? (>200000)

Sierpinski k=3:

2 (1)
5 (2)
18 (3)
28 (7)
43 (171)
79 (875)
83 (>8000)

Sierpinski k=4:

3 (1)
5 (2)
17 (6)
23 (342)
53 (>1610000)

Sierpinski k=5:

2 (1)
3 (2)
16 (3)
19 (78)
31 (1026)
137 (>2000)

Sierpinski k=6:

2 (1)
4 (2)
14 (6)
19 (14)
20 (15)
48 (27)
53 (143)
67 (4532)
108 (16317)
129 (16796)
212 (>400000)

Riesel k=1:

2 (2)
3 (3)
7 (5)
11 (17)
19 (19)
35 (313)
39 (349)
51 (4229)
91 (4421)
152 (270217)
185? (>66337)

Riesel k=2:

2 (1)
5 (4)
20 (10)
29 (136)
67 (768)
107 (21910)
170 (166428)
581 (>200000)

Riesel k=3:

2 (1)
3 (2)
23 (6)
31 (18)
42 (2523)
107 (4900)
295 (5270)
347 (>25000)

Riesel k=4:

2 (1)
7 (3)
23 (5)
43 (279)
47 (1555)
72 (1119849)
178? (>5000)

Riesel k=5:

2 (2)
8 (4)
14 (19698)
31? (>6000)

Riesel k=6:

2 (1)
13 (2)
21 (3)
48 (294)
119 (665)
154 (1989)
234 (>400000)

[sweety439]

Update PARI program files.

[sweety439]

The "ground base" of (k*b^n+-1)/gcd(k+-1,b-1) is the smallest value of b' such that

* b' is a root of b (or b itself)
* b'-1 is divisible by gcd(k+-1,b-1)
* The relative complement of (k*b^n+-1)/gcd(k+-1,b-1) in (k'*b'^n+-1)/gcd(k'+-1,b'-1) contain no primes

e.g. the "ground base" of (k*4^n+1)/gcd(k+1,4-1) is 2 for k == 1 mod 3 (since for these k, the relative complement of (k*4^n+1)/gcd(k+1,4-1) in (k*2^n+1)/gcd(k+1,2-1) is (2*k*4^n+1)/gcd(k+1,4-1), and all numbers of the form (2*k*4^n+1)/gcd(k+1,4-1) is divisible by 3, thus not prime), but it is 4 for k == 0 or 2 mod 3, similarly, the "ground base" of (k*4^n-1)/gcd(k-1,4-1) is 2 for k == 2 mod 3, but 4 for k == 0 or 1 mod 3

More examples:

the "ground base" for (k*36^n-1)/gcd(k-1,36-1) is 6 for k == 6 mod 7, but 36 for other k

the "ground base" for (k*25^n-1)/gcd(k-1,25-1) is 5 for k == 2 mod 3 or k == 5 mod 8, but 25 for other k

the "ground base" for 222*625^n+1 is 25 (since all primes of the form 222*25^n+1 are of the form 222*625^n+1, numbers of the form 5550*625^n+1 are divisible by 13, thus cannot be prime, and 25 is the smallest possible base, numbers of the form 1110*25^n+1 can be prime)

the "ground base" for 366*625^n-1 and 9150^625^n-1 are both 625 (since both of them can contain primes)

the "ground base" for 29*1024^n-1 and 74*1024^n-1 are both 32

the "ground base" for 40*25^n+1 and (61*25^n+1)/2 are both 5

the "ground base" for 2036*9^n+1, 302*9^n-1, 386*9^n-1, and 744*9^n-1 are all 9

the "ground base" for 443*16^n-1, 2297*16^n-1, 13380*16^n-1, 13703*16^n-1, 2908*16^n+1, 6663*16^n+1, and 10183*16^n+1 are all 16

the "ground base" for 9519*16^n-1 and 19464*16^n-1 are both 4

the "ground base" for 18344*16^n-1, 23669*16^n-1, 31859*16^n-1, and 21181*16^n+1 are all 2

the "ground base" for 244*529^n+1, 376*529^n+1, and 394*529^n+1 are all 23

the "ground base" for 426*529^n+1 is 529

the "ground base" for 62*576^n+1, 227*576^n+1, and 1077*576^n+1 are all 576

the "ground base" for 656*576^n+1, 1851*576^n+1, and 2351*576^n+1 are all 24

the "ground base" for 94*8^n+1 is 2 (this is a case for a non-square power, since 47*8^n+1 has covering set {3, 5, 13} and 188*8^n+1 has trivial factor of 7, only 94*8^n+1 can be prime)

the "ground base" for 37*8^n-1 is 8 (since both 37*8^n-1 and 74*8^n-1 can be prime)

the "ground base" for 450*100^n-1 is 10

the "ground base" for 653*100^n-1, 74*100^n-1, and 470*100^n-1 are all 100

the "ground base" for 5*196^n-1 is 14

the "ground base" for 198*196^n-1 is 196

[sweety439]

Originally Posted by sweety439

The "ground base" of (k*b^n+-1)/gcd(k+-1,b-1) is the smallest value of b' such that

* b' is a root of b (or b itself)
* b'-1 is divisible by gcd(k+-1,b-1)
* The relative complement of (k*b^n+-1)/gcd(k+-1,b-1) in (k'*b'^n+-1)/gcd(k'+-1,b'-1) contain no primes

e.g. the "ground base" of (k*4^n+1)/gcd(k+1,4-1) is 2 for k == 1 mod 3 (since for these k, the relative complement of (k*4^n+1)/gcd(k+1,4-1) in (k*2^n+1)/gcd(k+1,2-1) is (2*k*4^n+1)/gcd(k+1,4-1), and all numbers of the form (2*k*4^n+1)/gcd(k+1,4-1) is divisible by 3, thus not prime), but it is 4 for k == 0 or 2 mod 3, similarly, the "ground base" of (k*4^n-1)/gcd(k-1,4-1) is 2 for k == 2 mod 3, but 4 for k == 0 or 1 mod 3

More examples:

the "ground base" for (k*36^n-1)/gcd(k-1,36-1) is 6 for k == 6 mod 7, but 36 for other k

the "ground base" for (k*25^n-1)/gcd(k-1,25-1) is 5 for k == 2 mod 3 or k == 5 mod 8, but 25 for other k

the "ground base" for 222*625^n+1 is 25 (since all primes of the form 222*25^n+1 are of the form 222*625^n+1, numbers of the form 5550*625^n+1 are divisible by 13, thus cannot be prime, and 25 is the smallest possible base, numbers of the form 1110*25^n+1 can be prime)

the "ground base" for 366*625^n-1 and 9150^625^n-1 are both 625 (since both of them can contain primes)

the "ground base" for 29*1024^n-1 and 74*1024^n-1 are both 32

the "ground base" for 40*25^n+1 and (61*25^n+1)/2 are both 5

the "ground base" for 2036*9^n+1, 302*9^n-1, 386*9^n-1, and 744*9^n-1 are all 9

the "ground base" for 443*16^n-1, 2297*16^n-1, 13380*16^n-1, 13703*16^n-1, 2908*16^n+1, 6663*16^n+1, and 10183*16^n+1 are all 16

the "ground base" for 9519*16^n-1 and 19464*16^n-1 are both 4

the "ground base" for 18344*16^n-1, 23669*16^n-1, 31859*16^n-1, and 21181*16^n+1 are all 2

the "ground base" for 244*529^n+1, 376*529^n+1, and 394*529^n+1 are all 23

the "ground base" for 426*529^n+1 is 529

the "ground base" for 62*576^n+1, 227*576^n+1, and 1077*576^n+1 are all 576

the "ground base" for 656*576^n+1, 1851*576^n+1, and 2351*576^n+1 are all 24

This means that, if finding a (probable) of the form (k'*b'^n+-1)/gcd(k'+-1,b'-1) is completely the same as finding a (probable) of the form (k*b^n+-1)/gcd(k+-1,b-1), then the "ground base" of (k*b^n+-1)/gcd(k+-1,b-1) is the smallest possible value of b'

[sweety439]

Originally Posted by sweety439

Like Bunyakovsky conjecture, it is conjectured that for all integer triples (k, b, c) satisfying these conditions:

1. k>=1, b>=2, c != 0

2. gcd(k, c) = 1, gcd(b, c) = 1

3. there is no finite set {p_1, p_2, p_3, ..., p_u} (all p_i (1<=i<=u) are primes) and finite set {r_1, r_2, r_3, ..., r_s} (all r_i (1<=i<=s) are integers > 1) such that for every integer n>=1:

either

(k*b^n+c)/gcd(k+c, b-1) is divisible by at least one p_i (1<=i<=u)

or

k*b^n and -c are both r_i-th powers for at least one r_i (1<=i<=s)

or

one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t

4. the triple (k, b, c) is not in this case: c = 1, b = q^m, k = q^r, where q is an integer not of the form t^s with odd s > 1, and m and r are integers having 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

Then there are infinitely many integers n>=1 such that (k*b^n+c)/gcd(k+c, b-1) is prime.

Conjecture: If there is at least one prime of the form (k*b^n+c)/gcd(k+c, b-1) (k>=1, b>=2, c != 0, gcd(k, c) = 1, gcd(b, c) = 1) with n>=1, then (k*b^n+c)/gcd(k+c, b-1) has no covering set

If this conjecture is true, then k*2^n+1 has no covering set for all k<78557, since all odd k<78557 have at least one known proven prime of the form either k*2^n+1 (n>=1) or of the form 2^n+k (n>=1), and if k*2^n+1 has covering set, then 2^n+k must have the same covering set, since the dual of (k*b^n+c)/gcd(k+c, b-1) is (|c*b^n+k|)/gcd(k+c, b-1)/gcd(k, b^n), and if a form has covering set, then the dual form must have the same covering set

[sweety439]

fixed the program so it can check whether (k*b^n+-1)/gcd(k+-1,b-1) has:

* covering set (for primes <= 50000, check to exponent = 5000)
* full algebra factors (k and b are both r-th powers for (r>1 Riesel case) (odd r>1 Sierpinski case)) (4*k and b are both 4-th powers Sierpinski case)
* partial algebra factors for algebra factors of difference of squares for (even/odd) n and one fixed prime factor for (odd/even) n for Riesel case

It current cannot check these cases:

* Partial algebra factors for algebra factors of difference of squares for (even/odd) n and covering set of >=2 primes for (odd/even) n for Riesel case:

** 1369*30^n-1 ({7, 13, 19} for odd n)
** (400*88^n-1)/3 ({3, 7, 13} for odd n)
** 324*95^n-1 ({7, 13, 229} for odd n)
** 93025*498^n-1 ({13, 67, 241} for odd n)
** 61009*540^n-1 ({17, 1009} for odd n)

** Partial algebra factors with period = 2 for square Sierpinski base:

** 114244*225^n+1

* Partial algebra factors for period > 2:

** (343*10^n-1)/9 (period = 3)
** 3511808*63^n+1 (period = 3)
** 27000000*63^n+1 (period = 3)
** (64*847^n-1)/9 (period = 3)
** 64*957^n-1 (period = 3)
** 2500*13^n+1 (period = 4)
** 2500*55^n+1 (period = 4)
** 16*200^n+1 (period = 4)
** (324*1101^n+1)/5 (period = 4)
** 324*2070^n+1 (period = 4)
** 64*936^n-1 (period = 6)

* 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

** 8*128^n+1
** 32*128^n+1
** 64*128^n+1
** (27*2187^n+1)/2
** (243*2187^n+1)/2
** (729*2187^n+1)/2
** 64*16384^n+1
** 1024*16384^n+1
** 4096*16384^n+1
** 128*32768^n+1
** 2048*32768^n+1
** 8192*32768^n+1
** 16384*32768^n+1
** 8*131072^n+1
** 32*131072^n+1
** 64*131072^n+1
** 128*131072^n+1
** 1024*131072^n+1
** 2048*131072^n+1
** 4096*131072^n+1
** 16384*131072^n+1

But since these cases are very rarely happen, these programs are >99% sufficient

[sweety439]

A PRP number (k*b^n+-1)/gcd(k+-1,b-1) with large n can be proven be prime if and only if:

either

* gcd(k+-1,b-1) = 1

or

* gcd(k+-1,b-1) = k'+-1 (k' is the reduced k, i.e. k' = k/(b^r) which r is largest number such that this number is integer (i.e. r = valuation(k,b) in PARI), if k is not multiple of b (MOB), then k' = k) and the number b^n-1 (= prod_(d|n)Phi_d(b), where Phi is the cyclotomic polynomial) has >= 33.3333% factored

[sweety439]

Re-update the files for all Sierpinski/Riesel conjectures for bases 2<=b<=128 and bases b = 256, 512, 1024

Also see https://github.com/xayahrainie4793/E...el-conjectures for these files online.

[sweety439]

Some algebra factors for the k's which is not (perfect power for Riesel case) (perfect odd power or of the form 4*m^4 for Sierpinski case):

* S48 k=36 (n = 1 mod 3 and n = 2 mod 4 are algebraic)
* S200 k=5 (n = 1 mod 3 are algebraic)
* S200 k=16 (n = 2 mod 4 are algebraic, and make this k have full covering set with partial algebraic factors)
* S200 k=40 (n = 1 mod 3 are algebraic)
* S529 k=184 (n = 1 mod 3 are algebraic)
* S968 k=11 (n = 1 mod 3 are algebraic)
* R12 k=27 (n = 1 mod 2 and n = 0 mod 3 are algebraic, and make this k have full covering set with partial algebraic factors)
* R12 k=300 (n = 1 mod 2 are algebraic, and make this k have full covering set with partial algebraic factors)
* R18 k=50 (n = 1 mod 2 are algebraic)
* R40 k=490 (n = 1 mod 2 are algebraic)
* R80 k=10 (n = 2 mod 3 are algebraic)
* R88 k=3773 (n = 2 mod 3 are algebraic)
* R392 k=7 (n = 1 mod 3 are algebraic)
* R392 k=56 (n = 1 mod 3 are algebraic)
* R432 k=3 (n = 1 mod 2 are algebraic)
* R578 k=2 (n = 1 mod 2 are algebraic)
* R588 k=3 (n = 1 mod 2 are algebraic)
* R750 k=6 (n = 2 mod 3 are algebraic)
* R800 k=5 (n = 2 mod 5 are algebraic)
* R800 k=8 (n = 1 mod 2 and n = 0 mod 3 are algebraic)
* R800 k=25 (n = 0 mod 2 and n = 4 mod 5 are algebraic)
* R972 k=3 (n = 1 mod 2 are algebraic)
* R972 k=8 (n = 0 mod 3 and n = 1 mod 5 are algebraic)
* R1152 k=2 (n = 1 mod 2 are algebraic)

[sweety439]

Originally Posted by sweety439

Some algebra factors for the k's which is not (perfect power for Riesel case) (perfect odd power or of the form 4*m^4 for Sierpinski case):

* S48 k=36 (n = 1 mod 3 and n = 2 mod 4 are algebraic)
* S200 k=5 (n = 1 mod 3 are algebraic)
* S200 k=16 (n = 2 mod 4 are algebraic, and make this k have full covering set with partial algebraic factors)
* S200 k=40 (n = 1 mod 3 are algebraic)
* S529 k=184 (n = 1 mod 3 are algebraic)
* S968 k=11 (n = 1 mod 3 are algebraic)
* R12 k=27 (n = 1 mod 2 are algebraic, and make this k have full covering set with partial algebraic factors)
* R12 k=300 (n = 1 mod 2 are algebraic, and make this k have full covering set with partial algebraic factors)
* R18 k=50 (n = 1 mod 2 are algebraic)
* R40 k=490 (n = 1 mod 2 are algebraic)
* R80 k=10 (n = 2 mod 3 are algebraic)
* R88 k=3773 (n = 2 mod 3 are algebraic)
* R392 k=7 (n = 1 mod 3 are algebraic)
* R392 k=56 (n = 1 mod 3 are algebraic)
* R432 k=3 (n = 1 mod 2 are algebraic)
* R578 k=2 (n = 1 mod 2 are algebraic)
* R588 k=3 (n = 1 mod 2 are algebraic)
* R750 k=6 (n = 2 mod 3 are algebraic)
* R800 k=5 (n = 2 mod 5 are algebraic)
* R800 k=8 (n = 1 mod 2 and n = 0 mod 3 are algebraic)
* R800 k=25 (n = 0 mod 2 and n = 4 mod 5 are algebraic)
* R972 k=3 (n = 1 mod 2 are algebraic)
* R972 k=8 (n = 0 mod 3 and n = 1 mod 5 are algebraic)
* R1152 k=2 (n = 1 mod 2 are algebraic)

A k-value which does not have covering set is proven composite by full algebraic factors if and only if all n-values are algebraic (e.g. R4 k=1, R4 k=9, R9 k=1, R9 k=4, S8 k=27, S27 k=8)

A k-value which does not have covering set is proven composite by partial algebraic factors if and only if there is covering set for all n-values which is not algebraic (e.g. R12 k=25, R12 k=27, R19 k=4, R28 k=175, R30 k=1369, S55 k=2500)

Both cases of k-values are excluded from the conjectures.