A244640 - OEIS

%I #42 Dec 23 2024 14:53:43

%S 2,4,4,16,16,16,8,192,240,128,512,36,24,224,96,896

%N a(n) is the number of 2-partitions of the set of primes less than A059756(n) that demonstrate that A059756(n) is prime-partitionable.

%C The sequence comprises the number of all possible partitions {P1,P2} for which each n is prime-partitionable.

%H Christopher Hunt Gribble, <a href="/A244640/a244640.txt">List of 2-partitions</a>

%H W. Holsztynski, R. F. E. Strube, <a href="http://dx.doi.org/10.1016/0012-365X(78)90059-6">Paths and circuits in finite groups</a>, Discr. Math. 22 (1978) 263-272.

%H R. J. Mathar and M. F. Hasler, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2014-June/013267.html">Is 52 prime-partitionable?</a>, Seqfan thread (Jun 29 2014)

%H W. T. Trotter, Jr. and Paul Erdős, <a href="https://www.renyi.hu/~p_erdos/1978-49.pdf">When the Cartesian product of directed cycles is Hamiltonian</a>, J. Graph Theory 2 (1978) 137-142 DOI:10.1002/jgt.3190020206.

%e Consider the first prime-partitionable number, A059756(1) = 16.

%e We have P = {2, 3, 5, 7, 11, 13}.

%e a(1) = 2 because the 2-partitions of P for which 16 is prime-partitionable are:

%e     P1a = {2, 5, 11},       P2a = {3, 7, 13}

%e     P1b = {2, 3, 7, 13},    P2b = {5, 11}

%e as is shown below:

%e        n1   n2   p1a   p2a      p1b   p2b

%e         1 + 15     -     3        -     5

%e         2 + 14     2     7        2     -

%e         3 + 13     -    13        3     -

%e         4 + 12     2     3        2     -

%e         5 + 11     5     -        -    11

%e         6 + 10     2     -        2     5

%e         7 +  9     -     3        7     -

%e         8 +  8     2     -        2     -

%e         9 +  7     -     7        3     -

%e        10 +  6     2     3        2     -

%e        11 +  5    11     -        -     5

%e        12 +  4     2     -        2     -

%e        13 +  3     -     3       13     -

%e        14 +  2     2     -        2     -

%e        15 +  1     5     -        3     -

%p Derived from the program provided by _Richard J. Mathar_ in the second link.

%p ppartabl := proc (n)

%p   local i, j, pless, p1, p2, n1, n2, pset1, pset2, alln1n2done, foundp1p2;

%p   # construct set of primes < n in pless.

%p   pless := {};

%p   for i from 2 to n-1 do

%p     if isprime(i) then

%p       pless := `union`(pless, {i});

%p     end if;

%p   end do;

%p   # loop over all nontrivial (nonempty) subsets of the primes, P1.

%p   j := 0;

%p   for pset1 in combinat[choose](pless) do

%p     if 1 <= nops(pset1) then

%p       if pset1 = pset2 then

%p         break;

%p       end if;

%p       # P2 is P \ P1.

%p       pset2 := `minus`(pless, pset1);

%p       # flag to indicate that for each n1,n2 we found a pair.

%p       alln1n2done := true;

%p       for n1 to n-1 do

%p         n2 := n-n1;

%p         # flag that we found a (p1,p2).

%p         foundp1p2 := false;

%p         for p1 in pset1 do

%p           if igcd(n1, p1) <> 1 then

%p             foundp1p2 := true;

%p             break;

%p           end if;

%p           for p2 in pset2 do

%p             if igcd(n2, p2) <> 1 then

%p               foundp1p2 := true;

%p               break;

%p             end if;

%p           end do:

%p           if foundp1p2 = true then

%p             break;

%p           end if;

%p         end do:

%p         if foundp1p2 = false then

%p           alln1n2done := false;

%p           break;

%p         end if;

%p       end do:

%p       if alln1n2done = true then

%p         j := j+1;

%p         if j = 1 then

%p           printf("%d\n", n);

%p         end if;

%p         print(j, pset1, pset2);

%p       end if;

%p     end if;

%p   end do:

%p end proc:

%p L := [16, 22, 34, 36, 46, 56, 64, 66, 70, 76, 78, 86, 88, 92,

%p       94, 96];

%p for i from 1 to 16 do

%p   ppartabl(L[i]);

%p end do:

%Y Cf. A059756.

%K nonn

%O 1,1

%A _Christopher Hunt Gribble_, Jul 03 2014