home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10652 < prev    next >
Encoding:
Text File  |  1992-08-27  |  2.0 KB  |  63 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!destroyer!ubc-cs!unixg.ubc.ca!unixg.ubc.ca!israel
  3. From: israel@unixg.ubc.ca (Robert B. Israel)
  4. Subject: Re: x 2^x = 2^n ?
  5. Message-ID: <israel.714951978@unixg.ubc.ca>
  6. Sender: news@unixg.ubc.ca (Usenet News Maintenance)
  7. Nntp-Posting-Host: unixg.ubc.ca
  8. Organization: University of British Columbia, Vancouver, B.C., Canada
  9. References: <17gnuqINNr7k@darkstar.UCSC.EDU>
  10. Date: Thu, 27 Aug 1992 21:46:18 GMT
  11. Lines: 50
  12.  
  13. In <17gnuqINNr7k@darkstar.UCSC.EDU> soeren@cse.ucsc.edu (Soren Soe) writes:
  14.  
  15. >Can anyone tell me what `x' is in this equation:
  16.  
  17. >    x 2^x = 2^n
  18.  
  19. >Is there a general solution, or do I have to approximate `x' to something like
  20. >x = n - lg n + a_little_more ?
  21. >In fact I can do with an approximation to x, iff 
  22. >        floor(x) <= app(x) <= x
  23.  
  24. >I need the "floor" of `x' to solve the following summation, where k 
  25. >would be equal to floor(x):
  26.  
  27. >    i=n-1
  28. >    SUM   min(2^i, 2^2^(n-i))
  29. >    i=0
  30.  
  31. >    i=k         i=n-1
  32. >    =   SUM  2^i  +  SUM   2^2^(n-i)
  33. >    i=0         i=k+1
  34.  
  35. >--soeren
  36.  
  37. >Soren Soe,
  38. >soeren@ce.ucsc.edu
  39.  
  40. I assume n is a positive integer.  For n = 1, x = 1, so suppose n >= 2.
  41.  
  42. Write n = 2^m k where m is a positive integer and 1 <= k < 2, i.e. 
  43. m = floor(lg n).
  44.  
  45. Let x1 = n - m - 1.  Then x1 2^x1 < n 2^x1 = k 2^(n-1) < 2^n.  So x1 < x.
  46.  
  47. Let x2 = n - m + 1.  Then x2 2^x2 = 2^(n+1) k x2/n >= 2^(n+1) (1 - (m - 1)/n)
  48.                                  >= 2^(n+1) (1 - (m-1) 2^(-m)) > 2^n
  49.  
  50. since  m - 1 < 2^(m-1) for all m.  So x > x2.  Thus floor(x) is either
  51. x3 = n - m or x1 = n - m - 1.
  52.  
  53. Now x3 2^x3 = (n-m) 2^(n-m) = (n-m)k/n 2^n.  To have floor(x) = x3 we need
  54. n <= (n-m) k = (n-m) n 2^(-m), i.e. n >= 2^m + m.  Thus we conclude that
  55. floor(x) = n - m - 1 if 2^m <= n < 2^m + m for some m
  56. floor(x) = n - m     if 2^m + m <= n < 2^(m+1).
  57.   
  58. -- 
  59. Robert Israel                            israel@math.ubc.ca
  60. Department of Mathematics             or israel@unixg.ubc.ca
  61. University of British Columbia
  62. Vancouver, BC, Canada V6T 1Y4
  63.