Below, is the definition of a **prime-partitionable** integer taken from W. Holsztynski, R. F. E. Strube, [Paths and circuits in finite groups](http://www.sciencedirect.com/science/article/pii/0012365X78900596), 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](https://www.renyi.hu/~p_erdos/1978-49.pdf), 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.



Proofs needed for observations regarding prime-partitionable numbers
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


