From - Mon Feb  9 21:00:31 1998
From: mareg@csv.warwick.ac.uk (Dr D F Holt)
Newsgroups: sci.math
Subject: Re: sums of distinct primes
Date: 9 Feb 1998 12:00:31 -0000
Organization: University of Warwick, UK

spear@empty.set (David Spear) writes:
>These simple results concerning the representation of a positive
>integer n as a sum of distinct primes grew out of my attempts to
>show that S_n cannot be embedded in A_(n+1) if n>=2. However the
>results seem interesting in their own right:

Sorry, I have lost the original articles about this. I think I have finally
sorted out proofs using only Bertand's Postulate (BP). This is perhaps a rather
silly way of proving that S_n cannot be embedded in A_{n+1}, but as
you say, the results on decompositions of numbers seem quite interesting.

BP: For any positive integer n there is a prime p with  n < p < 2n.

Theorem A.  Every integer n>6 can be written as a sum of positive powers of
distinct odd primes.  Furthermore, if n>13, then this can be done using more
than one summand.
(e.g. 13 = 13 is the only solution for n=13, but 17 = 9 + 5 + 3)

From this we easily deduce (basically by applying Theorem A to n-2):

Theorem B. Every positive integer n not equal to 1, 3 or 6 can be written
as a sum of positive powers of distinct primes, one of which is a power of 2. 

which has the corollary:

For n not equal to 1,3 or 6, there exists m such that the symmetric group
S_n has an element of order m, but the alternating group A_{n+1} does not.

An inspection of the proof of Theorem A shows that the only non-prime
summand that occurs is 9, and that 9 and 7 never need appear together, so
by replacing 9 by 7+2 we can prove:

Theorem C. Every integer n>6 can be written as a sum of distinct primes.

Is that "well-known"?

Proof of Theorem A.
Proof is by induction on n.  It is vacuously true for n=1.

Case 1. n odd.
  The cases n=7,9,11,13,15=7+5+3,17=9+5+3,19=11+5+3 all work, so assume n>19.
  By BP applied to (n-7)/2, there is a prime p with (n-5)/2 <= p < n-7, 
  and n>19 implies p>7.
  We apply induction to n-p. This provides the required decomposiiton of n,
  except possibly in the two cases:
  (a) p=(n-5)/2, (n-p)=p+5;  and
  (b) p=(n-3)/2, (n-p)=p+3.

  In these cases, we apply BP again to  (p-1)/2, to find a prime q with
  (p+1)/2 <= q < p-1, and then apply induction to n-p-q = p+5-q or p+3-q.
  Note that p>7 means that p cannot re-occur as a summand of n-p-q.
  In fact, the only cases where this might not provide the required
  decomposition of  n  are where
  n-p-q=q; i.e. q=(p+5)/2 or q=(p+3)/2 in (a) and (b), respectively.
  But here we use the part of the theorem that says that for q>13,
  there is a decomposition of q using more than one summand.
  That leaves the cases q<=13 to be checked individually, which is
  straightforward. e.g. q=13, p=23, n=49 = 41+7.

Case 2. n even.
  8=5+3, so assume n>=10.
  By BP applied to (n-6)/2, there is a prime p>=3 with (n-4)/2 <= p < n-6.
  Applying induction to n-p completes the proof except in the case n=2p.
  But again this only fails for p<=13, and we can check the cases
  individually. e.g. p=13, n=26=19+7.
  Note. This proof gives the decomposition 7+9 for n=16, but we also have
  16=11+5, so we never need to use 9 and 7 together.

Derek Holt.

-------------------------------------------------------------------------
From: Paul Zimmermann

# M0022: partitions of n into distinct primes
Primes:=proc(n) if isprime(n) then 1 else 0 fi end:
M[22]:=[N,{N=PowerSet(P),P=Predefined(Primes)},unlabelled]:
seq(count(M[22],size=n),n=0..57);

 1, 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 5, 5,

     6, 5, 6, 7, 6, 9, 7, 9, 9, 9, 11, 11, 11, 13, 12, 14, 15, 15, 17, 16, 18,

     19, 20, 21, 23, 22, 25, 26, 27, 30, 29, 32

# M0022': partitions of n into distinct odd primes

 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 2,
     3, 3, 3, 4, 3, 5, 4, 4, 5, 5, 6, 6, 5, 7, 7, 7, 8, 8, 9, 8, 9, 
     11, 11, 10, 12, 12, 13, 14, 14, 16, 15, 16