# Proofs needed for observations regarding prime-partitionable numbers

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.

• Can you edit this so it's readable? Is $n_1$ the same as $n1$? Does $<>$ mean $\ne$? Is $P1XP2$ meant to be $P_1\times P_2$? Is $pp$ just the name of a variable? And what does that dangling doi do? Jul 31 '15 at 23:32
• I hope this is better now - I am on a formatting learning curve. Aug 2 '15 at 21:31
• Better...still not entirely clear. So it does appear that you are using $pp$ as the name of a variable, not a common practice in math. Observation 3 no verb. Also, Trotter had a co-author for that paper, fellow named Paul Erdos. And the first paper was 1978, not 1987. Aug 3 '15 at 4:29
• Prime-partitionable numbers are mentioned at oeis.org/A244640 and oeis.org/A059756, along with some links and references. Aug 3 '15 at 4:33
• Corrected references and added links to the papers. Replaced $pp$ by $\psi$. Verb introduced in 3rd conjecture. Included references to related OEIS sequences. Aug 3 '15 at 19:23

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

• Actually, we need to make exceptions in the assumption for p=2 (so k=1) and p=3 (so k=2). However, for larger primes p, small even values of k seem to work. Gerhard "Except For Finitely Many Exceptions" Paseman, 2015.08.03 Aug 4 '15 at 2:09