Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site brl-tgr.ARPA
Path: utzoo!linus!decvax!genrad!mit-eddie!godot!harvard!seismo!brl-tgr!gwyn
From: gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>)
Newsgroups: net.math
Subject: Re: Floor Log Problem
Message-ID: <5496@brl-tgr.ARPA>
Date: Mon, 29-Oct-84 00:37:59 EST
Article-I.D.: brl-tgr.5496
Posted: Mon Oct 29 00:37:59 1984
Date-Received: Tue, 30-Oct-84 19:26:42 EST
References: <1200@eosp1.UUCP>
Organization: Ballistic Research Lab
Lines: 36

> 	 |_lg(n+1)_|+1   |_lg(n)_|+1
> 	2             - 2         = (n+1)(|_lg(n+1)_|-|_lg(n)_|)

There are four cases to consider:

(a)  floor(lg(n+1)) < lg(n+1)  &  floor(lg(n)) < lg(n)

(b)  floor(lg(n+1)) < lg(n+1)  &  floor(lg(n)) = lg(n)

(c)  floor(lg(n+1)) = lg(n+1)  &  floor(lg(n)) < lg(n)

(d)  floor(lg(n+1)) = lg(n+1)  &  floor(lg(n)) = lg(n)

Case (d) is easy; it has the unique integer solution n = 1.  Plug into
the original equation and verify (2 = 2).

Case (a) is not much harder; in this case floor(lg(n+1)) = floor(lg(n))
so both sides of the original equation are 0 (0 = 0).

In case (b), floor(lg(n+1)) = floor(lg(n)) = lg(n), and again 0 = 0.

Case (c) is the only interesting one.  floor(lg(n+1)) = floor(lg(n)) + 1
= lg(n+1).  The LHS of the original equation becomes
	2 ^ (lg(n+1) + 1) - 2 ^ (lg(n+1) - 1 + 1)
or
	2(n+1) - (n+1)
or
	n + 1.
The RHS of the original equation becomes
	(n+1) (lg(n+1) - (lg(n+1) - 1))
or
	(n+1) (1)
or
	n + 1.

QED.