[seqfan] Re: Is 52 prime-partitionable?

[M. F. Hasler]

On Sun, Jun 29, 2014 at 11:06 AM, Richard J. Mathar
<mathar at mpia-hd.mpg.de> wrote:
> There is a definition of prime-partitionable numbers n as follows:
> An integer n>=2 is said to be prime-partitionable if there is a
> partition {P1,P2} of the set P of all primes less than n such that, for
> all natural numbers n1 and n2 satisfying n1+n2=n we have that either
> gcd(n1,p1) <> 1 or gcd(n2,p2) <> 1 or both, for some pair (p1,p2) = P1 X P2.
(...)
> So the two primes p1 and p2 may depend on n1 and n2, but the disjoint
> sets P1 and P2 are not a function of n1 and n2.
>
> The point is that I cannot find how 52 is prime-partitionable, although
> claimed to have that property by Hostynsik-Strubbe and Trotter.

I confirm your reasoning and the list:
for(n=1,90,(t=prime_part(n))&& print(n","t","))
16,[[5, 11], [2, 3, 7, 13]],
22,[[5, 7, 17], [2, 3, 11, 13, 19]],
34,[[11, 23], [2, 3, 5, 7, 13, 17, 19, 29, 31]],
36,[[7, 29], [2, 3, 5, 11, 13, 17, 19, 23, 31]],
46,[[5, 7, 11, 13, 41], [2, 3, 17, 19, 23, 29, 31, 37, 43]],
56,[[5, 13, 17, 31, 43], [2, 3, 7, 11, 19, 23, 29, 37, 41, 47, 53]],
64,[[5, 7, 13, 17, 19, 29, 47, 59], [2, 3, 11, 23, 31, 37, 41, 43, 53, 61]],
66,[[13, 53], [2, 3, 5, 7, 11, 17, 19, 23, 29, 31, 37, 41, 43, 47, 59, 61]],
70,[[23, 47], [2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 53, 59, 61, 67]],
76,[[5, 17, 59, 71], [2, 3, 7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47,
53, 61, 67, 73]],
78,[[11, 67], [2, 3, 5, 7, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 71, 73]],
86,[[7, 17, 23, 37, 79], [2, 3, 5, 11, 13, 19, 29, 31, 41, 43, 47, 53,
59, 61, 67, 71, 73, 83]],
88,[[29, 59], [2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53,
61, 67, 71, 73, 79, 83]],

with the following code
(PARI)
prime_part(n)={my(P=primes(primepi(n-1)))/* primes less than n */;
forstep(x1=2,2^#P-1,2, P1=vecextract(P,x1); P2=setminus(P,P1)/* always
holds p2=2 */;
for(n1=1,n-1, bittest(n-n1,0) || next /* n2 even => OK */;
/* we do not impose n1<=n2 since we do impose that P2 is the subset
that holds the prime 2 */
setintersect(P1,factor(n1)[,1]~) && next /* OK */;
setintersect(P2,factor(n-n1)[,1]~) && next /* OK */;
next(2) /* for this (n1,n2) the condition is not satisfied so we have
to find another P1,P2 */
)/* end for n1 */; return([P1,P2]))} /* return "fail" if no P1,P2 found */


PS:
The "n>=2" in the definition is misleading, one could as well write n>=0
(No partition {P1,P2} can exist for n<4, since there's only one prime
less than 3).

Maximilian