Conference rusure::math

2062.0. "differences between powers" by FLOYD::YODER (MFY) Fri Sep 06 1996 15:42

First, some background which may be skipped if you want to go straight to the
problem.

I once wrote an Ada RTL which supported a priority range which was a 36-bit
integer (yes, it was on the PDP-10).  However, we couldn't make the entire
priority range available to the user because some high (and low) values had to
be reserved for, e.g., the debugger and null tasks.  My recollection is that we
took out the ones we absolutely needed, but my preferred solution would have
been to make available the range -10^10 .. 10^10 on the grounds that it's easy
to remember and insures there are plenty of leftover values for future needs.

(End of background.)

Problem: find simply computable lower bounds for f(n) = 2^n - 10^m, where 10^m
is the largest power of 10 <= 2^n; n is a positive integer. (You needn't bother
writing some hairy expression for m, but can use it directly if you want.) 
Here's one example:

We have m < n, so f(n) = 2^m(2^(n-m) - 5^m) >= 2^m since the two operands of the
subtraction differ by at least 1 (one is odd and the other even).

A fact which may or may not be useful is that 2^n = 10^m approx. means that n =
m lg 10 approx., where lg(n) = ln(n)/ln(2) is log base 2, so n/m approximates
lg(10).

It's OK to deal with special cases, but it's inelegant if the number of special
cases your formula handles is finite.  :-)  For example, if your formula only
dealt with cases where n was a power of 2, that would be fine.