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