2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ By "one $2$" presumably you mean at least one even number? $\endgroup$ – Travis Mar 9 '15 at 4:16
  • $\begingroup$ Oh yes, sorry. I just wrote what was in my mind. $\endgroup$ – user167045 Mar 9 '15 at 4:17
  • $\begingroup$ 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. $\endgroup$ – Kwin van der Veen Mar 9 '15 at 4:30
  • 1
    $\begingroup$ @fibonatic "positive" in English descriptions excludes zero. I know that other languages have variations on that though. $\endgroup$ – Joffan Mar 9 '15 at 4:41
8
$\begingroup$

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 $$

$\endgroup$
  • 2
    $\begingroup$ You can use {2,6,12,5,17,41} to maximize the number of primes in the original set :-) $\endgroup$ – Joffan Mar 9 '15 at 4:55
  • $\begingroup$ @Joffan: neat, did you determine that by trial and error? or else how? $\endgroup$ – smci Mar 9 '15 at 10:17
  • $\begingroup$ @Joffan: 2,5,6,12,17 (without 41) pops up in a couple of different OEIS sequences $\endgroup$ – smci Mar 9 '15 at 10:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Joffan Mar 9 '15 at 14:32
  • $\begingroup$ @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? $\endgroup$ – smci Mar 10 '15 at 1:35

Your Answer

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