# [seqfan] Is 52 prime-partitionable?

Richard J. Mathar mathar at mpia-hd.mpg.de
Sun Jun 29 17:06:58 CEST 2014

```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.

Taken from:
W. Holsztynski, R. F. E. Strube, Paths and circuits in finite groups, Discr. Math. 22 (1987) 263-272, doi
and apparently the same as in
W. T. Trotter, Jr, When the Cartesian product of directed cycles is Hamiltonian, J. Graph Theory 2 (1978) 137-142

I interpret the definition as follows: "for some pair (p1,p2)" means we
need to find a fixed 2-set partition of these primes, and then check for
all partitions n=n1+n2 that we can find a pair p1 in P1 and p2 in P2 with
at least one of the two gcd's larger than 1. 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.
So here is some probability that this set is actually just A059756
in disguise.

So my basic question is: is 52 prime-partitionable as claimend?
And the secondary question is: is that correct set of integers in the OEIS?

For the set {16,22,34,36,...} of numbers that are prime-partitionable
we have the following pairs of prime-number sets:

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:                  {5, 11, 17, 19, 31}, {2, 3, 7, 13, 23, 29}
46:            {5, 7, 11, 13, 23, 41}, {2, 3, 17, 19, 29, 31, 37, 43}
56:        {5, 7, 13, 17, 31, 41, 43}, {2, 3, 11, 19, 23, 29, 37, 47, 53}
64:    {3, 11, 31, 37, 43, 53, 61}, {2, 5, 7, 13, 17, 19, 23, 29, 41, 47, 59}
66:    {7, 13, 17, 19, 31, 47, 53, 59}, {2, 3, 5, 11, 23, 29, 37, 41, 43, 61}
70:  {11, 17, 23, 37, 47, 53, 59}, {2, 3, 5, 7, 13, 19, 29, 31, 41, 43, 61, 67}

Example for n=22 (covered by the two prime sets shown):
1+21 matched by p2=3, igcd(21,3) > 1
2+20 matched by p2=2, igcd(20,2) > 1
3+19 matched by p2=19, igcd(19,19 > 1
4+18 matched by p2=18, igcd(18,2) > 1
5+17 matched by p1=5, igcd(5,5) > 1
6+16 matched by p2=2, igcd(16,2) > 1
7+15 matched by p1=7, igcd(7,7) > 1
8+14 matched by p2=14, igcd(14,2) > 1
9+13 matched by p2=13, igcd(13,13) > 1
10+12 matched by p2=2, igcd(12,2) > 1
11+11 matched by p2=11, igcd(11,11) > 1
12+10 matched by p2=10, igcd(10,2) > 1
13+9 matched by p2=3, igcd(9,3) > 1
14+8 matched by p2=2, igcd(8,2) > 1
15+7 matched by p1=5, igcd(15,5) > 1
16+6 matched by p2=2, igcd(6,2) > 1
17+5 matched by p1=17, igcd(17,17) > 1
18+4 matched by p2=2, igcd(4,2) > 1
19+3 matched by p2=3, igcd(3,3) > 1
20+2 matched by p2=2, igcd(2,2) > 1
21+1 matched by p1=7, igcd(21,7) > 1

Found by the following Maple program:

# true if n is prime-partitionable, false if not.
ppartabl := proc(n)
local pless,p1,p2,n1,n2,p1set,p2set ;
# construct set of primes < n in pless.
pless := {} ;
for i from 2 to n-1 do
if isprime(i) then
pless := pless union {i} ;
end if;
end do:

# loop over all non-trivial (non-empty) subsets of the primes, P1
for pset1 in combinat[choose](pless) do
if nops(pset1) >= 1 then
# P2 is P \ P1
pset2 := pless minus pset1 ;
# flag to indicate that for each n1,n2 we found a pair
alln1n2done := true ;
for n1 from 1 to n-1 do
n2 := n-n1 ;
# flag that we found a (p1,p2)
foundp1p2 := false;
for p1 in pset1 do
if igcd(n1,p1) <> 1 then
foundp1p2 := true ;
break ;
end if;
for p2 in pset2 do
if igcd(n2,p2) <> 1 then
foundp1p2 := true;
break;
end if;
end do:
if foundp1p2 = true then
break;
end if;
end do:
if foundp1p2 = false then
alln1n2done := false ;
break ;
end if;
end do:
if alln1n2done = true then
print(pset1,pset2) ;
return true;
end if;
end if;
end  do:
return false ;
end proc:

for n from 2 do
if ppartabl(n) then
printf("%d,\n",n) ;
end if;
end do:

--
Richard J. Mathar
```