wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> No set of 5 with sum of 3 equal to a prime 
        
(Message started by: gkwal on May 3^rd, 2007, 11:31am)

Title: No set of 5 with sum of 3 equal to a prime
Post by gkwal on May 3^rd, 2007, 11:31am

The set {3, 5, 9, 29} has the property that the sum of any three of its elements is a prime number. Prove there is no set of five (5) numbers with this property

Title: Re: No set of 5 with sum of 3 equal to a prime
Post by towr on May 3^rd, 2007, 2:29pm

[hide]I think considering them mod 2 and mod 6 would suffice.
If you have more than three evens those sum to an even number. If you have at least one even and at least two odd ones, those also add to even. So the last case is were all numbers are odd.
Now considering them mod 6, you have 5 numbers for the 3 odd positions. If three are in the same place, then those sum to a multiple of three. So all three different slots will be taken by at least one of the numbers, and taking one from each slot also adds to a multiple of three.[/hide]

Title: Re: No set of 5 with sum of 3 equal to a prime
Post by towr on May 3^rd, 2007, 2:36pm

How many sets of four (positive) numbers are there for which every subset of three sums to a prime? Are there infinitely many?
Primes do thin out a bit at the higher regions of the number line, after all. If there aren't infinitely many, what is the maximum number in the disjunction of all these sets?

Title: Re: No set of 5 with sum of 3 equal to a prime
Post by Eigenray on May 3^rd, 2007, 3:44pm

There are infinitely many such sets. It's not too hard to show this if we don't require the individual elements to be positive. But my proof that they can all be taken positive uses the following lemma (so I don't know if there's an elementary proof):

Lemma: Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif= (3/2)^1/3, and r = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1. Then for sufficiently large x, there is always a prime p between x and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx with p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif r mod 3.

Proof: By a result of Dirichlet,

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif_r(x) = #{primes p < x, p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif r mod 3} ~ 1/2 x/log x as xhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif.

Hence, for any fixed http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif> 0, we have

(1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif) 1/2 x/log x < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif_r(x) < (1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif) 1/2 x/log x

for all sufficiently large x. So if we pick http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif>0 such that

1 > (1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif)/(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif) > 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif,

then for x sufficiently large, we will have

(1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif)/(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif) > 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif [1 + log http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif/log x],

and therefore

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif_r(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx) > (1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif) 1/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx/log (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx)
> (1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif) 1/2 x/log x
> http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif_r(x),

which means there must be a prime p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif r mod 3 between x and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx, as claimed.

Title: Re: No set of 5 with sum of 3 equal to a prime
Post by Eigenray on May 4^th, 2007, 3:48pm

Followup/generalization:

Call a set {x₁,...,x_n} of n distinct integers primey if every (n-1)-subset has a prime sum. In roughly increasing difficulty:

(1a) If n is odd, then there are no positive primey sets, but

(1b) there are infinitely many primey sets.

(2) If n is even, then there are infinitely many positive primey sets.

You may use the following result: Let r, n be relatively prime integers, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif> 1. Then for x sufficiently large, there is always a prime p between x and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx with p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif r mod n.

Title: Re: No set of 5 with sum of 3 equal to a prime
Post by Eigenray on May 20^th, 2007, 9:25pm

on 05/03/07 at 14:36:52, towr wrote:

How many sets of four (positive) numbers are there for which every subset of three sums to a prime? Are there infinitely many?

The equations

x+y+z=p
w+y+z=q
w+x+z=r
w+x+y=s

are equivalent to {w,x,y,z} = S/3 - {p,q,r,s}, where S=p+q+r+s. So if p<q<r<s are primes with S divisible by 3, there is a unique set of integers satisfying the above equations. They will all be positive iff p+q+r>2s.

Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif=(3/2)^1/3, and pick N such that, for all x>N, there are primes between x and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifx congruent to both 1 and -1 mod 3.

Let p>N be a prime congruent to 1 mod 3. Then pick another prime q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif -1 mod 3, such that p<q<http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifp. Similarly pick r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 mod 3 with q<r<http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifq, and s http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif -1 mod 3 with r<s<http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifr. Then S=p+q+r+s is divisible by 3, and 2s < 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif³p = 3p < p+q+r.

Since p can be chosen arbitrarily large this gives infinitely many such sets.

More generally, if n is even, then we may pick primes with p_i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 mod (n-1) for i=1,...,n-2, p_n-1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif -1 mod (n-1), and p_n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 2 mod (n-1), satisfying

p₁ < p₂ < ... < p_n < (n-1)/(n-2) p₁,

which shows there are infinitely many positive n-primey sets.

If n is odd, we can pick p₁=2, (n-3)/2 primes congruent to 1 mod (n-1), and the remaining (n+1)/2 primes congruent to -1 mod (n-1). So there are infinitely many integral n-primey sets, but no positive n-primey sets.