home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17686 < prev    next >
Encoding:
Text File  |  1993-01-05  |  2.1 KB  |  57 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!spool.mu.edu!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: I imagine this comes up all the time...
  5. Message-ID: <1993Jan5.003642.11261@linus.mitre.org>
  6. Keywords: unique factors
  7. Sender: news@linus.mitre.org (NONUSER)
  8. Nntp-Posting-Host: gauss.mitre.org
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. References: <1993Jan3.003521.26610@tessi.com>
  11. Date: Tue, 5 Jan 1993 00:36:42 GMT
  12. Lines: 43
  13.  
  14. In article <1993Jan3.003521.26610@tessi.com> ronl@tessi.com (Ron Lunde) writes:
  15. >I'm not a mathematician, so I'd appreciate it if anyone could point me to
  16. >any references on this topic (that I might be able to understand :-)).
  17. >
  18. >The question I was toying with last night was: Given a number N,
  19. >what is the smallest number M such that aside from 1 and M, M has exactly
  20. >N unique factors (I guess I'm probably using "factor" in a funny way here,
  21.  
  22. Mathematicians usually include 1 and M as factors. Let 
  23.  
  24. N = p1^a1 * p2^a2 * p3^a3 * ....
  25.  
  26. be the canonical prime factorization of N. Then, the number of
  27. factors is (a1+1) * (a2+1) * ....
  28.  
  29. If you don't want to include 1 and N, then subtract 2.
  30.  
  31. For your problem, we want (a1+1)(a2+1)... - 2 = 15,  so (a1+1)(a2+1) ... = 17
  32. This leads to a1+1 = 17, or a1 = 16.
  33.  
  34. The smallest such N is 2^16. Indeed, 2 through 2^15 are the factors.
  35.  
  36. If you allow 1 and N as factors, we have (a1+1)(a2+1) = 15;
  37. so either a1 =2 and a2 = 4, giving 2^2 * 3^4 = 324  or  a1 = 14 giving
  38. 2^14.  
  39.  
  40. It is easy to verify that 324 has 15 distinct factors. Note that for
  41. ANY number to have an odd number of distinct factors it must be a 
  42. square.
  43.  
  44.  
  45. >since I'm not referring to primes, necessarily).  Obviously there *is* such
  46. >a number, since we can construct at least one by multiplying the first N
  47. >primes.  It seems odd that the first ones are all fairly small, but I can't
  48. >find the 15th (at least nothing smaller than 614889782588491410):
  49. >
  50.  
  51. rest deleted....
  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.