mersenneforum.org - A Sierpinski/Riesel-like problem

mersenneforum.org (https://www.mersenneforum.org/index.php)

- sweety439 (https://www.mersenneforum.org/forumdisplay.php?f=137)

- - A Sierpinski/Riesel-like problem (https://www.mersenneforum.org/showthread.php?t=21839)

[QUOTE=sweety439;460350]The 1st, 2nd and 3rd conjecture of Sierpinski/Riesel bases 4, 5, 7, 8, 9, 10, 11, 12, 13, 14 and 16 are:

[CODE]
base 1st 2nd 3rd
S4 419 659 794
S5 7 11 31
S7 209 1463 3305
S8 47 79 83
S9 31 39 111
S10 989 1121 3653
S11 5 7 17
S12 521 597 1143
S13 15 27 47
S14 4 11 19
S16 38 194 524
R4 361 919 1114
R5 13 17 37
R7 457 1291 3199
R8 14 112 116
R9 41 49 74
R10 334 1585 1882
R11 5 7 17
R12 376 742 1288
R13 29 41 69
R14 4 11 19
R16 100 172 211
[/CODE]Now, I only decide to reserve the 1st, 2nd and 3rd conjecture of Sierpinski/Riesel bases 5, 8, 9, 11, 13, 14 and 16, since the 2nd and 3rd conjecture for other bases b<=16 are larger.[/QUOTE]

The 1st, 2nd and 3rd conjectures for S2 are not {78557, 271129, 271577}, they are {78557, 157114, 271129}, since we also include the k-values that are a multiple of base (b) (included in the conjectures, but excluded from testing if (k+-1)/gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) is not prime).

[QUOTE=sweety439;501815]The 1st, 2nd and 3rd conjectures for S2 are not {78557, 271129, 271577}, they are {78557, 157114, 271129}, since we also include the k-values that are a multiple of base (b) (included in the conjectures, but excluded from testing if (k+-1)/gcd(k+-1,b-1) (+ for Sierpinski, - for Riesel) is not prime).[/QUOTE]

Note: 1 is not considered prime (it is unit), thus, 7 [B]is[/B] included from testing for R7 since although 7 is a multiple of 7, but (7-1)/gcd(7-1,7-1) = 6/6 = 1 is not prime, however, 36 is not included from testing for R6 since 36 is a multiple of 6 and (36-1)/gcd(36-1,6-1) = 35/5 = 7 is prime.

[QUOTE=sweety439;501817]Note: 1 is not considered prime (it is unit), thus, 7 [B]is[/B] included from testing for R7 since although 7 is a multiple of 7, but (7-1)/gcd(7-1,7-1) = 6/6 = 1 is not prime, however, 36 is not included from testing for R6 since 36 is a multiple of 6 and (36-1)/gcd(36-1,6-1) = 35/5 = 7 is prime.[/QUOTE]

Besides, the corresponding prime for R7 k=1 is not (1*7^1-1)/gcd(1-1,7-1) = 1, since 1 is not prime, the corresponding prime for R7 k=1 is (1*7^5-1)/gcd(1-1,7-1) = 1201.

Like [URL="https://en.wikipedia.org/wiki/Bunyakovsky_conjecture"]Bunyakovsky conjecture[/URL], 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. (k*b^n+c)/gcd(k+c, b-1) cannot be proved as composite for all n or prime only for very small n (like the case of (4^n-1)/3) in these three ways:

** Periodic sequence p of prime divisors with p(n) | (k*b^n+c)/gcd(k+c, b-1)
** Algebraic factors (e.g. difference-of-squares factorization, difference-of-cubes factorization, sum-of-cubes factorization, difference-of-5th-powers factorization, sum-of-5th-powers factorization, Aurifeuillian factorization of x^4+4*y^4, etc.) of k*b^n+c
** The combine of them (like the case of 25*12^n-1)

4. the triple (k, b, c) is [B][I]not[/I][/B] 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 (like the case of 8*128^n+1)

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

[QUOTE=sweety439;529838]Like [URL="https://en.wikipedia.org/wiki/Bunyakovsky_conjecture"]Bunyakovsky conjecture[/URL], 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 [B][I]not[/I][/B] 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.[/QUOTE]

If this conjecture is true, then:

* All Sierpinski (1st, 2nd, 3rd, ...) conjectures base b are true for all b>=2.
* All Riesel (1st, 2nd, 3rd, ...) conjectures base b are true for all b>=2.
* All extended Sierpinski (1st, 2nd, 3rd, ...) conjectures base b are true for all b>=2.
* All extended Riesel (1st, 2nd, 3rd, ...) conjectures base b are true for all b>=2.
* All reversed Sierpinski problems can be solved for all k.
* All reversed Riesel problems can be solved for all k.
* There are infinitely many primes of the form k*2^n+1 with integer n>=1 for all 1<=k<78557.
* There are infinitely many primes of the form k*2^n-1 with integer n>=1 for all 1<=k<509203.
* There are infinitely many primes of the form 2^n+k with integer n>=1 for all odd 1<=k<78557.
* There are infinitely many primes of the form |2^n-k| with integer n>=1 for all odd 1<=k<509203.
* There are infinitely many generalized Fermat primes b^(2^n)+1 in every even base b>=2 not of the form m^r with odd r>1.
* There are infinitely many generalized half Fermat primes (b^(2^n)+1)/2 in every odd base b>=3 not of the form m^r with odd r>1.
* There are infinitely many generalized repunit primes (b^n-1)/(b-1) in every base b>=2 not of the form m^r with r>1.
* There are infinitely many generalized Wagstaff primes (b^n+1)/(b+1) in every base b>=2 not of the form m^r with odd r>1 and not of the form 4*m^4 with integer m.
* There are infinitely many primes of the form 2*b^n-1 for all b>=2.
* There are infinitely many primes of the form 2*b^n+1 for all b>=2 and b = 0 mod 3 (not always true for b = 2 mod 3, counterexample: b = 201446503145165177, 2*201446503145165177^n+1 is divisible by at least one primes in this set for all n: {3, 5, 17, 257, 641, 65537, 6700417}).
* There are infinitely many primes of the form (2*b^n+1)/3 for all b>=2 and b = 1 mod 3.
* There are infinitely many primes of the form b^n-2 for all odd b>=3.
* There are infinitely many primes of the form b^n+2 for all b>=3 and b = 3 mod 6 (not always true for b = 5 mod 6, counterexample: b = 201446503145165177, 2*201446503145165177^n+1 is divisible by at least one primes in this set for all n: {3, 5, 17, 257, 641, 65537, 6700417}).
* There are infinitely many primes of the form (b^n+2)/3 for all b>=3 and b = 1 mod 3.
* There are infinitely many primes of the form 3*b^n-1 for all even b>=2.
* There are infinitely many primes of the form 3*b^n+1 for all even b>=2.
* There are infinitely many primes of the form (b-1)*b^n-1 for all b>=2.
* There are infinitely many primes of the form (b-1)*b^n+1 for all b>=2 such that b-1 is not of the form m^r with odd r>1 and not of the form 4*m^4.
* There are infinitely many primes of the form (b+1)*b^n-1 for all b>=2.
* There are infinitely many primes of the form b^n-(b-1) for all b>=2.
* There are infinitely many primes of the form b^n+(b-1) for all b>=2 such that b-1 is not of the form m^r with odd r>1 and not of the form 4*m^4.
* There are infinitely many primes of the form b^n-(b+1) for all b>=2.
* The "minimal prime problem" can be solved in every base b>=2.

[QUOTE=sweety439;529838]Like [URL="https://en.wikipedia.org/wiki/Bunyakovsky_conjecture"]Bunyakovsky conjecture[/URL], 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 [B][I]not[/I][/B] 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.[/QUOTE]

Examples of the condition 3:

(k, b, c) = (78557, 2, 1): (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n: {3, 5, 7, 13, 19, 37, 73}

(k, b, c) = (509203, 2, -1): (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n: {3, 5, 7, 13, 17, 241}

(k, b, c) = (419, 4, 1): (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n: {3, 5, 7, 13}

(k, b, c) = (334, 10, -1): (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n: {3, 7, 13, 37}

(k, b, c) = (7, 5, 1): (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n: {2, 3}

(k, b, c) = (13, 5, -1): (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n: {2, 3}

(k, b, c) = (1, 4, -1): k*b^n and -c are both 2nd powers for all n

(k, b, c) = (9, 4, -1): k*b^n and -c are both 2nd powers for all n

(k, b, c) = (1, 9, -1): k*b^n and -c are both 2nd powers for all n

(k, b, c) = (4, 9, -1): k*b^n and -c are both 2nd powers for all n

(k, b, c) = (1, 8, 1): k*b^n and -c are both 3rd powers for all n

(k, b, c) = (1, 8, -1): k*b^n and -c are both 3rd powers for all n

(k, b, c) = (8, 27, 1): k*b^n and -c are both 3rd powers for all n

(k, b, c) = (8, 27, -1): k*b^n and -c are both 3rd powers for all n

(k, b, c) = (4, 16, -1): "one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t" for all n

(k, b, c) = (4, 81, -1): "one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t" for all n

(k, b, c) = (324, 16, -1): "one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t" for all n

(k, b, c) = (64, 81, -1): "one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t" for all n

(k, b, c) = (4, 19, -1): k*b^n and -c are both 2nd powers for all even n, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all odd n: {5}

(k, b, c) = (4, 24, -1): k*b^n and -c are both 2nd powers for all even n, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all odd n: {5}

(k, b, c) = (1369, 30, -1): k*b^n and -c are both 2nd powers for all even n, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all odd n: {7, 13, 19}

(k, b, c) = (400, 88, -1): k*b^n and -c are both 2nd powers for all even n, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all odd n: {3, 7, 13}

(k, b, c) = (3600, 270, -1): k*b^n and -c are both 2nd powers for all even n, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all odd n: {7, 13, 37}

(k, b, c) = (343, 10, -1): k*b^n and -c are both 3rd powers for all n divisible by 3, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n not divisible by 3: {3, 37}

(k, b, c) = (3511808, 63, 1): k*b^n and -c are both 3rd powers for all n divisible by 3, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n not divisible by 3: {37, 109}

(k, b, c) = (64, 957, -1): k*b^n and -c are both 3rd powers for all n divisible by 3, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n not divisible by 3: {19, 73}

(k, b, c) = (2500, 55, 1): "one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t" for all n divisible by 4, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n not divisible by 4: {7, 17}

(k, b, c) = (16, 200, 1): "one of k*b^n and c is a 4th power, another is of the form 4*t^4 with integer t" for all n = 2 mod 4, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n not = 2 mod 4: {3, 17}

(k, b, c) = (64, 936, -1): k*b^n and -c are both 2nd powers for all even n, k*b^n and -c are both 3rd powers for all n divisible by 3, (k*b^n+c)/gcd(k+c, b-1) is divisible by at least one primes in this set for all n = 1 or 5 mod 6: {37, 109}

Examples of the condition 4:

(k, b, c) = (8, 128, 1)

(k, b, c) = (32, 128, 1)

(k, b, c) = (64, 128, 1)

(k, b, c) = (8, 131072, 1)

(k, b, c) = (32, 131072, 1)

Only the k’s that [I]may have infinitely many primes[/I] are considered.

e.g. S8 k=1, S8 k=27, S27 k=1, S16 k=4, S64 k=1, S64 k=8, S128 k=8, S128 k=32, R4 k=1, R4 k=9, R9 k=1, R9 k=4, R8 k=1, R16 k=1, R16 k=4, R8 k=27, R24 k=4, R19 k=4, R64 k=4, R64 k=8, R64 k=9, R128 k=1 are not considered, since they are [I]proved to have no primes or only finitely many primes[/I].

However, R243 k=81, S243 k=27, S38 k=1, S31 k=1, S32 k=4, S128 k=16, R185 k=1, R269 k=1 are considered, since they [I]may have infinitely many primes[/I].

I have tested R331, with CK=165, see post [URL="https://mersenneforum.org/showpost.php?p=467715&postcount=144"]https://mersenneforum.org/showpost.php?p=467715&postcount=144[/URL]

Result file attached, tested to n=1024 (the (probable) prime for k=1 is n=25033).

Reserve R394, with CK=159.

Sierpinski problem base b: Find and prove the smallest k such that (k*b^n+1)/gcd(k+1,b-1) is not prime for all n>=1

Riesel problem base b: Find and prove the smallest k such that (k*b^n-1)/gcd(k-1,b-1) is not prime for all n>=1

R394 also tested to n=1024

Note: k = m^2 and m == 2 or 3 mod 5 proven composite by partial algebraic factors.

Reserve R298 and R303 (these two bases are interesting since they have k=2 remaining at n=2000, R276 and R278 also have k=2 remaining at n=2000, but the CK of R276 is too large, and the primes of R278 are just the same as the prime of R278 in CRUS plus the prime (278^3-1)/(278-1), since 278-1 is prime, and the CK of R278 is < 278-1, also, R107 and R170 have k=2 remaining at n=2000, but I have already tested them (I have already tested all bases <= 128 (except 66, 120, 124, 126) and all bases <= 180 with small CK))