Problems & Puzzles: Puzzles

Puzzle 1078 Find the next prime of the form... Sebastián Martín Ruiz sent the following puzzle Let p<q to be two consecutive primes. Q. Prove that p+(2^(p-2))(q-p) is composite for all p>3 or find a counterexample.

---

During the week 6-12 March, 2012, contributions came from Richard Chen, Alain Rochelli,

***

Richard Chen wrote:

p+(2^(p-2))(q-p) cannot be proven as composite for all primes p>3, thus it should eventually have a prime, but none is found for p<=prime(600), if a form can be proven as only contain composite numbers, then it either have covering congruence (e.g. 78557*2^n+1) or algebraic factorization (e.g. 4*9^n-1) or combine of them (e.g. 25*12^n-1), see section “proof” of this article, it has many examples and references.

If a form can be proven as only contain composite numbers by covering congruence, then every number of this form has small prime factors (usually < 10^4), and if a form can be proven as only contain composite numbers by algebraic factorization, then every number of this form has two factors with near size (for the case for difference-of-two-squares factorization) or a factor with near double the size of the other (for the case for difference-of-two-cubes factorization), if a for can be proven as only contain composite numbers by combine of them, then every number of this form meet at least one of these two conditions, but see the factorizations for n=15 and 32, they do not meet any of these two conditions, thus this form cannot be proven composite, other forms like this including 4*72^n-1, 2^n-n-2, n*13^n+1, (2^n-7)*2^n+1, 5*11^n+7*(11^n-1)/10, p*2^p+1 with prime p, (18^p-1)/17 with odd prime p, (32^p+5^p)/37 with prime p, all these forms do not have small primes, but cannot be proven as only contain composite numbers.

***

Alain wrote:

I am sending you a partial proof and a computed contribution for Puzzle 1078:

If q-p = 6*k+2 or 6*k+4 with k integer >= 0, based on congruence theory, we can prove that p+(q-p)*2^(p-2) is a multiple of 3.

In the other cases where q-p is a multiple of 6 (sequence OEIS A258578), using PARI application, I checked that there is no prime of the form p+(q-p)*2^(p-2) for p less than 75 000.

***