# How does FindInstance work?

I was asked a question one day: find an integer n such that the first five digits of 5*7^n is 12345. It's very nice that I can quickly write code like this:

Block[{n=1,x=5},
While[RealDigits[x=7.*x][[1,;;5]]!={1,2,3,4,5},n++];
n]//Timing

{55.86399999999998,456370}


It takes less than a minute. Later, I found that using the function FindInstance I could find a solution in much less time (but not the minimal solution):

FindInstance[{m+Log[10,1.2345]<Log[10,5.]+n Log[10,7.]<m+Log[10,1.2346],n>0},{m,n},Integers]//Timing

{0.3119999999999869,{{m->12872681,n->15232174}}}


Furthermore, I modified the code to be able to find the minimal solution like this:

 NestWhileList[
n/.FindInstance[{m+Log[10,1.2345]<Log[10,5.]+n Log[10,7.]<m+Log[10,1.2346],First@#>n>0},{m,n},Integers]&,
n/.FindInstance[{m+Log[10,1.2345]<Log[10,5.]+n Log[10,7.]<m+Log[10,1.2346],n>0},{m,n},Integers],
#!={}&]//Timing

{11.872000000000007,{{15232174},{15188314},{10277666},{5410878},{2955299},{499720},
{497170},{496660},{496150},{494620},{493090},{492580},{492070},{490540},{490030},{489520},{489010},{478300},{456370},n}}


The time it takes is one fifth of that classic method. So, I found a new way to solve this class of questions (just in Mathematica)? My question is, can this method be used for other questions, and which mathematical method does the function FindInstance exactly use?

-

I think FindInstance isn't very fast but sequental evaluation with While is very slow. Of course, FindInstance use some optimization. However, I can optimize even more

Pick[#, UnitStep[
Log[10, 1.2346/1.2345] -
FractionalPart[Log[10, 5./1.2345] + # Log[10, 7.]]], 1] &@
Range[1000000] // AbsoluteTiming


{0.051233, {456370, 456880, 457390, 457900, 458410, 458920, 459430, 459940, 460450, 460960, 461470, 461980, 462490, 463000, 463510, 464020, 464530, 465040, 465550, 466060, 466570, 467080, 467590, 468100, 468610, 469120, 469630, 470140, 470650, 471160, 471670, 472180, 472690, 473200, 473710, 474220, 474730, 475240, 475750, 476260, 476770, 477280, 477790, 478300, 478810, 479320, 479830, 480340, 480850, 481360, 481870, 482380, 482890, 483400, 483910, 484420, 484930, 485440, 485950, 486460, 486970, 487480, 487990, 488500, 489010, 489520, 490030, 490540, 491050, 491560, 492070, 492580, 493090, 493600, 494110, 494620, 495130, 495640, 496150, 496660, 497170, 497680, 498190, 498700, 499210, 499720}}

It test first 1000000 values of n. For comparison the approach with While takes 12 sec on my machine.

-
Thank you very much for your answer! Could you explain in brief why your code works so fast ( or why mine is slow )? Is there any aritifice to do with this class of questions? –  pencil Sep 26 '13 at 14:00
@pencil This method works fast because it operates with packed arrays. FindInstance use unknown proprietary algorithm. Perhaps it is slower because it find pair of tho integers (n,m) instead of one integer. –  ybeltukov Sep 27 '13 at 15:50