home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14846 < prev    next >
Encoding:
Text File  |  1992-11-12  |  2.6 KB  |  64 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: An Interesting Function
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <VICTOR.92Nov12104834@terse.watson.ibm.com>
  7. In-Reply-To: sasrdt@shewhart.unx.sas.com's message of Wed, 11 Nov 1992 18:37:05 GMT
  8. Date: Thu, 12 Nov 1992 15:48:34 GMT
  9. Reply-To: victor@watson.ibm.com
  10. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  11. References: <1992Oct29.001255.35683@Cookie.secapl.com> <BxKEDt.sL@unx.sas.com>
  12. Nntp-Posting-Host: terse.watson.ibm.com
  13. Organization: IBM, T.J. Watson Research Center
  14. Lines: 48
  15.  
  16. >>>>> On Wed, 11 Nov 1992 18:37:05 GMT, sasrdt@shewhart.unx.sas.com (Randall D. Tobias) said:
  17. Randall> Originator: sasrdt@shewhart.unx.sas.com
  18. Randall> Nntp-Posting-Host: shewhart.unx.sas.com
  19.  
  20.  
  21. Randall> In article <1992Oct29.001255.35683@Cookie.secapl.com>, frank@Cookie.secapl.com (Frank Adams) writes:
  22. Frank> Consider the function W(n) = sum(0<i<n,mod(n,i)).  The problem is to find an
  23. Frank> asymptotic expression for W(n).
  24. Frank>
  25. Frank> It is pretty clear that W(n) = O(n^2).  In fact, we can write
  26. Frank> W(n)=c n^2 + o(n^2).  The question is, what is c?  I know the answer, and
  27. Frank> will post it later if no one gets it.
  28. Frank>
  29. Frank> I think in fact W(n) = c n^2 + O(n), but I can't prove it.  It seems that
  30. Frank> W(n) /= c n^2 + d n + o(n); the O(n) stuff "wanders around".
  31.  
  32. Randall> Well?  I got as far as empirically verifying the
  33.  
  34. Randall>    W(n) /= c n^2 + d n + o(n)
  35.  
  36. Randall> for n up to 100000 or so.  But i haven't got the number theory know-how
  37. Randall> to go much further.  Pretty function, though.
  38.  
  39. Randall> -- 
  40.  
  41. Randall> Randy Tobias          SAS Institute Inc.     sasrdt@unx.sas.com
  42. Randall> (919) 677-8000 x7933  SAS Campus Dr.         72450.2545@compuserve.com
  43. Randall> (919) 677-8123 (Fax)  Cary, NC   27512-8000  norat@aol.com
  44.  
  45. Randall>  ... just my $(-exp(2*sqrt(-1)*arcos(0))/(((2**(2 + 1)) - 1)**2 + 1)).
  46.  
  47. The answer is W(n) = (1 - 1/12 \pi^2) n^2 + O(n log n).  This may be
  48. seen as follows:
  49.  
  50. W(n) = \sum_{i=1}^n (n - i [n/i]) = n^2 - \sum_{i=1}^n i [n/i].
  51.  
  52. The latter sum is = \sum_{i=1}^n \sum_{k=1, i|k}^n i =
  53. \sum_{k=1}^n\sum_{i|k} i = \sum_{k=1}^n \sigma(k), where \sigma(k) is
  54. the sum of the divisors of k.  By Hardy and Wright Theorem 234 (page
  55. 266 in the Fourth edition), the latter sum is = (1/12) \pi^2 + O(n log n).
  56.  
  57.  
  58. --
  59.         Victor S. Miller
  60.         Bitnet: VICTOR at WATSON
  61.         Internet: victor@watson.ibm.com
  62.         IBM, TJ Watson Research Center
  63.         "Great artists steal; lesser artists borrow" Igor Stravinsky
  64.