Author |
Topic: No set of 5 with sum of 3 equal to a prime (Read 480 times) |
|
gkwal
Newbie
Posts: 25
|
 |
No set of 5 with sum of 3 equal to a prime
« on: May 3rd, 2007, 11:31am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: No set of 5 with sum of 3 equal to a prime
« Reply #1 on: May 3rd, 2007, 2:29pm » |
Quote Modify
|
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.
|
| « Last Edit: May 3rd, 2007, 2:31pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: No set of 5 with sum of 3 equal to a prime
« Reply #2 on: May 3rd, 2007, 2:36pm » |
Quote Modify
|
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?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: No set of 5 with sum of 3 equal to a prime
« Reply #3 on: May 3rd, 2007, 3:44pm » |
Quote Modify
|
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  = (3/2)1/3, and r =  1. Then for sufficiently large x, there is always a prime p between x and x with p  r mod 3.
Proof: By a result of Dirichlet,
 r(x) = #{primes p < x, p r mod 3} ~ 1/2 x/log x as x  .
Hence, for any fixed  > 0, we have
(1-) 1/2 x/log x < r(x) < (1+) 1/2 x/log x
for all sufficiently large x. So if we pick >0 such that
1 > (1-)/(1+) > 1/,
then for x sufficiently large, we will have
(1-)/(1+) > 1/ [1 + log /log x],
and therefore
r(x) > (1-) 1/2 x/log (x)
> (1+) 1/2 x/log x
> r(x),
which means there must be a prime p r mod 3 between x and x, as claimed.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: No set of 5 with sum of 3 equal to a prime
« Reply #4 on: May 4th, 2007, 3:48pm » |
Quote Modify
|
Followup/generalization:
Call a set {x1,...,xn} 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 > 1. Then for x sufficiently large, there is always a prime p between x and x with p r mod n.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: No set of 5 with sum of 3 equal to a prime
« Reply #5 on: May 20th, 2007, 9:25pm » |
Quote Modify
|
on May 3rd, 2007, 2:36pm, 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 =(3/2)1/3, and pick N such that, for all x>N, there are primes between x and x congruent to both 1 and -1 mod 3.
Let p>N be a prime congruent to 1 mod 3. Then pick another prime q -1 mod 3, such that p<q<p. Similarly pick r 1 mod 3 with q<r<q, and s -1 mod 3 with r<s<r. Then S=p+q+r+s is divisible by 3, and 2s < 23p = 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 pi 1 mod (n-1) for i=1,...,n-2, pn-1 -1 mod (n-1), and pn 2 mod (n-1), satisfying
p1 < p2 < ... < pn < (n-1)/(n-2) p1,
which shows there are infinitely many positive n-primey sets.
If n is odd, we can pick p1=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.
|
| « Last Edit: May 20th, 2007, 9:43pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print