home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10321 < prev    next >
Encoding:
Text File  |  1992-08-17  |  2.8 KB  |  71 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!yktnews!victor
  3. From: victor@watson.ibm.com (Victor Miller)
  4. Subject: Re: Primes
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <VICTOR.92Aug17102144@terse4.watson.ibm.com>
  7. In-Reply-To: bs@faron.mitre.org's message of Mon, 17 Aug 1992 11:02:34 GMT
  8. Date: Mon, 17 Aug 1992 14:21:44 GMT
  9. Reply-To: victor@watson.ibm.com
  10. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  11. References: <1992Aug17.160252.10145@waikato.ac.nz> <1992Aug17.110234.13501@linus.mitre.org>
  12. Nntp-Posting-Host: terse4.watson.ibm.com
  13. Organization: IBM, T.J. Watson Research Center
  14. Lines: 55
  15.  
  16. >>>>> On Mon, 17 Aug 1992 11:02:34 GMT, bs@faron.mitre.org (Robert D. Silverman) said:
  17. Bob> Nntp-Posting-Host: faron.mitre.org
  18.  
  19. Bob> In article <1992Aug17.160252.10145@waikato.ac.nz> bill@waikato.ac.nz writes:
  20. Bob> :How many primes are there less than 2 to the power of p?
  21. Bob> :
  22. Bob> 2^p/(p log 2)   [approximately]
  23.  
  24. Bob> :Is there a way of calculating this, or does anyone know of where I can get my
  25. Bob>  
  26. Bob> How big is p? If p isn't too large it can be calculated exactly using
  27. Bob> methods developed by Lagarias, Odlyzko, and Coppersmith. These are
  28.  
  29. Make that Lagarias, Odlyzko and Miller (not Coppersmith!).
  30.  
  31. Bob> improvements on the Meisel-Lehmer method.
  32.  
  33. Bob> :hands on a list of primes so I can find out how many primes there are
  34. Bob> :less than 2^16 or 2^32 for example?
  35. Bob>  
  36. Bob> For p THIS small you can do it directly by sieving. 2^16 will take
  37. Bob> milliseconds. How long 2^32 will take is memory dependent, but should
  38. Bob> only be a few hours at most.
  39.  
  40. Bob> :Is there some way of determining (or estimating) the expected magnitude of the
  41. Bob> :nth prime? Or of the growth of the difference between the nth and (n+1)th
  42. Bob>  
  43. Bob> the n'th prime is approximately n log n.
  44.  
  45. Bob> the growth of the difference is not well understood. studying it involves
  46. Bob> some deep methods in analytic number theory. For example, if one has
  47. Bob> a 'random' sequence of integers going to infinity, whose normal order
  48. Bob> difference is log n, then one has lim sup (n-->infinity) p_n/log n = 2,
  49. Bob> whereas for primes, the lim sup is infinite. Further, Rankin has shown
  50. Bob> that the difference is
  51.  
  52. Bob> C log n  loglog n  loglogloglog n
  53. Bob> ---------------------------------
  54.  
  55. Bob>     logloglog n ^2
  56.  
  57. Bob> infinitely often.
  58.  
  59. Bob> I suggest you start by reading a book on number theory. Start with
  60. Bob> Hardy & Wright.
  61. Bob> --
  62. Bob> Bob Silverman
  63. Bob> These are my opinions and not MITRE's.
  64. Bob> Mitre Corporation, Bedford, MA 01730
  65. Bob> "You can lead a horse's ass to knowledge, but you can't make him think"
  66. --
  67.             Victor S. Miller
  68.             Vnet and Bitnet:  VICTOR at WATSON
  69.             Internet: victor@watson.ibm.com
  70.             IBM, TJ Watson Research Center
  71.