# Maximum number of prime sums

Zach thinks of six different positive integers, and for each pair of numbers, he adds them. This gives him $\binom{6}{2}=15$ sums. Among these sums, find the maximum number that can be prime numbers. I deducted that there has to be atleast one even number among the $6$ numbers. But will there be one even number, or two evens. Then what will the other numbers be.

• By "one $2$" presumably you mean at least one even number? – Travis Mar 9 '15 at 4:16
• Oh yes, sorry. I just wrote what was in my mind. – user167045 Mar 9 '15 at 4:17
• To be clear, 0 would be allowed as well? It that case I believe that you would at least be able to get 10 prime numbers by using 3 odd and 3 even integers, two of which would have to be 0 and 2, and the odd numbers would have to be primes. – Kwin van der Veen Mar 9 '15 at 4:30
• @fibonatic "positive" in English descriptions excludes zero. I know that other languages have variations on that though. – Joffan Mar 9 '15 at 4:41

## 1 Answer

The sum of two different positive integers is always at least $3$, and so in order for it to be prime, it has to be odd. So one summand has to be even, the other odd. If there are $a$ even numbers and $b = 6-a$ odd numbers, then the potential number of primes is at most $ab \leq 9$, attained when $a=b=3$. Can this bound be attained? Here is an example: $$2,3,4,8,9,15.$$ All of the following are primes: $$2+3 = 5 \\ 3+4 = 7 \\ 2+9 = 3 + 8 = 11 \\ 4+9 = 13 \\ 2+15 = 8+9 = 17 \\ 4+15 = 19 \\ 8+15 = 23$$ If you don't like the repeated sums, you can try instead: $$2,3,4,8,39,99.$$ All of the following are prime: $$2+3 = 5 \\ 3+4 = 7 \\ 3+8 = 11 \\ 2+39 = 41 \\ 4+39 = 43 \\ 8+39 = 47 \\ 2+99 = 101 \\ 4+99 = 103 \\ 8+99 = 107$$

• You can use {2,6,12,5,17,41} to maximize the number of primes in the original set :-) – Joffan Mar 9 '15 at 4:55
• @Joffan: neat, did you determine that by trial and error? or else how? – smci Mar 9 '15 at 10:17
• @Joffan: 2,5,6,12,17 (without 41) pops up in a couple of different OEIS sequences – smci Mar 9 '15 at 10:20
• @smci - a pre-existing list of primes, good spreadsheet design and a little trial and error. I rejected some alternatives that had duplicate sums. It's no surprise to me that those numbers pop up in some sequences - the law of small numbers. – Joffan Mar 9 '15 at 14:32
• @Joffan: you have discovered a new interesting sequence worthy of submitting to OEIS, please do!!! Now can you generalize to N=8, 10... integers with C(N,2) distinct prime sums? Is it always possible for even N? – smci Mar 10 '15 at 1:35