OFFSET
1,1
COMMENTS
The sequence comprises the number of all possible partitions {P1,P2} for which each n is prime-partitionable.
LINKS
Christopher Hunt Gribble, List of 2-partitions
W. Holsztynski, R. F. E. Strube, Paths and circuits in finite groups, Discr. Math. 22 (1978) 263-272.
R. J. Mathar and M. F. Hasler, Is 52 prime-partitionable?, Seqfan thread (Jun 29 2014)
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.
EXAMPLE
Consider the first prime-partitionable number, A059756(1) = 16.
We have P = {2, 3, 5, 7, 11, 13}.
a(1) = 2 because the 2-partitions of P for which 16 is prime-partitionable are:
P1a = {2, 5, 11}, P2a = {3, 7, 13}
P1b = {2, 3, 7, 13}, P2b = {5, 11}
as is shown below:
n1 n2 p1a p2a p1b p2b
1 + 15 - 3 - 5
2 + 14 2 7 2 -
3 + 13 - 13 3 -
4 + 12 2 3 2 -
5 + 11 5 - - 11
6 + 10 2 - 2 5
7 + 9 - 3 7 -
8 + 8 2 - 2 -
9 + 7 - 7 3 -
10 + 6 2 3 2 -
11 + 5 11 - - 5
12 + 4 2 - 2 -
13 + 3 - 3 13 -
14 + 2 2 - 2 -
15 + 1 5 - 3 -
MAPLE
Derived from the program provided by _Richard J. Mathar_ in the second link.
ppartabl := proc (n)
local i, j, pless, p1, p2, n1, n2, pset1, pset2, alln1n2done, foundp1p2;
# construct set of primes < n in pless.
pless := {};
for i from 2 to n-1 do
if isprime(i) then
pless := `union`(pless, {i});
end if;
end do;
# loop over all nontrivial (nonempty) subsets of the primes, P1.
j := 0;
for pset1 in combinat[choose](pless) do
if 1 <= nops(pset1) then
if pset1 = pset2 then
break;
end if;
# P2 is P \ P1.
pset2 := `minus`(pless, pset1);
# flag to indicate that for each n1, n2 we found a pair.
alln1n2done := true;
for n1 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
j := j+1;
if j = 1 then
printf("%d\n", n);
end if;
print(j, pset1, pset2);
end if;
end if;
end do:
end proc:
L := [16, 22, 34, 36, 46, 56, 64, 66, 70, 76, 78, 86, 88, 92,
94, 96];
for i from 1 to 16 do
ppartabl(L[i]);
end do:
CROSSREFS
KEYWORD
nonn
AUTHOR
Christopher Hunt Gribble, Jul 03 2014
STATUS
approved