## Homework 18 Special.  1-April-2012.  Pat Devlin. ##
## I have no preferrence about keeping my work private ##

Help:=proc():
  print(`mex(S)`):
end proc:


mex:=proc(S) local i:
  return min({seq(i, i=0..max(S)+1)} minus S):
end proc:



# 
# After considering the sequence a[i] for a little bit, I realize that it is
# {p[1], p[2], p[3], ...}, where p[k] is the kth prime number
# 
# This is 'obvious' by the sieve method sort of definition of the sequence
# 


# Claim 1 is that there are infinitely many i such that a_[i+1] - a_[i] = 2 is
# the twin prime conjecture.
# 
# Claim 2 is that for every n, there exist i and j such that 2n = a_i + a_j is
# the Golbach conjecture.


# Proof of claim 1: this follows by a simple counting argument
# [hint: partition the set of integers (i,k), by the value of |a_k - a_i|,
# and use the prime number theorem to obtain a contradiciton]
#
#
# Proof of claim 2: clear by induction on n.
# 
# (Both of these proof ideas were suggested by my wife, Nora, to whom any
# fields medal is due)
# 
# Details of these proofs are left to the reader as exercises.  Additional
# hints can be found in the appendix.  (Try not to use the internet!)