Primes Again

Logic Level 3

Given six distinct positive integers $a, b, c, d, e,$ and $f,$ what is the maximum number of distinct primes that can be formed from the pairwise sums?

5 6 7 8 9 10 11 None of the above

2 solutions

Ralph Macarasig
Jun 13, 2016

Let $S = \{ a, b, c, d, e, f \}$ . Consider the number of odd numbers and the number of even numbers in $S$ .

If there is $0$ or there are $6$ odd numbers in $S$ , obviously, there is no way of forming a prime number from the pairwise sums as it will always lead to an even integer greater than $2$ .

If there is $1$ or there are $5$ odd numbers in $S$ , there exists an $S$ such that the maximum number of primes that can be formed from the pairwise sums is $\boxed{5}$ .

If there are $2$ or there are $4$ odd numbers in $S$ , there exists an $S$ such that the maximum number of primes that can be formed from the pairwise sums is $\boxed{8}$ .

Finally, if there are $3$ odd numbers in $S$ , there exists an $S$ such that the maximum number of primes that can be formed from the pairwise sums is $\boxed{9}$ .

To show that such a set $S$ exists, consider $S = \{ 2, 4, 9, 15, 27, 32\}$ .

$2 + 9 = 11$

$2 + 15 = 17$

$2 + 27 = 29$

$4 + 9 = 13$

$4 + 15 = 19$

$4 + 27 =31$

$32 + 9 = 41$

$32 + 15 = 47$

$32 + 27 = 59$

So, there are $9$ primes formed from the pairwise sums in the given $S$ . I didn't include the other sums as it would only result to an even number. Hence, the maximum is $\boxed9$ .

I solved it with the same reasoning as you did, except that I didn't find an example set. How could you find it?

Konstantin Zeis - 5 years ago

I did a little guess and check on that one. I used $2$ and $4$ then looked for 3 odd numbers that when I add it to them, it will form prime numbers. Then, for the third even number, the conjecture I got was that it must be congruent to $2$ mod $10$ or $4$ mod $10$

Ralph Macarasig - 4 years, 12 months ago

Lakas ni Ralph

Norwyn Kah - 5 years ago

Hindi pooo...

Ralph Macarasig - 5 years ago

That's not Hindi

Grant Bulaong - 5 years ago

I do not understand this even a little bit

Guido Perdomo - 4 years, 1 month ago

Which part do you not understand? Do you understand the first line? What about the second line?

If you specify the part that you started getting lost, and what was confusing about that, then someone could help guide you.

Calvin Lin Staff - 4 years, 1 month ago

Is there a proof that says "x number of odd numbers provides y number of distinct primes when added"?

Todd Dean - 3 years, 8 months ago

@Todd Dean – Hm, not that I'm aware of. Extending this argument, an upper bound on $y$ would be $\lfloor \frac{x}{2} \rfloor \times \lceil \frac{x}{2} \rceil$ . However, it's not immediately obvious to me that this can necessarily be achieved.

If the answer is yes, then I suspect that there is some deeper Number Theory fact that is happening.

Calvin Lin Staff - 3 years, 8 months ago

A sequence of six distinct integers would not necessarily contain ANY even numbers.

Did you mean a contiguous range of integers?

Bob Stine - 3 years, 8 months ago

You are right to say that "A sequence of six distinct integers would not necessarily contain ANY even numbers.". If so, this is covered under the case of "If there is 0 or 6 odd numbers in S, then the sum is an even integer greater than 2 hence not prime".

Calvin Lin Staff - 3 years, 8 months ago

Has the wording of the question or any of the answers changed since bob's remark? I can't see any references to sequences.

Katherine barker - 3 years, 5 months ago

@Katherine Barker – No, nothing has changed.

I'm not too sure what he is referring to. I was trying to point out that the solution considered the cases of 0/1/2/3/4/5/6 odd numbers, and so includes the case that he mentioned.

Calvin Lin Staff - 3 years, 5 months ago

I got there by somewhat less rigorous means than you have shown above - the only way a pair of integers can sum up to a prime is if one is even and the other odd. The maximum number of possible pairings is achieved by having three even and three odd integers - each even integer combining with each odd integer to form a prime, which gives us overall three sets of three primes, for a total of nine primes. I did not get as far as generating a set of numbers for which this actually works because I was confident that such a set would exist and I take short cuts whenever possible.

Thomas Sutcliffe - 3 years, 3 months ago

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)


noprimes = set(j for i in range(2, 8) for j in range(i*2, 100, i))
primes = [x for x in range(2, 100) if x not in noprimes]
distinct_ints = 6

combos = list(combinations(range(1,20), distinct_ints))

max_counter = {0:''}
prime_sum = {}
noprime_sum = {}
counter_p = 0
counter_np = 0
for i in combos:
    t = list(combinations(i, 2))
    for j in t:
        y = sum(j)
        if y in primes:
            counter_p += 1
            prime_sum[counter_p]=j
        if y in noprimes:
            counter_np += 1
            noprime_sum[counter_np]=j
    if counter_p > max(max_counter.keys()):
        max_counter[counter_p] = i,prime_sum.values(),noprime_sum.values()
    counter_p = 0
    counter_np = 0
    prime_sum = {}
    noprime_sum = {}
z = [[k,max_counter[k]] for k in sorted(max_counter)][1:] 
for i in z:
    print 'Number of distinct primes from sum: %d/%d\tDistinct positive ints:%s\tPrime Pairs: %s\tNon-Prime Pairs: %s' \
    % (i[0],len(t),i[1][0], i[1][1], i[1][2])
    print

For 6 distinct integers
Number of distinct primes from sum: 7/15        Distinct positive ints:(1, 2, 3, 4, 5, 6)       Prime Pairs: [(1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (5, 6)]   Non-Prime Pairs: [(1, 3), (1, 5), (2, 4), (2, 6), (3, 5), (3, 6), (4, 5), (4, 6)]

Number of distinct primes from sum: 8/15        Distinct positive ints:(1, 2, 3, 4, 7, 10)      Prime Pairs: [(1, 2), (1, 4), (1, 10), (2, 3), (3, 4), (3, 10), (4, 7), (7, 10)]        Non-Prime Pairs: [(1, 3), (1, 7), (2, 4), (2, 7), (2, 10), (3, 7), (4, 10)]

Number of distinct primes from sum: 9/15        Distinct positive ints:(1, 2, 3, 4, 9, 10)      Prime Pairs: [(1, 2), (1, 4), (1, 10), (2, 3), (2, 9), (3, 4), (3, 10), (4, 9), (9, 10)]        Non-Prime Pairs: [(1, 3), (1, 9), (2, 4), (2, 10), (3, 9), (4, 10)]


For 7 distinct integers
Number of distinct primes from sum: 9/21        Distinct positive ints:(1, 2, 3, 4, 5, 6, 7)    Prime Pairs: [(1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (4, 7), (5, 6), (6, 7)]   Non-Prime Pairs: [(1, 3), (1, 5), (1, 7), (2, 4), (2, 6), (2, 7), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (5, 7)]

Number of distinct primes from sum: 10/21       Distinct positive ints:(1, 2, 3, 4, 5, 8, 9)    Prime Pairs: [(1, 2), (1, 4), (2, 3), (2, 5), (2, 9), (3, 4), (3, 8), (4, 9), (5, 8), (8, 9)]   Non-Prime Pairs: [(1, 3), (1, 5), (1, 8), (1, 9), (2, 4), (2, 8), (3, 5), (3, 9), (4, 5), (4, 8), (5, 9)]

Number of distinct primes from sum: 11/21       Distinct positive ints:(1, 2, 3, 4, 7, 9, 10)   Prime Pairs: [(1, 2), (1, 4), (1, 10), (2, 3), (2, 9), (3, 4), (3, 10), (4, 7), (4, 9), (7, 10), (9, 10)]       Non-Prime Pairs: [(1, 3), (1, 7), (1, 9), (2, 4), (2, 7), (2, 10), (3, 7), (3, 9), (4, 10), (7, 9)]

Number of distinct primes from sum: 12/21       Distinct positive ints:(1, 2, 5, 6, 11, 12, 17) Prime Pairs: [(1, 2), (1, 6), (1, 12), (2, 5), (2, 11), (2, 17), (5, 6), (5, 12), (6, 11), (6, 17), (11, 12), (12, 17)] Non-Prime Pairs: [(1, 5), (1, 11), (1, 17), (2, 6), (2, 12), (5, 11), (5, 17), (6, 12), (11, 17)]


For 8 distinct integers
Number of distinct primes from sum: 11/28       Distinct positive ints:(1, 2, 3, 4, 5, 6, 7, 8) Prime Pairs: [(1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (3, 4), (3, 8), (4, 7), (5, 6), (5, 8), (6, 7)]   Non-Prime Pairs: [(1, 3), (1, 5), (1, 7), (1, 8), (2, 4), (2, 6), (2, 7), (2, 8), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (4, 8), (5, 7), (6, 8), (7, 8)]

Number of distinct primes from sum: 12/28       Distinct positive ints:(1, 2, 3, 4, 5, 6, 7, 10)        Prime Pairs: [(1, 2), (1, 4), (1, 6), (1, 10), (2, 3), (2, 5), (3, 4), (3, 10), (4, 7), (5, 6), (6, 7), (7, 10)]        Non-Prime Pairs: [(1, 3), (1, 5), (1, 7), (2, 4), (2, 6), (2, 7), (2, 10), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (4, 10), (5, 7), (5, 10), (6, 10)]

Number of distinct primes from sum: 13/28       Distinct positive ints:(1, 2, 3, 4, 5, 8, 9, 10)        Prime Pairs: [(1, 2), (1, 4), (1, 10), (2, 3), (2, 5), (2, 9), (3, 4), (3, 8), (3, 10), (4, 9), (5, 8), (8, 9), (9, 10)]        Non-Prime Pairs: [(1, 3), (1, 5), (1, 8), (1, 9), (2, 4), (2, 8), (2, 10), (3, 5), (3, 9), (4, 5), (4, 8), (4, 10), (5, 9), (5, 10), (8, 10)]

Number of distinct primes from sum: 14/28       Distinct positive ints:(1, 2, 3, 4, 7, 9, 10, 16)       Prime Pairs: [(1, 2), (1, 4), (1, 10), (1, 16), (2, 3), (2, 9), (3, 4), (3, 10), (3, 16), (4, 7), (4, 9), (7, 10), (7, 16), (9, 10)]    Non-Prime Pairs: [(1, 3), (1, 7), (1, 9), (2, 4), (2, 7), (2, 10), (2, 16), (3, 7), (3, 9), (4, 10), (4, 16), (7, 9), (9, 16), (10, 16)]

Number of distinct primes from sum: 15/28       Distinct positive ints:(1, 2, 5, 6, 11, 12, 17, 18)     Prime Pairs: [(1, 2), (1, 6), (1, 12), (1, 18), (2, 5), (2, 11), (2, 17), (5, 6), (5, 12), (5, 18), (6, 11), (6, 17), (11, 12), (11, 18), (12, 17)]     Non-Prime Pairs: [(1, 5), (1, 11), (1, 17), (2, 6), (2, 12), (2, 18), (5, 11), (5, 17), (6, 12), (6, 18), (11, 17), (12, 18), (17, 18)]

Michael Fitzgerald - 3 years, 1 month ago

The solution set I found was {1, 2, 3, 10, 16, 21}, after I reached the same conclusion regarding the maximum number of odd pairs in the same way as you.

My thinking was as follows: I started with the smallest numbers I could (since primes tend to be spaced further apart the higher you get, making solutions harder to find, and it seemed more elegant to find a set of smallish numbers).

{1, 2, 3} worked fine. But then, if you add 4, you get 5 as a duplicated prime.

You could add 5 as the 4th member, but the resulting set of 3 prime you have {3, 5, 7} are consecutive odd numbers. That's a problem, because one of the set will always be a multiple of 3, and 2 is the only even number that doesn't yield a non-prime when added.

Choosing 6, 7 or 8 as the 4th member will result in a 9, which isn't prime.

Choosing 9 as the 4th member will work. The solution is {1, 2, 3, 9, 28, 58}. I found this by looking along the list of primes for further sets of 3 primes, {n, n+2, n+8}.

However I wondered if a solution with smaller numbers existed. Choosing 10 as the 4th member does the trick. Then if you work your way up through the possibilities for the 5th and 6th members, till you find values that work, you'll get the solution above.

Ian MacDonald - 2 years, 10 months ago

I did the same way :) . And that verification set I got was ${1,2,3,4,9,10}$ .

Manish Mayank - 5 years ago

I think you only got $6$ primes which are $3, 5, 7, 11, 13, 19$ but it's nice if you got the correct answer lol

Ralph Macarasig - 5 years ago

Oh.. Yes :P I counted the repeated prime sums.

Manish Mayank - 4 years, 12 months ago

@Manish Mayank – Thanks. I added in the condition that we want distinct primes :)

Calvin Lin Staff - 4 years, 12 months ago

@Calvin Lin – Yeah :D .. It's better now.

Manish Mayank - 4 years, 12 months ago

If we consider the set {1,2,3,4,5,6 } Then we are getting maximum 11 primes from pairwise sums

Deeponjit Bose - 3 years, 10 months ago

Can you state what are the distinct primes ?

Note that you only have there are only 9 numbers from $3=1+2$ to $11=6+5$ inclusive.

Calvin Lin Staff - 3 years, 10 months ago

I can only make 3, 5, 7 and 11, which fits with calvin's comment

Katherine barker - 3 years, 5 months ago

Pavan Konathala
Apr 2, 2018

If the set contains 6 odd numbers or 6 even numbers there is no chance of getting a prime number by adding any two numbers from the set. Therefore set must contain both odd and even to get prime number (odd+odd results in even number which is not a prime similarly with even+even). If we want maximum distinct primes we should have 3 even,3 odd numbers then for every even number we can have 3 combinations(3 odd numbers) Therefore 3*3=9

You still need to show that there is at least one such a set. It's enough to give an example. Without that, you only proved that you can form maximum 9 odd numbers, not primes.

Laszlo Kocsis - 3 years, 1 month ago

Starting with 2N integers, one can always get N^2 distinct odd numbers as pairwise sums. Are there always N^2 distinct prime numbers as well?

Boris Rabinovich - 2 years, 4 months ago

Yes. From Green-Tao theorem, the are N^2 primes forming an arithmetic progression. From there it's easy to construct an example for this problem

Boris Rabinovich - 2 years, 4 months ago

Primes Again

2 solutions

1 pending report

Vote up reports you agree with