6
$\begingroup$

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.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Any attempts? Any background or research for a general solution? Notice you didn't even ask a question. $\endgroup$ – Kuba♦ Nov 7 '18 at 14:14
  • $\begingroup$ Yes I did, and it was with brute force attack to the problem. I am wondering whether there is a simple solution. I found easily the exponent for small number of nines and then I tried to find a pattern and if I could fit a curve in it. But it was time consuming and went nowhere. $\endgroup$ – Giorgio Nov 7 '18 at 14:39
  • 1
    $\begingroup$ Seems interesting. But as @Kuba noted, you should show what you did. $\endgroup$ – Daniel Lichtblau Nov 7 '18 at 15:05
6
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ Exactly. As the number of 9 increases, the difficulty goes up. I could never find x when n=9 and m=9, but I could find x when n=9 and m=10 and m=8, m=7, m=6, m= 5, m=4, m=3 and m=2 $\endgroup$ – Giorgio Nov 7 '18 at 20:07
  • $\begingroup$ Good start... (I upvoted for that alone) $\endgroup$ – Daniel Lichtblau Nov 7 '18 at 20:12
  • $\begingroup$ @Giorgio please see the new edit I made $\endgroup$ – J42161217 Nov 7 '18 at 22:41
  • $\begingroup$ Thanks for the effort, but the list you produced is not the exponent of 2 that produces a number starting with certain number of nines. There are some coincidences but they are not in the right sequence. The correct numbers are: 53, 93, 2621, 13301, 254370, 5781869, 38267831 and 146964308 respectively that produce numbers starting from one nine up to 8 nines. The exponent for 9 nines I could not find until today. Another number is 1 923 400 330 which when used as the exponent of 2 produces a huge number starting with ten nines. $\endgroup$ – Giorgio Nov 8 '18 at 17:43
  • $\begingroup$ I never said I found all the numbers of the sequence, but finding a formula that produces instantly and accurately more than half of these numbers was a big surprise for me. In number theory you can see crazy stuff happen and they are not just coincidences. If you want to find super-records for your list you only have to search a tiny amount of the numbers that this formula produces. you can find around 1000 9's by just testing 2-3 huge numbers... $\endgroup$ – J42161217 Nov 8 '18 at 21:51
4
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ Wow that is great! I will try it. $\endgroup$ – Giorgio Nov 8 '18 at 14:50
  • $\begingroup$ find2Power[9, 10] returns 3846800660... $\endgroup$ – J42161217 Nov 8 '18 at 21:55
  • $\begingroup$ @J42161217 Sorry, I had changed an inequality and used the wrong version. Still not sure edited version is correct but it allows another digit of slop. $\endgroup$ – Daniel Lichtblau Nov 8 '18 at 22:00
  • $\begingroup$ @DanielLichtblau yes, it's ok now $\endgroup$ – J42161217 Nov 8 '18 at 22:02
  • $\begingroup$ @J42161217 find2Power[9,9] returned 5 770 200 990 which gives 10 nines, which is not wrong per se, but I could not find an exponent who gives exactly 9 nines. I will report today what I have found so far. $\endgroup$ – Giorgio Nov 9 '18 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.