Hei ed,
I waited since september 5, for a solution to Gordon
Bower question about
powers of 2 beginning with a fixed number and then I
decided to solve it by
myself. Here is the Mathematica solution where n is
the fixed number and b
is the exponent base.

firstnum[n_, b_] := 
  Block[{fr1 = Log[10, b], fr2 =
FractionalPart[N[Log[10, n], 20]], fr3, 
      fr4 = FractionalPart[N[Log[10, n + 1], 20]], 
      fr5 = Power[10, -StringLength[ToString[n]]], i =
1},
    fr3 = fr1;
    While[
      Abs[FractionalPart[N[fr3, 20]] - fr2] > fr5 && 
        Abs[FractionalPart[N[fr3, 20]] - fr4] > fr5,
fr3 = fr3 + fr1; 
      i = i + 1];
    Print["lower exponent is: ", i]
    ]
    
    
Edoardo Gueglio
Milan
Italy
----------------------------------------------------
OK - here is my method. It finds the smallest integer n such that the
real part of the base-10 logarithm of 2^n lies in any given open
interval (a,b) where 0<a<b<1.

We get closer and closer to the interval from below until we hit the
interval. We keep track of where n is, and we let r stay equal to the
real part of the base-10 logarithm of 2^n at all points. We use the
function f that takes a number 0<x<1 and outputs the smallest positive
integer k such that the real part of the base-10 logarithm of 2^k is
smaller than x. We give the program for f afterwards. We fix z at
Log(2)/Log(10) so that the real part of the base-10 logarithm of 2^n is
the real part of z*n.

MAIN PROGRAM

Set z:=Log(2)/Log(10);
Set n:=0, r:=0;
While r is less than or equal to a do
{
 Set k:=f(b-r);
 Set n:=n+k;
 Set r:=RealPart(z*n)
}
Output n.

PROGRAM FOR FUNCTION f(x)
Set Lowest:=1, Highest:=1, l:=z; 
While l is more than or equal to x do
{
 Set Sum:=Lowest+Highest;
 Set p:=RealPart(Sum*z);
 If (p is less than l) then
 {
  Set Lowest:=Sum; l:=p;
 }
 else
 {
  Set Highest:=Sum;
 }
}
return Lowest;

FACT 1: If the function works, the program works.
 1) At every step, the real part of z*n is less than b.
 It is to start with. We proceed by induction.
 At the start of every step, the real part of z*n is r, which by the
  induction hypothesis is less than b. Because the function works,
  the real part of z*k is less than b-r. Therefore, at the end of the
  step, the real part of z*n is less than b.
 2) At the end, the real part of z*n is in the interval (a,b)
 Clear.
 3) If m is such that the real part of z*m is in the interval (a,b) then
at
    every step, n<=m.
 It is at the start. We proceed by induction.
 At the start of every step, the real part of z*n is r, and n<=m.
 the real part of z*(m-n) is the real part of z*m minus r, which must be
 less than b-r. Therefore since f works, k<m-n, and hence n<=m at the
end
 of the step. The induction is complete.
This proves the fact.

FACT 2: The function works
 Harder to prove. Proof follows.

Luke Pebody
--------------------------------------------------------------------
You mentioned liking close approximations on this week's Mathpuzzle page
update (and have posted a variety of them in the past.) This, and the
diophantine inequality puzzle of the week before, reminded me of a fun
little exercise I indulged in in the spring of 2000.

The question of the week for the now-defunct student math club, of which I
was an advisor, was "is there a power of 2 that begins with ten sevens in
a row?" (Yes, there are infinitely many of them beginning with any finite
string of digits you want.) But no-one bothered to try to actually FIND
such a number. The next week I had to give a short presentation explaining
how I proved that 2^40193336864 = 7.777777777996 x 10^12099400021. (No
harm in me revealing the answer, since the fun is in discovering the
method of finding the solution for any sequence of digits you want.)

It makes a fun party game (if you are a sufficiently warped-minded
mathematician) to find an n such that 2^n starts with your girlfriend's
birthdate or suchlike and surprise her with it. Must warn you that mine
was not overly impressed by it, though.

Question: find n such that 2^n begins with 7777777777.

Or, in other words, find n such that

log 7.777777777 < n log 2 (mod 1) < log 7.777777778

The proof that such an n exists follows from the irrationality of log 2,
and the multiples of any irrational number mod 1 are dense in (0,1). Now,
all we have to do is find one.

This problem has a lot in common with finding rational approximations to
irrational numbers. The "mod 1" is keeping us from doing that in quite the
usual straightforward way though. Brute force search doesn't work well
either if the target is more than 6-8 digits either. We need a more
systematic way to search through the possibilities, looking only at the
possible n's which come "close" to our target.

Given a number m which comes "close" to the target, we can improve this
guess if we can find some k such that 2^k is very near a power of 10, then
look at 2^(m+k).

A list of such k's comes from the continued fraction expansion of log 2.
We'll need to carry out this expansion far enough to be good to at least
20 decimal places (we care about the first ten digits to the right of the
decimal point of k log 2, and have to expect to waste about ten digits to
the left of it in the process.)

log 2 ~ .30102999+ has continued fraction expansion [0 ; 3, 3, 9, 2, 2, 4,
6, 2, 1, 1, 3, 1, 18, 1, 6, 1, 2, 1, 1, 4, 1, 42, 6, 1 etc]

and convergents

1/3, 3/10, 28/93, 59/196, 146/485, 643/2136, 4004/13301, and so on (we
need the first 22 of these to get to our answer.)

Recall also that each continued fraction convergent is a linear
combination of the two previous ones, and that the convergents are
alternately too high and too low.

So, to improve a crude approximation like 2^3 = 8 ... we first go up by
threes, then by tens, then by ninety-threes, then by 196es:

2^3 = 8
2^6 = 6.4 x 10^1 ... overshot the target, so switch to tens
2^16 = 6.5536
2^26 ~ 6.7108
2^36 ~ 6.8719
2^46 ~ 7.0357
...
2^96 ~ 7.9228 ... overshot again, so switch to 93s (and notice that
instead of adding one 3 and nine 10s to 2^3, we could have just added 93)
2^189 ~ 7.84637
2^282 ~ 7.77067 ... getting warmer... switch to adding 196es
2^478 ~ 7.80437 ... switch to adding 485s
2^963 ~ 7.79625
2^1448 ~ 7.78813
2^1933 ~ 7.78003
2^2418 ~ 7.77194 ... switch to adding 2136s

...and so on until we approach our target with whatever degree of
precision we wish.

Since there are some well-known results about continued fractions being
the best possible approximations among all fractions with small
denominators, we have a guarantee that (say) every power of 2 from 1934 up
to 2417 is going to be *farther* from our target than the numbers we've
previously tested.

You will no doubt be pleased to hear I did the original work in 2000 in
Mathematica (an aging copy of Student version 2.2, actually!), though I
sure didn't code it particularly elegantly: (Warning, I had to retype this
by hand from a printout in my files, but I hope there are no typos!)

log2 = N[Log[10,2],40]

cflist = {{1,0,1,-log2}};
Do[{
x = Normal[ContinuedFraction[log2, i]];
a[i] = Numerator[x];
b[i] = Denominator[x];
c[i] = (x-N[log2,27]) b[i];
AppendTo[cflist, {i, a[i], b[i], c[i]}]}, {i,2,25}]

target = N[(Log[10,7777777777]+Log[10,7777777778])/2, 40]-9
epsilon = N[(Log[10,7777777778]-Log[10,7777777777])/2, 40]

powerlist = {{0,1}, {3,8}};
runningsum = 3;
runningm = 3 log2;
i = 2;
While[Abs[runningm - target] > epsilon,
{While[Abs[runningm-target]> epsilon &&
Sign[runningm-target] == Sign[c[i]],
{runningsum=runningsum + b[i];
runningm = Mod[runningm - c[i], 1];
AppendTo[powerlist, {runningsum, 10^runningm}]
}];
i=i+1
}]

After you run this code, "cflist" will contain convergents of the cfe of
log 2 from 1/3 up to 174131244785/578451474249, and "powerlist" will
contain all the steps in the appromixation of the target, from 3, 6, 16
... on up to ...36346536204, 38269936534, 40193336864.

Using this code for another target will, of course, mean making the
obvious changes to target= and epsilon=, and doing the first step by hand
to know what to initialize powerlist, runningsum, and i with. If your
target is more than 12 digits long, cflist needs to be made longer.
Changing the base from 2 to 3 (or any other number that's not a power ten)
requires several changes in the obvious places.

Gordon Bower
-----------------------------------------------------------------------
Here's a method for finding a power of 2 with given starting digits.

The problem is to solve, for x,y integers,

7.777777777 x 10^y < 2^x < 7.777777778 x 10^y

where the 7.777... may be replaced by any desired sequence of starting
digits.

Take the base 10 log of each term:

y + log10(7.777777777) < x log10(2) < y + log10(7.777777778)

Calculate the logs to an appropriate precision. The logs of the starting
digits must be solved to the point that they differ; the log10(2) must be
solved to approximately twice this precision, because it is going to be
multiplied by the potentially large number x.

This gives an equation like:

y + 0.8908555305315 < 0.301029995663981... x < y + 0.8908555305873

Here y is an integer, so ignore it and the whole number part
of 0.3010... x, a sort of mod 1

So we need to find x such that 0.3010... x has fractional part near
0.8908...

This is not trivial, but still doable. Given the fractional part of
the product for some x, you can always find another x with a smaller
fractional part by multiplying by the smaller number that makes that
fractional part exceed 1; this new product will have a smaller
fractional part than the original. So for x = 4, the product is
1.204... and the fractional part is reduced to 0.204...

You can jump to other values of x when you see how to make smaller
fractional parts. x=10 is a good choice yielding a fractional part
of 0.010.... Then you might go to x=3 or 0.903... and add ten 10s
to get 1.003 or thereabouts for x=103. Gradually in this manner you
find the mod 1 inverse of log10(2). When the fractional part is less
than the difference between the other logs, you are guaranteed to
be able to find a solution.
---------------------------------------------------------------------
Dear Ed,

this is an email from Germany, Munich.
I really enjoy your website since more than two years and I am visiting it weekly either to see if there are new puzzles and solutions or to go around in the old entries.
I now want to contribute to the Problem of approximating 7777777777... with powers of 2:
My idea is that you can accumulate smaller and smaller factors starting with 1.0... and by this it is possible to approach each sequence of digits in a number.
f.e. 2^  10  =  1.02400    *  10^3
      2^103  =  1.01412... * 10^31
      2^196  =  1.00434... * 10^59
If you are looking for the start 77....:
Start with 2^6 = 64 (as it is smaller than 77)
and multiply ongoing with 2^10, getting 65536, 67108..., 68719..., ..., 75557..., 77371....,
so 2^86 starts with 77.
And how do you get the small factors? The same way you get the other wanted digits: using the found factors and approach the number 100...

I have written a small program (pot2zahx.exe, compiled with dos-power-basic from pot2zahx.bas and sub-programs rechnenx.*) which supplies the search for powers of 2 resulting in the wanted sequence. 
When trying to get the mentioned result 2^40193336864 = 7.777777777996 * 10^12099400021 I found that the accuracy of my dos-program was bad for one digit. I had to invent my own computing with many digits. This is now already included in the program. I hope you can follow it, even if you don't understand German. You can also adjust the number of digits which are used for computing of the small factors by changing the input for the part 'RechIni2' and compiling again.
And I have included the program ‘rechnenx.exe’ which computes with many digits (variable).


As your are interested in approximations, I have found a good one for pi, which only uses 3 digits, but a lot of square-roots (=S):
S(S(S(S(S(S(S(S(S(S(7))))))))))^S(9!-S(S(4!)))  = 3.1415926 30829...
(It looks much nicer if you draw the square-root-signs.)
If you don't like so many square-roots, what about the following?
2+ 24th root of 24  =  3.1415 86441, where 24=4!, so you use only 3 digits: 2,4,4.


Anyway: I hope you enjoy somehow my findings ...If you want you can publish my dos-program.If you have got any questions, please don’t hesitate to ask.

Sincerely yours
Bodo ZinserEttenhoferstr. 2aD-81375 MunichBodoZinser@CosmoData.net