Necessità di elaborare un algoritmo numero macinare
-
19-09-2019 - |
Domanda
Mi sono imbattuto in questa domanda:
7 Potenza 7 è 823543. Quale maggiore potenza di 7 si chiude con 823.543?
Come devo fare? Quello che mi è venuta è molto lenta, continua a moltiplicare per 7 e controlla le ultime 6 cifre del risultato di una partita.
Ho provato con il codice di Lou:
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);}
}
E CPU suona come una pentola a pressione, ma non ha potuto ottenere la risposta: (
Soluzione
Moltiplicare modulo 10 ^ 6. Vedere questo Lua .
local x=1
for i=1,100000 do
x=(x*7) % 1e6
if x==823543 then print(i) end
end
Altri suggerimenti
Si potrebbe utilizzare generalizzazione di Eulero di piccolo teorema di Fermat, che applicata al vostro caso dice che per qualsiasi numero a che non è divisibile per due o cinque , un alla potenza 400000 è uguale a 1 modulo 10 ^ 6. Il che significa che il 7 ^ 400000 è uguale a uno e 7 ^ 400007 è pari a 823543 modulo 10 ^ 6
Ci possono essere piccole potenze di 7 che sono anche pari ad un modulo 10 ^ 6. Qualsiasi tale potere dovrebbe essere un divisore di 400000 Quindi, se si cerca tutti i divisori di 400.000 si dovrebbe trovare la risposta.
soluzione di forza bruta 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()
viene eseguito in un po 'più di 10 secondi sulla mia macchina:
$ time python 7\*\*7.py
5007 25461638709540284156782446957365168367138070393489656084508152816071765490828583739345420574947301301356529652113030016806506783009529977928336772622054260724106711204039012806363481521302203821096274017061906820115931889920385802499836705571461280700786627503189500663279772123190279763997339608040949194040289041117811256914511855302927500076094761237077649092849658261309060277197389760351907599243227298336309204635761799394324969277220810221310805265921431367291459357151617279190810954501590069774137519833706444943573459910208627100504003480684029216932299650285683013274883359754231186580602570771682084721896446416234857382909168309309630688331305154545352580787700878011742720440707156231891841057992434850068501355342227582074144717324718396296563918284728120322255330707786227631084119636101174217518654320128390401231343058708073280898554293777842571799775647325449392944570725467462072394864457569308219294304248413378339223195121800534783732295135735588409249690562213409520783181313960347723827308102920022860541043691808218543350580271593107019737918976365348051012746817678592727727988993175444584453532474156202438866838819565827414970029052602274354173178190323239427022953097424087683011937130778414189673555875258508014323428137406618951161046883845551087123412471364400737145434714864392224194773030522352601143771552489895838728148761974811275894561985163094852437703080985644653666048979901975905667811053289029958524703063742007291722490298429637413913574845245364780928447142275001431370017543206188428912106120676556219532197108435997375879569102044435752697298456147512203108094030745606163915437604076966518127099543894645297945324345093247636119593298654296614887389164509070158924404441687810434488061150620012547321097786493748417764592151734279632949607485719050349385098350202294648324398902047614892248381794929374952059877187100434970751833289677556040879755065563758085919673107576808662549999202791489324437408075089456174056904323973798979207791446889016369166632636035638123394649891606479407561222474471530411700646266636732205895085248823824764170316644547100628119484733814900100986786082211477261114056206393554335903410036064553032366200714266053598548735147707681592574886559888869327771461046450774938490837810526377213647071217152427693219479552580138352651791476758476864761332281826701978038126122728967682552206820425685782165630494478519812498630475776384700259524274670258777572341538755828794632819515842335609785884327007667337426644594091547392441314523035569100326662245947022517857248412004291423280879791576077952474202068318934524092750814844945529148131063116233331840380254781283689084385600858175504170157015630699919186013526052643206240745256569669847298952477441594748635701081031979500954081732722211598460098426985932512920424237248250698541558227081975966598720056015879151923686438360541128221854058867910136449528237543680180470919685862102358708465872395643586424250239281775923511452769821487580471289910257908740451431952197725174728917413539539795856895884961513784804247268727165303942024508367184898248006123651950710237279288601317817391869969699767431782664773248447758526620050588927086506013616563459173620496200348863132442180734592661348887012997849309740799709045762939781801481205704629203758859772476278892928066844445088880207986848424855774325574728566649552154520262460969975214802828263093097997124519153537792591659204109087699977445745067857471581656151077039286563447099850537157044829081400190710358959493358343935904669416958301921942118288210835104022359479660409954097409669785908666166908117346073702337825511531650740900904200220658196171839969860945908503151878488455004283026700303698398069644419655035582904253655945381261383285097911378914794161551292914993411444083214513058414480129560671193659591364146612550890288116403596333209446976453193340267725222134755872075133141618388704912211996423838163706006930973361661094103734887312836613195349528793780496172839376426055357343094188450140671138356505144988151110902047791487250988374130384058324229250761311655685931891857894126054047458969174494155762486464149775147410127618088224310828566286409277000561087588768230619606746804073498788244935099280434916850444895829823543
real 0m10.779s
user 0m10.709s
sys 0m0.024s
Non tanto una risposta, più un suggerimento:
Si noti che il modello di cifre più a destra di potenze di 7 va 1,7,9,3,1,7,9,3,1,7, ... in modo che solo bisogno di generare ogni 4 di potenza di 7 da il 3 °. Ulteriore studio potrebbe mostrare un modello per i due (tre, quattro, ...) più a destra le cifre, ma non ho fatto li studiate per voi.
Essere preparati per alcuni numeri molto grandi, Mathematica riporta che la prossima potenza di 7 con l'ambito per le cifre più a destra è il 5007i.
che immagino risponde alla tua domanda - un approccio più veloce è quello di scrivere un commento sul SO e aspettare che qualcuno di dirvi la risposta! Si potrebbe anche provare Wolfram Alpha, se non ti piace il SO algoritmo.
po approccio Il teorema di Fermat è una matematicamente sensibile, e solo mulitplying più e più volte da 7 mod 10 ^ 6 è il codice più semplice, ma c'è un altro approccio si potrebbe prendere che è computazionalmente efficiente (ma richiede codice più complesso). In primo luogo, si noti che quando moltiplicando per 7 ultima cifre dipende solo dalla ultima cifra prima (vale a dire che stiamo facendo tutto il mod 10). Moltiplichiamo più volte dal 7 per ottenere
7 (4)9 (6)3 (2)1 (0)7 ...
Ok, fantastico, quindi se vogliamo un 3, si parte alle 7 ^ 3 e andare ogni 7 ^ 4 da lì. Ora, notiamo che quando moltiplicando per 7 ^ 4, le ultime due cifre dipendono solo le ultime due cifre di 7 ^ 4 e le ultime due cifre della risposta precedente. 7 ^ 4 è 2401. Quindi, in realtà l'ultima due cifre sarà sempre lo stesso quando si va dai 7 ^ 4.
Che dire gli ultimi tre? Beh, 7 ^ 3 = 343 e 7 ^ 4 si conclude con 401, quindi mod 1000 otteniamo
343 543 743 943 143 343
Abbiamo le nostre prime tre cifre nella colonna # 2 (543), e si vede che la sequenza si ripete mai 5, quindi dovremmo salire da lì in 7 ^ 20.
Possiamo giocare questo trucco più e più volte: scopri come spesso il successivo blocco di ripetizioni cifre, trovare la sottosequenza destra all'interno di quel blocco, e quindi moltiplicare per non del 7, ma da 7 ^ n
.Quello che stiamo facendo veramente è trovare un anello (moltiplicativo) sopra la cifra m'th, e quindi moltiplicando le dimensioni di tutti gli anelli insieme per ottenere l'intervallo tra le potenze successive che hanno gli stessi N cifre se seguiamo questo metodo. Ecco alcuni codice Scala (2.8.0 Beta1) che fa proprio questo:
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))
}
Quindi, se abbiamo trovato una caso delle cifre che vogliamo, possiamo ora trovare tutti loro trovando la dimensione del ring appropriata. Nel nostro caso, a 6 cifre (vale a dire mod 10 ^ 6) e la base 7, troviamo un repeat dimensione di:
scala> interval(6,7)
res0: Long = 5000
Quindi, abbiamo la nostra risposta! 7 ^ 7 è il primo, 7 ^ 5007 è il secondo, 7 ^ 10007 è il terzo, ecc ..
Dal momento che questo è generico, possiamo provare altre risposte ... 11 ^ 11 = 285.311.670.611 (un numero di 8 cifre). Diamo un'occhiata a l'intervallo:
scala> interval(12,11)
res1: Long = 50000000000
Quindi, questo ci dice che l'11 ^ 50.000.000 mila sette è il numero successivo dopo l'11 ^ 11 con lo stesso set iniziale di 12 cifre. Controllare a mano se siete curiosi!
Diamo un'occhiata anche con 3 ^ 3 -? Qual è la prossima potenza di 3 la cui espansione decimale termina con 27
scala> interval(2,3)
res2: Long = 20
Dovrebbe essere 3 ^ 23. Controllo:
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!
(codice Switched a modifiche da usare BigInt quindi è in grado di gestire un numero arbitrario di cifre. Il codice non rileva casi degeneri, però, in modo da assicurarsi di utilizzare un numero primo per il potere ....)
Un altro suggerimento: Siete interessati solo negli ultimi N cifre: è possibile eseguire calcoli Modulo 10 ^ N e mantenere il risultato misura piacevolmente in un intero