home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18768 < prev    next >
Encoding:
Text File  |  1993-01-26  |  2.8 KB  |  62 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!howland.reston.ans.net!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: Number Theory
  5. Message-ID: <1993Jan26.132347.4704@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <1993Jan26.021132.15583@murdoch.acc.Virginia.EDU>
  10. Date: Tue, 26 Jan 1993 13:23:47 GMT
  11. Lines: 49
  12.  
  13. In article <1993Jan26.021132.15583@murdoch.acc.Virginia.EDU> pjp9q@honi2.acc.Virginia.EDU (Paul Joseph Perrone) writes:
  14. :
  15. :I am the non-mathematician who posted the question regarding prime
  16. :numbers a few messages ago, and I apologize for incorrectly phrasing
  17. :my question.
  18. :
  19. :Here is my rephrased question:
  20. :
  21. :What is the LARGEST set of prime numbers fulfilling the following
  22. :criterion,
  23. :        1) No prime number in this set can be greater than 1 million;
  24. :        2) No sum nor difference between any two of the primes in this
  25. :           set can be equal to the sum or difference between any other
  26. :           combinations of primes in this set.
  27.  
  28. This is a very interesting and unsolved problem. Firstly, let me say
  29. that it is sufficient to consider differences only. If p+q = r+s, then
  30. p-r=s-q.
  31.  
  32. There is a heuristic which suggests that if M is the upper bound, then
  33. the size of the largest set is between O(sqrt(M)/log(M)) and O(sqrt(M)),
  34. but this is a heuristic only. Hint: assume primes are uniformly distributed
  35. odd numbers between 3 and M  and look at the probability that 4 random
  36. variables drawn from this distribution satisfy x1+x2 = x3+x4.  This
  37. upper bound is also suggested by the birthday paradox. One needs 
  38. O(sqrt(M)) numbers approximately to give a 50% (roughly) chance of collision.
  39. There are other approaches based upon estimates from Goldbach's conjecture. 
  40. These involve estimates of the number of ways 2N can be written as the sum of
  41. two primes for large N. These estimates also give an upper bound of O(sqrt(M))
  42.  
  43. Thus the answer to your question is "around 1000". The exact number would be
  44. very difficult to calculate.
  45.  
  46. :I am looking for references or direction in how to compute such a
  47. :maximum set for the above problem, and for cases where I might
  48.  
  49. The maximum set for M  might be very different for (say) M+2 if M+2
  50. is prime, for example. I do not know offhand how to find the set other
  51. than by exhaustive search, but can suggest a starting point:
  52.  
  53. Consider the set 2,3,5,11,23,47 ....  [double then add 1]. Consider the
  54. nearest prime to each term. This gives a starting set of O(log M) numbers.
  55. Then start "fitting" additional primes.
  56.  
  57. --
  58. Bob Silverman
  59. These are my opinions and not MITRE's.
  60. Mitre Corporation, Bedford, MA 01730
  61. "You can lead a horse's ass to knowledge, but you can't make him think"
  62.