[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1879.0. "ISO sets that pairwise sum to primes" by VMSDEV::HALLYB (Fish have no concept of fire) Tue Jun 14 1994 20:36

    I've looked through this conference and not yet found anything on this.
    
    Please find me two sets A = {A_i} and B = {B_j} of positive integers
    satisfying the condition that A_i + B_j is prime for all i,j.
    
    A simple example is A = { 4, 8, 20} and B = { 3, 9, 33}
    
    I'd like the largest element of either set to be "not too big",
    say < 1000, and the sets should have roughly the same number of elements,
    say the larger set should be no more than 20% larger than the smaller.
    
    Aside from exhaustive search, is there any easy way to generate these sets?
    
      John
T.RTitleUserPersonal
Name
DateLines
1879.1CSC32::D_DERAMODan D'Eramo, Customer Support CenterWed Jun 15 1994 00:3615
        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
        
1879.2AFSRTL::GILBERTWed Jun 15 1994 20:3116
    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 }
1879.3Anybody have any references for this type of problem?VMSDEV::HALLYBFish have no concept of fireThu Jun 16 1994 12:2616