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$
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]
| improve this answer | |
$\endgroup$
  • 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$ – Daniel Mathias Oct 26 '19 at 21:23
  • $\begingroup$ Beautifully compact code! Thank you for sharing. $\endgroup$ – Dmitry Kamenetsky Oct 27 '19 at 0:41
  • $\begingroup$ @DanielMathias would you mind sharing your code/approach, especially for larger values. $\endgroup$ – Dmitry Kamenetsky Oct 27 '19 at 0:42
  • 1
    $\begingroup$ @Dmitry Tomorrow. (I need to work out a bug causing an error in the output) $\endgroup$ – Daniel Mathias Oct 27 '19 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 '19 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]

| improve this answer | |
$\endgroup$
  • $\begingroup$ Great work Daniel! Are these optimal solutions for the least maximum? $\endgroup$ – Dmitry Kamenetsky Oct 28 '19 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$ – Daniel Mathias Oct 28 '19 at 20:39
  • $\begingroup$ Thank you Daniel. Are you able to find any solutions for 10 elements? $\endgroup$ – Dmitry Kamenetsky Oct 28 '19 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$ – Daniel Mathias Oct 29 '19 at 23:17
  • 2
    $\begingroup$ I've added a sequence to OEIS about this problem: oeis.org/A328815 $\endgroup$ – Dmitry Kamenetsky Nov 7 '19 at 0:09

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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