15
$\begingroup$

Place every number from 1 to 20 into one of three lists $P$, $Q$ or $O$, such that any number from $P$ added to any number from $Q$ gives a prime. What is the fewest number of elements that can be in $O$? Note that $P$ and $Q$ cannot be empty.

Good luck!

$\endgroup$
15
$\begingroup$

It is possible to solve this without a computer search. The proof of $\min|O|$ is below.

These are all the odd prime numbers $\le20+19=39$; colours important later. $$\color{red}3,\color{blue}5,\color{green}7,\color{orange}{11},\color{purple}{13},\color{cyan}{17},\color{brown}{19},\color{silver}{23},\color{lightgreen}{29},31,\color{gold}{37}.$$ Let $P$ contain even integers only and $Q$ odd without loss of generality. We can then form the following table, where $\checkmark$ indicates whether the entry is prime and the colours correspond to the prime numbers above. The superscripts next to each number show how many times the total is prime. \begin{array}{c|c}+&2^{[7]}&4^{[7]}&6^{[6]}&8^{[5]}&10^{[6]}&12^{[6]}&14^{[5]}&16^{[5]}&18^{[5]}&20^{[4]}\\\hline1^{[7]}&\color{red}\checkmark&\color{blue}\checkmark&\color{green}\checkmark&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&\\\hline3^{[7]}&\color{blue}\checkmark&\color{green}\checkmark&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark\\\hline5^{[6]}&\color{green}\checkmark&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&\\\hline7^{[5]}&&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&\\\hline9^{[6]}&\color{orange}\checkmark&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark\\\hline11^{[6]}&\color{purple}\checkmark&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark\\\hline13^{[5]}&&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&\\\hline15^{[5]}&\color{cyan}\checkmark&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&&\\\hline17^{[5]}&\color{brown}\checkmark&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&&&\color{gold}\checkmark\\\hline19^{[4]}&&\color{silver}\checkmark&&&\color{lightgreen}\checkmark&\checkmark&&&\color{gold}\checkmark&\end{array} Clearly, $|S|=1\implies\max|S^*|=7\implies\min|O|=12$ where $S\in\{P,Q\}$ and $S\cup S^*=P\cup Q$. In particular, this yields the solutions $$[P,Q]=\begin{cases}[\{2\},\{1,3,5,9,11,15,17\}]\\ [\{4\},\{1,3,7,9,13,15,19\}]\\ [\{2,4,6,10,12,16,18\},\{1\}]\\ [\{2,4,8,10,14,16,20\},\{3\}]\end{cases}$$ due to the symmetry of $\checkmark$ in the table. Now, suppose $|S|=2$. It can be seen that $|O|$ is minimised and is equal to $12$ again when $|S^*|=6$, with $S=\{4,10\},\{3,9\}$ as they are the instances where $\checkmark$ appears in both columns/rows the most times. In particular, this yields the solutions $$[P,Q]=\begin{cases}[\{4,10\},\{1,3,7,9,13,19\}]\\ [\{3,9\},\{2,4,8,10,14,20\}]\end{cases}.$$ This means that any further solutions with $|S|>2$ must contain either $\{4,10\}$ or $\{3,9\}$. Again, due to symmetry, only the former case will be considered. Of the rows $1,3,7,9,13,19$, the highest number of checkmarks that appear in columns other than $4,10$ is $16$, with $4$ checkmarks at $1,3,7,13$. Therefore, if $|S|=3$, $\max|S^*|=4$ so $\min|O|=13>12$. As no other column contains checkmarks at all of $1,3,7,13$, it can be concluded that $\min|O|>12\,\forall |S|>2$. The result that $\min|O|=12$ follows. $\square$

$\endgroup$
  • 2
    $\begingroup$ what a beautiful proof! +1 $\endgroup$ – Omega Krypton Oct 26 at 16:32
8
$\begingroup$

Incorrect answer

Oops! The "solution" below is wrong in the following way:

I thought I had a "trivial" solution that gets 9 numbers into $P\cup Q$, but it only appeared to do that because I was an idiot and put one number into both sets without noticing. That solution therefore only actually achieves $|P\cup Q|=8$. I have other "less trivial" solutions that achieve the same, and I have a proof (in the "solution" below) that we can't get $|P\cup Q|=10$. But the possibility of getting 9 is not resolved by what follows.

Unfortunately it's 3:25am local time and I don't have time to attempt a proper fix. My apologies; hopefully someone else will do a less-hilariously-broken job. My incorrect solution follows, because I don't believe in hiding my screwups :-).

First of all,

suppose $P$ contains both an even number $p_0$ and an odd number $p_1$. Then $Q$ can't contain more than one number. (If $q,q'$ are of the same parity then one of the $p$ combines with them to make two different even numbers, which can't both be prime. If $q_0$ is even and $q_1$ odd, then $p_0+q_0,p_1+q_1$ are two different even numbers, which again can't both be prime.) So there can't be more elements of $P$ than primes in some interval of size 20: e.g., $Q=\{1\}$ and $P=\{2,4,6,10,12,16,18\}$. That leaves 12 elements in $O$, and we can't do better under these assumptions.

Obviously the same holds if

$Q$ contains both an even and an odd number.

So the only other possibility is that

one of $P,Q$ is all-even and the other is all-odd. Let's draw up a table showing which even numbers are compatible with which odd numbers:

    1  3  5  7  9 11 13 15 17 19
 2  x  x  x  .  x  x  .  x  x  .
 4  x  x  .  x  x  .  x  x  .  x
 6  x  .  x  x  .  x  x  .  x  .
 8  .  x  x  .  x  x  .  x  .  .
10  x  x  .  x  x  .  x  .  .  x
12  x  .  x  x  .  x  .  .  x  x
14  .  x  x  .  x  .  .  x  x  .
16  x  x  .  x  .  .  x  x  .  .
18  x  .  x  .  .  x  x  .  .  x
20  .  x  .  .  x  x  .  .  x  .

where

we must pick a set of rows and a set of columns such that all the intersections have "x" rather than ".". We managed 8 elements in $P\cup Q$ before; if we can get 9 or more than one of the sets must contain at least 5 elements. Notice that we can't have both 1 and 20, or both 3 and 18, or ..., or both 19 and 2 -- so we can't get more than 10 numbers in total into $P\cup Q$. Recall that we managed 9 by taking one of P,Q to be {1}, so if we can do better then we must take at least one number from each of these pairs.

Now

suppose, specifically, that we take 20. Then the only odds we can have are 3,9,11,17. If we have all of those then the only evens that work are 2,20 for a total of 6 things in $P\cup Q$, no good. It's fairly easy to see (just by slicing out the relevant columns of the table above) that if we pick three of those four odd numbers we can't get more than three evens possible, for a total of 6 again, and that if we pick two then the best we can do is {3,9} with {2,4,8,10,14,20}, a total of 8: still no better than with one of our sets being a singleton. So there are no better-than-singleton solutions that use 20.

Recall that

to do better than the singleton solution we have to use one number from each of our pairs. In particular, if we don't use 20 then we must use 1. That means we don't use 8,14 and hence must use their partners 13,7. Using 13 rules out both 2 and 12, which means we must use their partners 19,9. Having 19 rules out 6,16 and therefore requires their partners 15,5; having 9 also rules out 12,18 and therefore requires their partners 9 (duh) and 3. But now the only evens remaining are 4,10 and both are incompatible with 5 which we need to have.

So

there is no solution that uses one from each of our pairs {1,20}, {2,19}, etc., and hence no solution that puts 10 or more numbers in $P\cup Q$

and therefore

we can't do better than the "singleton" solution that uses 9

and therefore the smallest possible number of elements in $O$ is

11.

(I bet it's possible to streamline the reasoning above somewhat.)

$\endgroup$
  • $\begingroup$ You seem to have placed $1$ in both P and Q. I think each number can only be in one list. $\endgroup$ – Jens Oct 26 at 2:04
  • $\begingroup$ Ooooops! Quite right. I think I had a solution as good as that broken one that worked in a different way, so that should be patchable. Let me fix it. (Or retract, if I'm misremembering.) $\endgroup$ – Gareth McCaughan Oct 26 at 2:22
  • $\begingroup$ As far as I can tell putting 1 in both lists doesn't impact the validity of the solution. 1 is already accounted for, and the numbers in $O$ wouldn't have included 1 regardless of if it is in one or both lists. $\endgroup$ – Matthew0898 Oct 26 at 2:24
  • 1
    $\begingroup$ Nope, no quick fix. Matthew, the issue isn't that the solution is invalid but that my proof that it's optimal is broken because there's now a gap between the best solution I found and what I've proved can't be done. $\endgroup$ – Gareth McCaughan Oct 26 at 2:27
  • $\begingroup$ aah... I hadn't considered that. $\endgroup$ – Matthew0898 Oct 26 at 2:31
5
$\begingroup$

As it is currently worded:

There is no requirement that $P$ contain any number at all so long as all the other numbers are added to $Q$ or $O$.

Therefore

The minimum number of elements in $O$ is 0.

which can be obtained by

Addding all the numbers to $Q$. $P$ and $O$ are empty sets. There exists no value in $P$ that added to any value from $Q$ fails the condition of being prime, simply because there is no value in $P$ to add to a value in $Q$.

This feels like a non-answer, but it seems valid as far as I can tell.

$\endgroup$
  • 2
    $\begingroup$ Ha! Cunning and clearly correct, but equally clearly not what OP intended :-). $\endgroup$ – Gareth McCaughan Oct 26 at 2:21
  • $\begingroup$ Very cunning. I fixed the problem statement to prevent such solutions. $\endgroup$ – Dmitry Kamenetsky Oct 26 at 5:54
3
$\begingroup$

Computer search solution

A simple search of all combinations of even numbers in P and odd numbers in Q confirms that 8 is the most you can use, so 12 unused in set O is the best you can do. Symmetry between odds and evens means you can generate an odd/even solution from any even/odd solution by incrementing odds and decrementing evens. It's nice to note that there is a pair of arrangements with two elements in the 'short' list.

Solutions.

P1 Q7 sum 8 P (2) Q (1,3,5,9,11,15,17)
P1 Q7 sum 8 P (4) Q (1,3,7,9,13,15,19)
P2 Q6 sum 8 P (4,10) Q (1,3,7,9,13,19)
P7 Q1 sum 8 P (2,4,6,10,12,16,18) Q (1)
P6 Q2 sum 8 P (2,4,8,10,14,20) Q (3,9)
P7 Q1 sum 8 P (2,4,8,10,14,16,20) Q (3)

Code. Not a shining light for correct coding but it runs quickly until you hand it 32 instead of 20. Not much interesting happens with higher numbers. Algorithm is basically loop from 1 to 2^N where N is number of evens, then loop over 2^N again for odds, and for each, check which even and odd numbers are 'present' in the list by checking whether the loop number has that bit set.

// PrimePartition
// partition the numbers 1 to N into two lists such that all sums of one element from each list are prime
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MaxLen 20

int primes[27]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103};
int odds[MaxLen+1];
int evens[MaxLen+1];


void Solve(int MaxList)
{
    long i,j,ei,oi,k,pcount,qcount,thiseven,thisodd,thissum,failed,bestsofar=3;

    // Loop over first group (evens)
    for (i=1; i<(1 << MaxList); i++)
    {
        // Loop over second group (odds)
        for (j=1; j<(1 << MaxList); j++)
        {
            failed = 0;
            pcount = 0;
            // check to see whether this group pair satisfies the condition
            for (ei=0; ei<MaxList; ei++)
            {
                if ((1 << ei) & i)
                {
                    pcount++;
                    thiseven = evens[ei];
                    qcount = 0;
                    for (oi=0; oi<MaxList; oi++)
                    {
                        if ((1 << oi) & j)
                        {
                            qcount++;
                            thisodd = odds[oi];
                            thissum = thiseven + thisodd;
                            // search for ei'th even number plus the oi'th odd number in the prime list
                            for (k=0; primes[k]<thissum && k<26; k++);
                            if (primes[k]>thissum || k >= 26)
                            {
                                failed=1;
                                goto failedprimesearch;
                            }
                        }
                    }
                }
            }
            // ignore solutions not as good as best so far
            if (pcount+qcount >= bestsofar)
            {
                bestsofar = pcount+qcount;
                printf("P%ld Q%ld sum %ld\n", pcount,qcount,pcount+qcount);
                pcount = 0;
                // print out the solution
                printf("Set P (");
                for (ei=0; ei<MaxList; ei++)
                {
                    if ((1 << ei) & i)
                    {
                        if (pcount)
                            printf(",");
                        pcount++;
                        printf("%ld", evens[ei]);
                    }
                }
                printf(")\n");
                qcount = 0;
                printf("Set Q (");
                for (oi=0; oi<MaxList; oi++)
                {
                    if ((1 << oi) & j)
                    {
                        if (qcount)
                            printf(",");
                        qcount++;
                        printf("%ld", odds[oi]);
                    }
                }
                printf(")\n\n");
            }
failedprimesearch:;
        }
    }
}



void main(int argc, char **argv)
{
    int i,high;

    if (argc > 1)
    {
        high = atoi(argv[1]);
        if (high < 5 || high > MaxLen*2)
            goto usage;
    }
    else
    {
usage:
        printf("Usage: PrimePartition N\n");
        printf(" where N is highest number (max %d)\n", 2*MaxLen);
        exit(2);
    }

    for (i=0;i<MaxLen;i++)
    {
        evens[i] = i*2 + 2;
        odds[i] = i*2 + 1;
    }
    Solve(high/2);
}
$\endgroup$
  • $\begingroup$ For line breaks within spoiler, end each line with two spaces and begin each new line with the spoiler tag >! $\endgroup$ – Daniel Mathias Oct 26 at 9:42
  • $\begingroup$ For some reason I can no longer edit it. Can someone else do it? $\endgroup$ – Dmitry Kamenetsky Oct 26 at 10:41
  • $\begingroup$ Thanks it's the "end each line with two spaces" part I didn't know about $\endgroup$ – theonetruepath Oct 26 at 10:57
  • $\begingroup$ Great answer and thank you for the code. Perhaps the method can be simplified if you only loop through the numbers you want to leave out (ie., list O) and derive the other two lists from the remaining numbers. $\endgroup$ – Dmitry Kamenetsky Oct 26 at 13:26
  • 1
    $\begingroup$ Running it on 36 instead of 20 takes 25 minutes: P1 Q11 sum 12 Set P (2) Set Q (1,3,5,9,11,15,17,21,27,29,35) P11 Q1 sum 12 Set P (2,4,6,10,12,16,18,22,28,30,36) Set Q (1) command took 0:25:37.02 (1537.02s total) $\endgroup$ – theonetruepath Oct 26 at 15:10
1
$\begingroup$

List O

4,6,7,8,10,12,13,14,16,18,19,20

List P

2

List Q

1,3,5,9,11,15,17

$\endgroup$
  • 1
    $\begingroup$ You seem to be limiting yourself to primes in the Q list. What if you have 9 in there as well? $\endgroup$ – theonetruepath Oct 26 at 10:55
  • 1
    $\begingroup$ You're right, I was too focused on twin primes... $\endgroup$ – Torben Möller Oct 26 at 11:30

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.