home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17635 < prev    next >
Encoding:
Text File  |  1993-01-04  |  2.8 KB  |  61 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watmath!graceland.uwaterloo.ca!shallit
  3. From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit)
  4. Subject: Lunde's problem (least number with n divisors)
  5. Message-ID: <C0BzI1.MIu@math.uwaterloo.ca>
  6. Keywords: unique factors
  7. Sender: news@math.uwaterloo.ca (News Owner)
  8. Organization: University of Waterloo
  9. References: <1993Jan3.003521.26610@tessi.com>
  10. Date: Mon, 4 Jan 1993 13:15:37 GMT
  11. Lines: 48
  12.  
  13. In article <1993Jan3.003521.26610@tessi.com> ronl@tessi.com (Ron Lunde) writes:
  14. >I'm not a mathematician, so I'd appreciate it if anyone could point me to
  15. >any references on this topic (that I might be able to understand :-)).
  16. >
  17. >The question I was toying with last night was: Given a number N,
  18. >what is the smallest number M such that aside from 1 and M, M has exactly
  19. >N unique factors (I guess I'm probably using "factor" in a funny way here,
  20. >since I'm not referring to primes, necessarily).  Obviously there *is* such
  21. >a number, since we can construct at least one by multiplying the first N
  22. >primes.  It seems odd that the first ones are all fairly small, but I can't
  23. >find the 15th (at least nothing smaller than 614889782588491410):
  24. >
  25. >N Divisors Smallest M  Factors
  26. >2          6           2, 3
  27. >3          16          2, 4, 8
  28. >4          12          2, 3, 4, 6
  29. >5          64          2, 4, 8, 16, 32
  30. >6          24          2, 3, 4, 6, 8, 12
  31. >7          36          2, 3, 4, 6, 9, 12, 18
  32. >8          48          2, 3, 4, 6, 8, 12, 16, 24
  33. >9          1024        2, 4, 8, 16, 32, 64, 128, 256, 512
  34. >10         60          2, 3, 4, 5, 6, 10, 12, 15, 20, 30
  35. >11         4096        2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048
  36. >12         192         2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96
  37. >13         144         2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72
  38. >14         120         2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60
  39. >
  40. >Anyone know about this?
  41. >Thanks!
  42. >
  43. >Ron Lunde
  44. >email: ronl@tessi.com
  45.  
  46. Basically, you're looking for the smallest integer M with n positive *divisors*
  47. (although most mathematicians would include 1 and M in the enumeration).
  48.  
  49. This problem has not been extensively studied, to my knowledge.  The sequence
  50. is #A5179 in the new version of Sloane's book (which has yet to appear).  The
  51. only reference I know is Beiler, Recreations in the Theory of Numbers, pp. 7-8.
  52. Beiler also sketches an algorithm that will find such numbers.   To the best
  53. of my knowledge, it is not known how to produce the prime factorization of
  54. the solution in polynomial time (in log n, of course).  It is clearly impossible,
  55. in general, to produce the (say base-10) expansion of the solution in polynomial
  56. time in log n, since in general it could have Theta(n) digits.
  57.  
  58. The least number with 17 divisors (or 15, using your definition) is 2^16.
  59.  
  60. Jeff Shallit
  61.