Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site watdaisy.UUCP
Path: utzoo!watmath!watdaisy!gjerawlins
From: gjerawlins@watdaisy.UUCP (Greg Rawlins)
Newsgroups: net.math
Subject: Re: Floor Log Problem
Message-ID: <6734@watdaisy.UUCP>
Date: Sun, 11-Nov-84 05:39:46 EST
Article-I.D.: watdaisy.6734
Posted: Sun Nov 11 05:39:46 1984
Date-Received: Mon, 12-Nov-84 10:43:09 EST
Organization: U of Waterloo, Ontario
Lines: 44



Required to prove:

>	 |_lg(n+1)_|+1   |_lg(n)_|+1
>	2             - 2         = (n+1)(|_lg(n+1)_|-|_lg(n)_|)
>
>	where
>		|_lg X_| 
>
>	is the floor of the log base 2 of X.
--------------
	This problem is straightforward once you observe
that floor(lg(n+1)) - floor(lg(n)) = 1 iff n is a power of 2
minus 1, otherwise it is zero. This is easy to see since the
discrete log to base b only changes value (by one) at each
power of b.
	When n != a power of 2 minus 1 both the LHS and RHS
will be zero. When n = a power of 2 minus 1 they will both
equal n+1 (= a power of 2). All that is happening here is
that the expression floor(lg(n+1)) - floor(lg(n)) acts as an
indicator function.:-)

/--------------------------------------------------------\
|Mail :Greg Rawlins : U.of Waterloo,Waterloo,Ont.N2L3G1  |
|      allegra \                                         |
|      clyde \  \                                        |
|UUCP :decvax ---- watmath --- watdaisy --- gjerawlins   |
|      ihnp4 /  /                                        |
|      linus  /                                          |
|CSNET:gjerawlins%watmath%@waterloo.csnet                |
|ARPA :gjerawlins%watmath%waterloo.csnet@csnet-relay.arpa|
\--------------------------------------------------------/
-- 
/--------------------------------------------------------\
|Mail :Greg Rawlins : U.of Waterloo,Waterloo,Ont.N2L3G1  |
|      allegra \                                         |
|      clyde \  \                                        |
|UUCP :decvax ---- watmath --- watdaisy --- gjerawlins   |
|      ihnp4 /  /                                        |
|      linus  /                                          |
|CSNET:gjerawlins%watmath%@waterloo.csnet                |
|ARPA :gjerawlins%watmath%waterloo.csnet@csnet-relay.arpa|
\--------------------------------------------------------/