Two equal-sized lists that produce prime sums

Question

Place one or more distinct numbers between 1 and 100 into the lists $𝑃$ and $𝑄$, such that they contain the same number of elements and any number from $𝑃$ added to any number from $𝑄$ gives a prime. What is the largest number of elements that can be in $P$ and $Q$? You may need to use a computer to solve this.

Here is a similar puzzle: Dividing the first 20 numbers into 3 lists

Good luck!

Answer 1

Computer search solution.

It's easy to see that P and Q can't both contain an even number (since two positive even numbers never add up to a prime) or an odd number (since two distinct positive odd numbers don't either). We can therefore assume that P consists of just odd numbers and Q of just even numbers.

A quick and dirty Python script then identifies...

276 length 6 solutions but no length 7 ones. The first solution it gives is P=[1, 5, 11, 35, 71, 95] and Q=[2, 12, 18, 36, 78, 96]; the last is P=[15, 33, 39, 75, 93, 99] and Q=[4, 8, 14, 64, 74, 98].

Here is the script:

from sympy import isprime

solutions = []

def find_odd(odds, evens):
    if len(odds) >= 6: solutions.append((odds, evens))
    for o in range(odds[-1]+2 if odds else 1, 101, 2):
        if not odds: print(f"\n{o: 2d} ", end="")
        if all(isprime(o + e) for e in evens):
            find_even(odds + [o], evens)

def find_even(odds, evens):
    for e in range(evens[-1]+2 if evens else 2, 101, 2):
        if not evens: print(".", end="")
        if all(isprime(o + e) for o in odds):
            find_odd(odds, evens + [e])

find_odd([], [])

---

Update. After a bit of thought, I realised there's a somewhat faster algorithm: you can precompute the compatible odd numbers for every even numbers and just loop through combinations of even numbers.

from sympy import isprime

def solve(N=100):

    best = 0
    odds = set(range(1,N+1,2))
    compatible = { e : { o for o in odds if isprime(e+o) } for e in range(2,N+1,2) }

    def find(evens, odds):
        nonlocal best
        if len(evens) > best:
            best = len(evens)
            print(evens, list(odds)[:best])
        for e in range(evens[-1]+2 if evens else 2, N+1, 2):
            compat_odds = odds & compatible[e]
            if len(compat_odds) > len(evens):
                find(evens+[e], compat_odds)

    find([], odds)

Which gives:

>> solve(100)
[2] [1]
[2, 4] [1, 3]
[2, 4, 8] [99, 3, 39]
[2, 4, 8, 14] [3, 99, 39, 9]
[2, 4, 8, 14, 28] [99, 3, 39, 9, 15]
[2, 4, 14, 28, 58, 98] [3, 99, 69, 39, 9, 15]
>> solve(420)
[2] [1]
[2, 4] [1, 3]
[2, 4, 8] [225, 3, 99]
[2, 4, 8, 10] [99, 9, 3, 189]
[2, 4, 8, 14, 28] [3, 99, 39, 9, 15]
[2, 4, 8, 14, 28, 64] [99, 3, 39, 9, 15, 345]
[2, 4, 8, 22, 44, 74, 88] [39, 9, 105, 15, 309, 345, 189]
[2, 4, 8, 44, 88, 158, 232, 452] [225, 39, 105, 9, 459, 309, 345, 189]
[12, 48, 90, 138, 168, 180, 300, 342, 420] [419, 101, 11, 179, 341, 89, 59, 221, 319]

Answer 2

Code link

The algorithm is basically generating the table as seen in answers to the previous question, with each row stored as an extended bit field. The rows are the taken in groups, bitwise ANDed together to get their intersection, with a population count on the result to find the size of the intersection. If the size of the intersection is equal to or greater than the number of rows in the group, we have a solution.

Least-maximum solutions found:

3: [1,3,9] [2,4,10]
4: [1,7,13,31] [6,10,16,30]
5: [3,9,15,29,45] [2,8,14,38,44]
6: [1,7,25,55,67,85] [4,12,16,46,72,82]
7: [1,7,25,31,67,91,151] [6,12,16,22,72,82,106]
8: [1,3,31,43,45,121,135,253] [16,28,58,106,136,148,196,238]
9: [11,47,89,137,167,179,299,341,419] [12,60,90,102,180,222,320,342,420]