5
$\begingroup$

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!

$\endgroup$

2 Answers 2

8
$\begingroup$

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]
$\endgroup$
5
  • 2
    $\begingroup$ Very nice. Is this code efficient enough to find the lowest length 7 solutions (needing values up to 151) and length 8 solutions (needing values up to 253)? $\endgroup$ Oct 26, 2019 at 21:23
  • $\begingroup$ Beautifully compact code! Thank you for sharing. $\endgroup$ Oct 27, 2019 at 0:41
  • $\begingroup$ @DanielMathias would you mind sharing your code/approach, especially for larger values. $\endgroup$ Oct 27, 2019 at 0:42
  • 1
    $\begingroup$ @Dmitry Tomorrow. (I need to work out a bug causing an error in the output) $\endgroup$ Oct 27, 2019 at 1:01
  • $\begingroup$ @DanielMathias It can find the length 7 solutions (albeit slowly) but would take a very long time to find the length 8 ones. If I get a chance, I'll have a think about how to make it more efficient (beyond rewriting it in a faster language). $\endgroup$
    – Uri Granta
    Oct 27, 2019 at 7:10
3
$\begingroup$

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]

$\endgroup$
10
  • $\begingroup$ Great work Daniel! Are these optimal solutions for the least maximum? $\endgroup$ Oct 28, 2019 at 4:27
  • $\begingroup$ @Dmitry There are no solutions of equal size that have a greatest element less than the greatest element in each of the posted solutions. $\endgroup$ Oct 28, 2019 at 20:39
  • $\begingroup$ Thank you Daniel. Are you able to find any solutions for 10 elements? $\endgroup$ Oct 28, 2019 at 20:55
  • $\begingroup$ @Dmitry [1 3d 73 97 10f 127 145 169 295 307][c 16 a2 c4 15c 1c0 1ce 1f6 292 300] is probably least-max. It appears that an 11-element solution requires numbers greater than 1024. $\endgroup$ Oct 29, 2019 at 23:17
  • 2
    $\begingroup$ I've added a sequence to OEIS about this problem: oeis.org/A328815 $\endgroup$ Nov 7, 2019 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.