Finding $x$, the exponent of a $2^x$ when we need an specific output

Question

Say we need a program Findx[n_Integer, m_Integer] where n is an integer from 1 to 9 and m is an integer from 1 to 1000.

The output of the program is a number x, which is the exponent of 2 that generates a number starting with the number n, repeated m times.

Examples:

Findx[9,4] the output would be 13 301 because 2^13301 generates this big number that starts with four nines:

999936281703738626460116809416017800762 .... 742992557364341591351754752 with 4004 digits

Findx[9,10] the output would be 1 923 400 330 because 2^1923400330 generates this monstrous number that starts with ten nines:

99999999997213828437359271518597 ......... 12782767237949748583359053824 with

579001193 digits.

Answer 1

In the special case of 9's here is what you are looking for:

Findx9[m_] := Take[Numerator[Convergents[Log2[10], 2 m]], {1, -1, 2}]
Findx9[20]    

{3,93,485,13301,42039,254370,6107016,44699994,146964308,345060773,1923400330,496090320832,2809896217828,21404627947543,76610371662439,563875473494521,9279441562757101,100946106243339069,550563863556986329,1876500469327782617}

in this list 93 AND 485 return 99...
but you can get most of the numbers that you want

Anyway you can search your numbers in this list and get your results instantly!

here is the equation using your variables

Floor[10^(x*Log10[2] - 1 - Floor[x*Log10[2]] + m)] == FromDigits@Table[n, m]    

In the case Findx[9,4] this gives

Floor[10^(x*Log10[2] - 1 - Floor[x*Log10[2]] + 4)] == 9999    

you have to solve this equation for x

I'm not sure if mathematica can do this

In other words you are searching for the cases where
the Fractional Part of x*Log10[2] == 0.9999

Answer 2

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).