Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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