home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17652 < prev    next >
Encoding:
Internet Message Format  |  1993-01-04  |  1.1 KB
  1. Path: sparky!uunet!dtix!relay!relay2!tecsun1!zogwarg!hoey
  2. From: hoey@zogwarg.etl.army.mil (Dan Hoey)
  3. Newsgroups: sci.math
  4. Subject: Re: Lunde's problem (least number with n divisors)
  5. Keywords: unique factors
  6. Message-ID: <1287@zogwarg.etl.army.mil>
  7. Date: 4 Jan 93 16:49:23 GMT
  8. References: <1993Jan3.003521.26610@tessi.com> <C0BzI1.MIu@math.uwaterloo.ca>
  9. Organization: Naval Research Laboratory, Washington, DC
  10. Lines: 19
  11.  
  12. shallit@graceland.uwaterloo.ca (Jeffrey Shallit) writes:
  13.  
  14. >Basically, you're looking for the smallest integer M with n positive
  15. >*divisors* (although most mathematicians would include 1 and M in the
  16. >enumeration).
  17.  
  18. >Beiler also sketches an algorithm that will find such numbers.  To
  19. >the best of my knowledge, it is not known how to produce the prime
  20. >factorization of the solution in polynomial time (in log n, of
  21. >course).
  22.  
  23. If it were, we would have a polynomial-time factoring algorithm, since
  24. one plus the exponent of 2 is a factor of n, and a proper factor if n
  25. is composite.
  26.  
  27. If the prime factorization of n were given as input, would there then
  28. be a polynomial-time algorithm for this function?
  29.  
  30. Dan
  31.