For some k's without covering set, k*b^n+-1 still cannot be prime because of the algebra factors, thus, we can choose the solve another problem, if k*b^n+-1 has r-almost prime candidate but no (r-1)-almost prime candidate, then we want to find an r-almost prime (this r-almost prime should not have small prime factor) of the form k*b^n+-1.

For the k's with full algebra factors, we need to find an n such that all the factors are primes.

For the k's with partial algebra factors, we need to find an n with algebra factors but all the factors are primes.

These are the status for some k's with full/partial algebra factors for Sierpinski/Riesel bases b<=64:

S8, k=1: factors to (1*2^n + 1) * (1*4^n - 1*2^n + 1), and the two numbers are both primes for n = 1, 2, 4, ...

S8, k=8: factors to (2*2^n + 1) * (4*4^n - 2*2^n + 1), and the two numbers are both primes for n = 1, 3, ...

S16, k=2500: factors to (50*4^n + 10*2^n + 1) * (50*4^n - 10*2^n + 1), and the two numbers are both primes for n = 6, ...

S16, k=40000: factors to (200*4^n + 20*2^n + 1) * (200*4^n - 20*2^n + 1), and the two numbers are both primes for n = 5, ...

S27, k=8: factors to (2*3^n + 1) * (4*9^n - 2*3^n + 1), and the two numbers are both primes for n = 1, 2, 4, ...

S27, k=216: factors to (6*3^n + 1) * (36*9^n - 6*3^n + 1), and the two numbers are both primes for n = 1, 3, ...

S27, k=512: factors to (8*3^n + 1) * (64*9^n - 8*3^n + 1), and the two numbers are both primes for n = 2, ...

S32, k=1: factors to (1*2^n + 1) * (1*16^n - 1*8^n + 1*4^n - 1*2^n + 1), and the two numbers are both prime for n = 1, 4, 8, ...

S63, k=3511808: if n=3q, factors to (152*63^q + 1) * (23104*3969^q - 152*63^q + 1), the two numbers are not both prime for all q<=1000.

S63, k=27000000: if n=3q, factors to (300*63^q + 1) * (90000*3969^q - 300*63^q + 1), the two numbers are not both prime for all q<=1000.

S64, k=1: factors to (1*4^n + 1) * (1*16^n - 1*4^n + 1), and the two numbers are both primes for n = 1, 2, ...

R9, k=4: factors to (2*3^n - 1) * (2*3^n + 1), and the two numbers are both primes for n = 1, 2, ...

R9, k=16: factors to (4*3^n - 1) * (4*3^n + 1), and the two numbers are both primes for n = 1, 3, 15, ...

R9, k=36: factors to (6*3^n - 1) * (6*3^n + 1), and the two numbers are both primes for n = 1, ...

R9, k=64: factors to (8*3^n - 1) * (8*3^n + 1), and the two numbers are both primes for n = 2, 10, ...

R12, k=25: if n=2q, factors to (5*12^q - 1) * (5*12^q + 1), and the two numbers are both primes for q = 1, ...

R12, k=27: if n=2q+1, factors to (18*12^q - 1) * (18*12^q + 1), and the two numbers are both primes for q = 1, 3, ...

R12, k=64: if n=2q, factors to (8*12^q - 1) * (8*12^q + 1), and the two numbers are both primes for q = 2, ...

R12, k=300: if n=2q+1, factors to (60*12^q - 1) * (60*12^q + 1), the two numbers are not both prime for all q<=1000.

R12, k=324: if n=2q, factors to (18*12^q - 1) * (18*12^q + 1), and the two numbers are both primes for q = 2, ...

For all the bases above except S63 and R12, this problem is proven for the k's with algebra factors in the original problems. However, S16, S27 and S32 are still not proven since their original problem are not proven, all other bases above are

**completely proven**. (note that I do not exclude GFNs in the conjectures, thus, in my definition, S32 is not proven, and it has only k=4 remain)

That is, there is known semiprime of all the forms above but 3511808*63^n+1 (n%3=0), 27000000*63^n+1 (n%3=0), 300*12^n-1 (n%2=1), all the forms above have no prime candidate, but all have semiprime candidate.

There are many such k's for R4, R16, R19, R24, R25, and some other Riesel bases. In fact, the R4 problem is the same as the twin Proth/Riesel primes problem, since if k is square and gcd(k-1,4-1) = 1, then k is divisible by 3, and let k = m^2, k*4^n-1 factors to (m*2^n-1) * (m*2^n+1), this m is also divisible by 3, and find an n such that the two numbers are both primes is the same as the twin Proth/Riesel primes problem, see

http://mersenneforum.org/showthread.php?t=8479. According to this website, this problem still has 7 k's remain for k's with algebra factors in the original problem and k<39939: 12321, 15129, 23409, 25281, 29241, 33489, 35721. (these k's equal 111^2, 123^2, 153^2, 159^2, 171^2, 183^2, 189^2)