home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10657 < prev    next >
Encoding:
Text File  |  1992-08-27  |  2.4 KB  |  78 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!usc!sdd.hp.com!caen!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.714986049@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> <israel.714951978@unixg.ubc.ca>
  10. Date: Fri, 28 Aug 1992 07:14:09 GMT
  11. Lines: 65
  12.  
  13. In <israel.714951978@unixg.ubc.ca> israel@unixg.ubc.ca (Robert B. Israel) writes:
  14.  
  15. >In <17gnuqINNr7k@darkstar.UCSC.EDU> soeren@cse.ucsc.edu (Soren Soe) writes:
  16.  
  17. >>Can anyone tell me what `x' is in this equation:
  18.  
  19. >>    x 2^x = 2^n
  20.  
  21. >>Is there a general solution, or do I have to approximate `x' to something like
  22. >>x = n - lg n + a_little_more ?
  23. >>In fact I can do with an approximation to x, iff 
  24. >>        floor(x) <= app(x) <= x
  25.  
  26. >>I need the "floor" of `x' to solve the following summation, where k 
  27. >>would be equal to floor(x):
  28.  
  29. >>    i=n-1
  30. >>    SUM   min(2^i, 2^2^(n-i))
  31. >>    i=0
  32.  
  33. >>    i=k         i=n-1
  34. >>    =   SUM  2^i  +  SUM   2^2^(n-i)
  35. >>    i=0         i=k+1
  36.  
  37. >>--soeren
  38.  
  39. >>Soren Soe,
  40. >>soeren@ce.ucsc.edu
  41.  
  42. >I assume n is a positive integer.  For n = 1, x = 1, so suppose n >= 2.
  43.  
  44. >Write n = 2^m k where m is a positive integer and 1 <= k < 2, i.e. 
  45. >m = floor(lg n).
  46.  
  47. >Let x1 = n - m - 1.  Then x1 2^x1 < n 2^x1 = k 2^(n-1) < 2^n.  So x1 < x.
  48.  
  49. >Let x2 = n - m + 1.  Then x2 2^x2 = 2^(n+1) k x2/n >= 2^(n+1) (1 - (m - 1)/n)
  50. >                                 >= 2^(n+1) (1 - (m-1) 2^(-m)) > 2^n
  51.  
  52. >since  m - 1 < 2^(m-1) for all m.  So x > x2.  Thus floor(x) is either
  53. >x3 = n - m or x1 = n - m - 1.
  54.  
  55. >Now x3 2^x3 = (n-m) 2^(n-m) = (n-m)k/n 2^n.  To have floor(x) = x3 we need
  56. >n <= (n-m) k = (n-m) n 2^(-m), i.e. n >= 2^m + m.  Thus we conclude that
  57.  
  58. Oops! Reverse those inequalities, we need n <= 2^m + m.
  59.  
  60. >floor(x) = n - m - 1 if 2^m <= n < 2^m + m for some m
  61. >floor(x) = n - m     if 2^m + m <= n < 2^(m+1).
  62.  
  63. So it's really:
  64. floor(x) = n - m if 2^m <= n <= 2^m + m
  65. floor(x) = n - m - 1 if 2^m + m < n < 2^(m+1).
  66.  
  67. >  
  68. >-- 
  69. >Robert Israel                            israel@math.ubc.ca
  70. >Department of Mathematics             or israel@unixg.ubc.ca
  71. >University of British Columbia
  72. >Vancouver, BC, Canada V6T 1Y4
  73. -- 
  74. Robert Israel                            israel@math.ubc.ca
  75. Department of Mathematics             or israel@unixg.ubc.ca
  76. University of British Columbia
  77. Vancouver, BC, Canada V6T 1Y4
  78.