This is a bit fiddly but the idea is on track. One multiplies the relevant logs (base 2) by a relatively large integer, creates and reduces a certain lattice, and then does some integer linear programming to obtain a suitable combination.
The tricky part is getting the size constraint so that the result actually is smallest and also gives a value that begins with (at least) the correct number of n's.
find2Power[n_Integer, m_Integer] :=
Module[{digits = FromDigits[ConstantArray[n, m]], col1, lat, redlat,
c, vars, lpolys, constraints},
col1 = Round[10^(2*m)*Log[2, {digits, 10, 2}]];
lat = Transpose[Join[{col1}, IdentityMatrix[3]]];
redlat = LatticeReduce[lat];
vars = Array[c, 3];
lpolys = ({-1, 1, 1}*vars).redlat;
constraints = {lpolys[[4]] <= -1,
lpolys[[3]] >= 1, -10^(m) - 10^(m - 1) <= lpolys[[1]] <= -1,
lpolys[[2]] == 1};
NMaximize[{lpolys[[4]], constraints}, vars, Integers]]
The two given examples work. But that's about all I can guarantee.
find2Power[9, 4]
(* Out[13]= {13301., {c$2472[1] -> 9, c$2472[2] -> 8, c$2472[3] -> 8}} *)
find2Power[9, 10]
(* Out[14]= {1.92340033*10^9, {c$2481[1] -> 969, c$2481[2] -> 1,
c$2481[3] -> 19}} *)
Also it is not obvious how to recover the right integer once we exceed machine precision.
This could instead be done exactly using Minimize
but then the speed becomes an issue in some cases where NMinimize
remains fast.
I skimped on the explanation because it should be obvious how it works (read: I only barely even managed to make it work, and I'm not sure I could explain it if I tried).