Proofs needed for observations regarding prime-partitionable numbers

Question

Below, is the definition of a prime-partitionable integer taken from W. Holsztynski, R. F. E. Strube, Paths and circuits in finite groups, Discr. Math. 22 (1978) 263-272 and is apparently the same in W. T. Trotter, Jr. and Paul Erdős, When the Cartesian product of directed cycles is Hamiltonian, J. Graph Theory 2 (1978) 137-142 DOI:10.1002/jgt.3190020206:

An integer $n>=2$ is said to be prime-partitionable if there is a partition {$P_1,P_2$} of the set $P$ of all primes less than $n$ such that, for all natural numbers $n_1$ and $n_2$ satisfying $n_1+n_2=n$ we have that either $gcd(n_1,p_1) \ne 1$ or $gcd(n_2,p_2) \ne 1$ or both, for some pair $(p_1,p_2) \in P_1 \times P_2$.

Conjectures: If $P_1 =$ {$p_{1a}, p_{1b}$}, $p_{1a}$ and $p_{1b}$ are odd primes and $p_{1a}< p_{1b}$, it appears that, if $\psi = kp_{1a} + 1 = p_{1b} + p_{1a}$ for $k$ odd and $1 < k ≤ p_{1a}-2 $ then:

1. $\psi$ is prime-partitionable,

2. no two values of $p_{1b}$ are the same and

3. the number of values of $k$ is $≥ 1$ for each $p_{1a} ≥ 5$.

The following six sequences in the OEIS contain the results of my investigations into prime-partitionable numbers and their equivalence to Erdös-Woods numbers:

A059756, A244640, A245664, A249302, A245372, A259560

Can proofs be found for the conjectures please.

Answer 1

Let's assume a limited (and unproved) version of Linnik's theorem: There is a prime $q$ of the form $kp + 1$ for $k \leq (p-2)$ and $p$ a prime. Experimentally this is true, and can be proved for many primes, but at present not all. With this in hand, the proofs of the conjectures are exercises:

• 1) note that any number $n= n_1 + n_2$ with $n_2$ coprime to all but at most two primes less than $n$ must either have $n_2=1$, or else $n_2$ must have a prime factorization consisting of at most those two singled-out primes. Throw in the other conditions (and the assumption), and we get that $n_2$ is 1 or one of the two primes. Now the additional equations have to be satisfied for $n$ to be prime partitionable with respect to the given partition. The only problem is the existence of $k$ of the desired form, which we have already taken as an assumption.

• 2) Not sure what this means, but if $p_{1a}$ is fixed and $k$ varies, the primes $p_{1b}$ will vary.

• 3) If the first prime is 3, that restricts things too much. If it is 5 or greater, the assumption quickly yields the result.

So for a given number $n$, it is prime partitionable with respect to a special partition (the first part consisting of two primes) if it has the form given by the equations and restrictions involving $k$, and our assumption above holds. However, the assumption is a strong version of Linnik's theorem on primes in arithmetic progressions, and is the chief reason why an otherwise simple exercise remains a conjecture.

Gerhard "Deep Thoughts Upon Shallow Problems" Paseman, 2015.08.03