| You can make a graph where the vertices are integers and edges
connect those pairs of integers which sum to a prime. Then
look for subgraphs isomorphic to Kn,m. :-)
This extends your example (ignoring all but the sum to prime
criterion):
A = { 4, 8, 10, 14, 20, 34, 38, 64 }
B = { 3, 9, 33, 93 }
But I put that together interactively by intersecting lists
of the form { (- p n) | p in list of primes } for various n.
Dan
|
| First, if you drop the restriction that the numbers must be positive,
then w.l.g. 0 can be in one set. Then the other set contains only
primes. You can (presumabkly) also restrict one set to only even
numbers, and the other to only odd numbers.
This greatly reduces the search space.
Examples:
{ 0 2 20 230 266 566 926 1010 }+{ 3 11 41 107 191 311 521 857 }
{ 0 2 56 86 170 230 650 926 }+{ 3 11 41 107 137 227 521 821 }
{ 0 2 14 44 440 614 860 980 }+{ 3 17 59 137 269 419 599 809 }
{ 0 2 26 86 110 290 416 446 }+{ 3 17 41 197 311 461 521 881 }
{ 0 2 26 110 266 290 416 446 }+{ 3 17 41 197 311 461 521 617 }
{ 0 2 38 308 350 518 980 1010 }+{ 3 29 59 191 269 311 419 569 }
{ 0 2 68 110 278 308 590 740 968 }+{ 3 29 71 269 431 659 809 1019 }
{ 0 2 68 110 278 428 590 740 968 }+{ 3 29 71 431 641 659 809 1019 }
|
| Thanks for the collection. In fact, having thought about it some more,
negative numbers would be acceptable, as would 0 (but not 0 as a SUM).
�1 would also be an acceptable sum, even though they're not prime,
as has been discussed at great length elsewhere.
Gilbert (Peter?), is the above list "minimal" in the sense that
(max(A)+max(B))/max(|A|,|B|) is smallest? So if I wanted sets with
eight or so members I'll end up with some sums > 1000?
Unrelated random question: how does the ratio
<largest possible sum>/<total number of elements>
behave as the sets grow indefinitely?
John
|