home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14866 < prev    next >
Encoding:
Text File  |  1992-11-12  |  1.5 KB  |  38 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!secapl!Cookie!frank
  3. From: frank@Cookie.secapl.com (Frank Adams)
  4. Subject: Re: An Interesting Function
  5. Message-ID: <1992Nov12.195839.76492@Cookie.secapl.com>
  6. Date: Thu, 12 Nov 1992 19:58:39 GMT
  7. References: <1992Oct29.001255.35683@Cookie.secapl.com> <BxKEDt.sL@unx.sas.com>
  8. Organization: Security APL, Inc.
  9. Lines: 27
  10.  
  11. In article <BxKEDt.sL@unx.sas.com> sasrdt@shewhart.unx.sas.com (Randall D. Tobias) writes:
  12. >In article <1992Oct29.001255.35683@Cookie.secapl.com>, frank@Cookie.secapl.com (Frank Adams) writes:
  13. >|> Consider the function W(n) = sum(0<i<n,mod(n,i)).  The problem is to find an
  14. >|> asymptotic expression for W(n).
  15. >|>
  16. >|> It is pretty clear that W(n) = O(n^2).  In fact, we can write
  17. >|> W(n)=c n^2 + o(n^2).  The question is, what is c?  I know the answer, and
  18. >|> will post it later if no one gets it.
  19. >|>
  20. >|> I think in fact W(n) = c n^2 + O(n), but I can't prove it.  It seems that
  21. >|> W(n) /= c n^2 + d n + o(n); the O(n) stuff "wanders around".
  22. >
  23. >Well?
  24.  
  25. The key is to look at the summation from the "back end".  Between n/2 and
  26. n, the values go in arithmetic sequence from just under n/2 to 0.  Between
  27. n/3 and n/2, they go from n/3 to 0.  This works well enough back to
  28. sqrt(n); and the terms up to sqrt(n) sum to at most O(n).  So
  29.  
  30.   W(n) ~ SUM((k,1,sqrt(n)),(n/k - n/(k+1))*n/(2(k+1)))
  31.        ~ n^2 * (SUM(k,1/(k*(k+1)))-SUM(k>0,1/(k+1)^2))/2
  32.        = n^2 * (1 - (pi^2/6 - 1))/2
  33.        = (1 - pi^2/12) * n^2
  34.  
  35. So c = pi^2/12.
  36.  
  37. (A more precise analysis is required to get an error estimate.)
  38.