Problems & Puzzles:
Find the next prime of the
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
During the week 6-12 March, 2012, contributions came from Richard Chen,
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.
I am sending you a partial proof and a computed contribution for
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.