Need to devise a number crunching algorithm_问答_开发者

I stumbled upon this question:

7 power 7 is 823543. Which higher power of 7 ends with 823543 ?

How should I go about it ? The one I came up with is very slow, it keeps on multiplying by 7 and checks last 6 digits of the result for a match.

I tried with Lou's code:

int x=1;
    for (int i=3;i<=100000000;i=i+4){
            x=(x*7)%1000000;
            System.out.println("i="+ i+" x= "+x);
            if (x==823543){
         开发者_运维知识库       System.out.println("Ans "+i);}
            }

And CPU sounds like a pressure cooker but couldn't get the answer :(

Multiply modulo 10^6. See this Lua code.

local x=1
for i=1,100000 do
        x=(x*7) % 1e6
        if x==823543 then print(i) end
end

You could use Euler's generalization of Fermat's little theorem which applied to your case says that for any number a that is not divisible by two or five, a to the power 400000 is equal to 1 modulo 10^6. Which means that 7^400000 is equal to one and 7^400007 is equal to 823543 modulo 10^6

There may be smaller powers of 7 that are also equal to one modulo 10^6. Any such power should be a divisor of 400000. So if you search all divisors of 400000 you should find your answer.

Brute-force solution in Python:

def check():
    i = 8
    while True:
        if str(7**i)[-6:] == "823543":
            print i, 7**i
            break
        i += 1

if __name__ == "__main__":
  check()

Runs in a tad more then 10 seconds on my machine:

$ time python 7\*\*7.py 
5007 25461638709540284156782446957365168367138070393489656084508152816071765490828583739345420574947301301356529652113030016806506783009529977928336772622054260724106711204039012806363481521302203821096274017061906820115931889920385802499836705571461280700786627503189500663279772123190279763997339608040949194040289041117811256914511855302927500076094761237077649092849658261309060277197389760351907599243227298336309204635761799394324969277220810221310805265921431367291459357151617279190810954501590069774137519833706444943573459910208627100504003480684029216932299650285683013274883359754231186580602570771682084721896446416234857382909168309309630688331305154545352580787700878011742720440707156231891841057992434850068501355342227582074144717324718396296563918284728120322255330707786227631084119636101174217518654320128390401231343058708073280898554293777842571799775647325449392944570725467462072394864457569308219294304248413378339223195121800534783732295135735588409249690562213409520783181313960347723827308102920022860541043691808218543350580271593107019737918976365348051012746817678592727727988993175444584453532474156202438866838819565827414970029052602274354173178190323239427022953097424087683011937130778414189673555875258508014323428137406618951161046883845551087123412471364400737145434714864392224194773030522352601143771552489895838728148761974811275894561985163094852437703080985644653666048979901975905667811053289029958524703063742007291722490298429637413913574845245364780928447142275001431370017543206188428912106120676556219532197108435997375879569102044435752697298456147512203108094030745606163915437604076966518127099543894645297945324345093247636119593298654296614887389164509070158924404441687810434488061150620012547321097786493748417764592151734279632949607485719050349385098350202294648324398902047614892248381794929374952059877187100434970751833289677556040879755065563758085919673107576808662549999202791489324437408075089456174056904323973798979207791446889016369166632636035638123394649891606479407561222474471530411700646266636732205895085248823824764170316644547100628119484733814900100986786082211477261114056206393554335903410036064553032366200714266053598548735147707681592574886559888869327771461046450774938490837810526377213647071217152427693219479552580138352651791476758476864761332281826701978038126122728967682552206820425685782165630494478519812498630475776384700259524274670258777572341538755828794632819515842335609785884327007667337426644594091547392441314523035569100326662245947022517857248412004291423280879791576077952474202068318934524092750814844945529148131063116233331840380254781283689084385600858175504170157015630699919186013526052643206240745256569669847298952477441594748635701081031979500954081732722211598460098426985932512920424237248250698541558227081975966598720056015879151923686438360541128221854058867910136449528237543680180470919685862102358708465872395643586424250239281775923511452769821487580471289910257908740451431952197725174728917413539539795856895884961513784804247268727165303942024508367184898248006123651950710237279288601317817391869969699767431782664773248447758526620050588927086506013616563459173620496200348863132442180734592661348887012997849309740799709045762939781801481205704629203758859772476278892928066844445088880207986848424855774325574728566649552154520262460969975214802828263093097997124519153537792591659204109087699977445745067857471581656151077039286563447099850537157044829081400190710358959493358343935904669416958301921942118288210835104022359479660409954097409669785908666166908117346073702337825511531650740900904200220658196171839969860945908503151878488455004283026700303698398069644419655035582904253655945381261383285097911378914794161551292914993411444083214513058414480129560671193659591364146612550890288116403596333209446976453193340267725222134755872075133141618388704912211996423838163706006930973361661094103734887312836613195349528793780496172839376426055357343094188450140671138356505144988151110902047791487250988374130384058324229250761311655685931891857894126054047458969174494155762486464149775147410127618088224310828566286409277000561087588768230619606746804073498788244935099280434916850444895829823543

real    0m10.779s
user    0m10.709s
sys 0m0.024s

Not so much an answer, more a hint:

Observe that the pattern of rightmost digits of powers of 7 goes 1,7,9,3,1,7,9,3,1,7,... so you only need to generate every 4th power of 7 from the 3rd. Further study might show a pattern for the two (three, four, ...) rightmost digits, but I haven't done studied them for you.

Be prepared for some very large numbers, Mathematica reports that the next power of 7 with the sought-for rightmost digits is the 5007th.

Which I guess answers your question -- a faster approach is to post on SO and wait for someone to tell you the answer ! You could even try Wolfram Alpha if you don't like the SO algorithm.

The Fermat's little theorem approach is a mathematically sensible one, and just mulitplying over and over by 7 mod 10^6 is the simplest code, but there's another approach you could take that is computationally efficient (but requires more complex code). First, note that when multiplying by 7 the last digit depends only on the last digit before (i.e. we're doing everything mod 10). We multiply repeatedly by 7 to get

7  (4)9  (6)3  (2)1 (0)7 ...

Okay, great, so if we want a 3, we start at 7^3 and go up every 7^4 from there. Now, we note that when multiplying by 7^4, the last two digits depend only on the last two digits of 7^4 and the last two digits of the previous answer. 7^4 is 2401. So in fact the last two digits will always be the same when going up by 7^4.

What about the last three? Well, 7^3 = 343 and 7^4 ends with 401, so mod 1000 we get

343 543 743 943 143 343

We've got our first three digits in column #2 (543), and we see that the the sequence repeats ever 5, so we should go up from there by 7^20.

We can play this trick over and over again: find how often the next block of digits repeats, find the right subsequence within that block, and then multiply up not by 7 but by 7^n.

What we're really doing is finding a (multiplicative) ring over the m'th digit, and then multiplying the sizes of all the rings together to get the span between successive powers that have the same N digits if we follow this method. Here's some Scala code (2.8.0 Beta1) that does just this:

def powRing(bigmod: BigInt, checkmod: BigInt, mul: BigInt) = {
  val powers = Stream.iterate(1:BigInt)(i => (i*mul)%bigmod)
  powers.take( 2+powers.tail.indexWhere(_ % checkmod == 1) ).toList
}
def ringSeq(digits: Int, mod: BigInt, mul: BigInt): List[(BigInt,List[BigInt])] = {
  if (digits<=1) List( (10:BigInt , powRing(mod,10,mul)) )
  else {
    val prevSeq = ringSeq(digits-1, mod, mul)
    val prevRing = prevSeq.head
    val nextRing = powRing(mod,prevRing._1*10,prevRing._2.last)
    (prevRing._1*10 , nextRing) :: prevSeq
  }
}
def interval(digits: Int, mul: Int) = {
  val ring = ringSeq(digits, List.fill(digits)(10:BigInt).reduceLeft(_*_), mul)
  (1L /: ring)((p,r) => p * (r._2.length-1))
}

So, if we've found one case of the digits that we want, we can now find all of them by finding the size of the appropriate ring. In our case, with 6 digits (i.e. mod 10^6) and base 7, we find a repeat size of:

scala> interval(6,7)                                                           
res0: Long = 5000

So, we've got our answer! 7^7 is the first, 7^5007 is the second, 7^10007 is the third, etc..

Since this is generic, we can try other answers...11^11 = 285311670611 (an 8 digit number). Let's look at the interval:

scala> interval(12,11)            
res1: Long = 50000000000

So, this tells us that 11^50000000007 is the next number after 11^11 with the same initial set of 12 digits. Check by hand if you're curious!

Let's also check with 3^3--what's the next power of 3 whose decimal expansion ends with 27?

scala> interval(2,3)
res2: Long = 20

Should be 3^23. Checking:

scala> List.fill(23)(3L).reduceLeft((l,r) => {println(l*r) ; l*r})
9
27
81
243
729
2187
6561
19683
59049
177147
531441
1594323
4782969
14348907
43046721
129140163
387420489
1162261467
3486784401
10460353203
31381059609
94143178827

Yup!

(Switched code in edits to use BigInt so it could handle arbitrary numbers of digits. The code doesn't detect degenerate cases, though, so make sure you use a prime for the power....)

Another hint: You are only interested in the last N digits: you can perform calculations modulo 10^N and keep the result fit nicely into an integer