A Sierpinski/Riesel-like problem

[sweety439]

Originally Posted by sweety439

Reserve all 1k base (only 1 remain k that is neither GFN nor half GFN nor in CRUS) 65<=b<=105.

These bases are:

S83 (k=3), S85 (k=70), S88 (k=8), R67 (k=25), R75 (k=35), R91 (k=27), R94 (k=16), R100 (k=133).

Found three (probable) primes:

70*85^1586+1
(8*88^1094+1)/3
(35*75^1844-1)/2

Thus, S85, S88 and R75 are proven.

[kar_bon]

Originally Posted by sweety439

Thus, will you reserve S10, k=269?

No, I thought it was clear, I got my own work: 158 hours of my work here and you're unable to run WinPFGW?

You're testing to n~1500, which is done in seconds with pfgw. I don't know which program you're using so how much can you/we trust your results.

Notes:
- Stop posting tons of files and posts with pages of numbers, update the Wiki pages instead.
- You gave some values in bold, but nowhere explained the meaning.
- Change the display style of the table like this: it's more compact and easier to watch
- Give the GCD for every k-val (I know it's easy to calculate, but noone will do this for many k-values, see example for base 2 & 3)
- Put more own work on current given values instead of creating more new conjectures (2nd, 3rd, 4th CK).

[sweety439]

Originally Posted by sweety439

Completed extended SR15 for k<=10000 (tested to n=1500).

The remain k's <= 10000 for S15 are: (include the k's without from testing)

225, 341, 343, 641, 965, 1205, 1827, 2263, 2323, 2403, 2445, 2461, 2471, 2531, 2813, 3347, 3375, 3625, 3797, 3935, 3959, 4045, 4169, 4355, 4665, 4733, 5115, 5145, 5169, 5793, 5891, 5983, 6061, 6331, 6476, 6553, 6598, 6661, 6775, 6849, 7087, 7693, 7711, 7773, 7975, 7979, 8017, 8161, 8181, 8271, 8603, 8881, 9215, 9615, 9643, 9767, 9783, 9857

[sweety439]

Originally Posted by sweety439

Completed extended SR15 for k<=10000 (tested to n=1500).

The remain k's <= 10000 for R15 are: (include the k's without from testing)

47, 203, 239, 407, 437, 451, 705, 889, 893, 1945, 2049, 2245, 2487, 2507, 2689, 2699, 2863, 2940, 3045, 3059, 3163, 3179, 3261, 3409, 3585, 3697, 3701, 3725, 4173, 4249, 4609, 4771, 4877, 5041, 5243, 5425, 5441, 5503, 5669, 5857, 5913, 5963, 6105, 6231, 6447, 6555, 6765, 6787, 6879, 6999, 7386, 7407, 7459, 7473, 7527, 7615, 7683, 7687, 7859, 8099, 8610, 8621, 8671, 8839, 8863, 9025, 9267, 9409, 9655, 9663, 9707, 9817, 9955

[sweety439]

Originally Posted by sweety439

The remain k's <= 10000 for S15 are: (include the k's without from testing)

225, 341, 343, 641, 965, 1205, 1827, 2263, 2323, 2403, 2445, 2461, 2471, 2531, 2813, 3347, 3375, 3625, 3797, 3935, 3959, 4045, 4169, 4355, 4665, 4733, 5115, 5145, 5169, 5793, 5891, 5983, 6061, 6331, 6476, 6553, 6598, 6661, 6775, 6849, 7087, 7693, 7711, 7773, 7975, 7979, 8017, 8161, 8181, 8271, 8603, 8881, 9215, 9615, 9643, 9767, 9783, 9857

The k's from the same family are:

{225, 3375}
{341, 5115}
{343, 5145}
{641, 9615}

Thus, the remain k<=10000 for S15 are: (totally 54 k's)

225, 341, 343, 641, 965, 1205, 1827, 2263, 2323, 2403, 2445, 2461, 2471, 2531, 2813, 3347, 3625, 3797, 3935, 3959, 4045, 4169, 4355, 4665, 4733, 5169, 5793, 5891, 5983, 6061, 6331, 6476, 6553, 6598, 6661, 6775, 6849, 7087, 7693, 7711, 7773, 7975, 7979, 8017, 8161, 8181, 8271, 8603, 8881, 9215, 9643, 9767, 9783, 9857

[sweety439]

Originally Posted by sweety439

The remain k's <= 10000 for R15 are: (include the k's without from testing)

47, 203, 239, 407, 437, 451, 705, 889, 893, 1945, 2049, 2245, 2487, 2507, 2689, 2699, 2863, 2940, 3045, 3059, 3163, 3179, 3261, 3409, 3585, 3697, 3701, 3725, 4173, 4249, 4609, 4771, 4877, 5041, 5243, 5425, 5441, 5503, 5669, 5857, 5913, 5963, 6105, 6231, 6447, 6555, 6765, 6787, 6879, 6999, 7386, 7407, 7459, 7473, 7527, 7615, 7683, 7687, 7859, 8099, 8610, 8621, 8671, 8839, 8863, 9025, 9267, 9409, 9655, 9663, 9707, 9817, 9955

The k's from the same family are:

{47, 705}
{203, 3045}
{239, 3585}
{407, 6105}
{437, 6555}
{451, 6765}

Thus, the remain k<=10000 for R15 are: (totally 67 k's)

47, 203, 239, 407, 437, 451, 889, 893, 1945, 2049, 2245, 2487, 2507, 2689, 2699, 2863, 2940, 3059, 3163, 3179, 3261, 3409, 3697, 3701, 3725, 4173, 4249, 4609, 4771, 4877, 5041, 5243, 5425, 5441, 5503, 5669, 5857, 5913, 5963, 6231, 6447, 6787, 6879, 6999, 7386, 7407, 7459, 7473, 7527, 7615, 7683, 7687, 7859, 8099, 8610, 8621, 8671, 8839, 8863, 9025, 9267, 9409, 9655, 9663, 9707, 9817, 9955

[sweety439]

Completed all extended Sierpinski and Riesel bases 65<=b<=128 (except SR66, S70, SR78, SR82, SR96, SR106, SR108, SR112, SR120, SR124, SR126 and SR127).


These are the text files.

Note:

For S125, all k = m^3 proven composite by full algebra factors.
For S128, all k = m^7 proven composite by full algebra factors.
For S128, all k = 2^r with r = 3, 5 or 6 mod 7 has no possible prime, see post #265.

For R109, all k = m^2 with m = 2 or 3 mod 5 proven composite by partial algebra factors.
For R110, all k = m^2 with m = 6 or 31 mod 37 proven composite by partial algebra factors.
For R114, all k = m^2 with m = 2 or 3 mod 5 proven composite by partial algebra factors.
For R118, all k = m^2 with m = 4 or 13 mod 17 proven composite by partial algebra factors.
For R121, all k = m^2 proven composite by full algebra factors.
For R125, all k = m^3 proven composite by full algebra factors.
For R128, all k = m^7 proven composite by full algebra factors.

The prime 4*107^32586+1 (S107, k=4) is given by CRUS.
The prime 20*110^933+1 (S110, k=20) is given by CRUS.
The prime 4*113^2958+1 (S113, k=4) is given by CRUS.
The prime 30*115^47376+1 (S115, k=30) is given by CRUS.
The prime 2*122^755+1 (S122, k=2) is given by CRUS.
The prime 16*122^764+1 (S122, k=16) is given by CRUS.
The prime 25*122^674+1 (S122, k=25) is given by CRUS.
The prime 31*122^1236+1 (S122, k=31) is given by CRUS.
The prime 37*122^1622+1 (S122, k=37) is given by CRUS.
The prime 41*128^39271+1 (S128, k=41) is given by CRUS.
The prime 42*128^13001+1 (S128, k=42) is given by CRUS.

The prime 2*107^21910-1 (R107, k=2) is given by CRUS.
The prime 17*110^2598-1 (R110, k=17) is given by CRUS.
The prime 23*110^78120-1 (R110, k=23) is given by CRUS.
The prime 37*110^1689-1 (R110, k=37) is given by CRUS.
The prime 29*118^599-1 (R118, k=29) is given by CRUS.
The prime 62*121^13101-1 (R121, k=62) is given by CRUS.
The prime 23*128^2118-1 (R128, k=23) is given by CRUS.
The prime 26*128^1442-1 (R128, k=26) is given by CRUS.
The prime 29*128^211192-1 (R128, k=29) is given by CRUS.
The prime 37*128^699-1 (R128, k=37) is given by CRUS.

Some test limits converted by CRUS:

S117, k=58: at n=250K.
S118, k=48: at n=700K.
S122, k=34: at n=700K.
S128, k=40: at n=1.2857M.

(no such k's for all tested Riesel bases 105<b<=128)

Some test limits converted by GFN stats:

S122, k=1: at n=2^24-1.
S128, k=16: at n=(2^35-4)/7-1

[sweety439]

Originally Posted by sweety439

Completed all extended Sierpinski and Riesel bases 65<=b<=128 (except SR66, S70, SR78, SR82, SR96, SR106, SR108, SR112, SR120, SR124, SR126 and SR127).


These are the text files.

The remain k's for these Sierpinski bases b>105 are: (b<=105 are already posted in #295)

base   remain k
S107   1
S109   1
S110   none (proven)
S111   none (proven)
S113   13, 17
S114   none (proven)
S115   17, 47, 50
S116   none (proven)
S117   11, 58, 59, 75, 117
S118   48
S119   none (proven)
S121   none (proven)
S122   1, 34
S123   1, 3, 41
S125   none (proven)
S128   16, 40

[sweety439]

Originally Posted by sweety439

Completed all extended Sierpinski and Riesel bases 65<=b<=128 (except SR66, S70, SR78, SR82, SR96, SR106, SR108, SR112, SR120, SR124, SR126 and SR127).


These are the text files.

The remain k's for these Riesel bases b>105 are: (b<=105 are already posted in #296)

base   remain k
R107   3
R109   none (proven)
R110   none (proven)
R111   none (proven)
R113   none (proven)
R114   none (proven)
R115   4, 13, 23, 43, 45, 51
R116   none (proven)
R117   5, 17, 33, 141
R118   27, 43
R119   none (proven)
R121   79
R122   none (proven)
R123   11
R125   none (proven)
R128   none (proven)

[sweety439]

Originally Posted by sweety439

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)

proof:

First, if b^n+1 (for even b) or (b^n+1)/2 (for odd b) is prime, then n must be a power of 2 (including 1), since if m is an odd factor of n and m>1, then

For even b, b^n+1 = (b^(n/m)+1) * (b^((m-1)n/m)-b^((m-2)n/m)+b^((m-3)n/m)-...-b^(3n/m)+b^(2n/m)-b^(n/m)+1)

and both of the two factors are > 1

For odd b, (b^n+1)/2 = ((b^(n/m)+1)/2) * (b^((m-1)n/m)-b^((m-2)n/m)+b^((m-3)n/m)-...-b^(3n/m)+b^(2n/m)-b^(n/m)+1)

and both of the two factors are > 1

Thus b^n+1 (for even b) or (b^n+1)/2 (for odd b) is composite.

Second, if b = q^m and k = q^r, then k*b^n+1 = q^(r+n*m)+1

Thus, if k*b^n+1 (for even b) or (k*b^n+1)/2 (for odd b) is prime, then r+n*m must be a power of 2, let it be 2^s, thus r+n*m = 2^s, thus 2^s = n*m+r, thus 2^s = r mod m. Thus, if the equation 2^x = r (mod m) has no solution, then k*b^n+1 (for even b) or (k*b^n+1)/2 (for odd b) is always composite.

Finally, we choose some values of m:

m    2^n mod m (start with n=0)
1    0, 0, 0, ...
2    1, 0, 0, 0, ...
3    1, 2, 1, 2, 1, 2, ...
4    1, 2, 0, 0, 0, ...
5    1, 2, 4, 3, 1, 2, 4, 3, ...
6    1, 2, 4, 2, 4, 2, 4, ...
7    1, 2, 4, 1, 2, 4, 1, 2, 4, ...
8    1, 2, 4, 0, 0, 0, ...
9    1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7, 5, ...
10   1, 2, 4, 8, 6, 2, 4, 8, 6, ...
11   1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, ...
12   1, 2, 4, 8, 4, 8, 4, 8, ...

We found that if m = 7, then 2^n mod m cannot be 3, 5, 6. Thus, if m = 7 and r = 3, 5 or 6 mod 7, then 2^x = r (mod m) has no solution and k*b^n+1 (for even b) or (k*b^n+1)/2 (for odd b) is always composite. (for all other m<=12, for all r satisfy these two conditions: (1) m and r have no common odd prime factor, (2) the exponent of highest power of 2 dividing r >= the exponent of highest power of 2 dividing m, 2^x = r (mod m) has a solution, the next m with an r satisfy those two conditions and 2^x = r (mod m) has no solution is 14, if r = 6, 10, 12 (mod 14), then 2^x = r (mod m) has no solution, the next such m is 15, if r = 7, 11, 13, 14 (mod 15), then 2^x = r (mod m) has no solution, for all such examples up to m = 33, see post #265)

[sweety439]

Originally Posted by sweety439

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)

If m and r have a common odd prime factor, let it be p, then k*b^n+1 can be written as x^p+1, thus it has algebra factors and is already excluded. (In fact, k*b^n+1 has algebra factors if and only if m and r have a common odd prime factor)

If the exponent of highest power of 2 dividing r < the exponent of highest power of 2 dividing m, then gcd(k+1,b-1) is neither 1 nor 2, thus this number is neither GFN nor GFN, this number is a generalized repunit number in a negative base. (In fact, gcd(k+1,b-1) is either 1 or 2 if and only if the exponent of highest power of 2 dividing r >= the exponent of highest power of 2 dividing m)