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.

  • $\begingroup$ 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? $\endgroup$ Jul 31 '15 at 23:32
  • $\begingroup$ I hope this is better now - I am on a formatting learning curve. $\endgroup$ Aug 2 '15 at 21:31
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 3 '15 at 4:29
  • $\begingroup$ Prime-partitionable numbers are mentioned at oeis.org/A244640 and oeis.org/A059756, along with some links and references. $\endgroup$ Aug 3 '15 at 4:33
  • 1
    $\begingroup$ Corrected references and added links to the papers. Replaced $pp$ by $\psi$. Verb introduced in 3rd conjecture. Included references to related OEIS sequences. $\endgroup$ 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

  • $\begingroup$ 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 $\endgroup$ Aug 4 '15 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.