Necessidade de elaborar um algoritmo de processamento de números
https://stackoverflow.com/questions/2424215
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
me deparei com esta pergunta:
7 potência 7 é 823543. Que maior poder de 7 extremidades com 823.543?
Como devo ir sobre ele? O que eu vim com é muito lento, ele continua a multiplicar por 7 e verifica últimos 6 dígitos do resultado de um jogo.
Eu tentei com código de 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 soa como uma panela de pressão, mas não conseguiu obter a resposta: (
Solução
Multiply módulo 10 ^ 6. Veja este Lua código .
local x=1
for i=1,100000 do
x=(x*7) % 1e6
if x==823543 then print(i) end
end
Outras dicas
Você pode usar generalização de Euler de pouco de Fermat teorema que se aplicava ao seu caso diz que para qualquer número a que não é divisível por dois ou cinco ,
Pode haver menores poderes de 7, que também são igual a um módulo 10 ^ 6. Qualquer tal poder deve ser um divisor de 400000 Então, se você pesquisar todos os divisores de 400000 você deve encontrar a sua resposta.
solução de força bruta em Python:
def check():
i = 8
while True:
if str(7**i)[-6:] == "823543":
print i, 7**i
break
i += 1
if __name__ == "__main__":
check()
É executado em um pouco mais de 10 segundos em minha máquina:
$ time python 7\*\*7.py
5007 25461638709540284156782446957365168367138070393489656084508152816071765490828583739345420574947301301356529652113030016806506783009529977928336772622054260724106711204039012806363481521302203821096274017061906820115931889920385802499836705571461280700786627503189500663279772123190279763997339608040949194040289041117811256914511855302927500076094761237077649092849658261309060277197389760351907599243227298336309204635761799394324969277220810221310805265921431367291459357151617279190810954501590069774137519833706444943573459910208627100504003480684029216932299650285683013274883359754231186580602570771682084721896446416234857382909168309309630688331305154545352580787700878011742720440707156231891841057992434850068501355342227582074144717324718396296563918284728120322255330707786227631084119636101174217518654320128390401231343058708073280898554293777842571799775647325449392944570725467462072394864457569308219294304248413378339223195121800534783732295135735588409249690562213409520783181313960347723827308102920022860541043691808218543350580271593107019737918976365348051012746817678592727727988993175444584453532474156202438866838819565827414970029052602274354173178190323239427022953097424087683011937130778414189673555875258508014323428137406618951161046883845551087123412471364400737145434714864392224194773030522352601143771552489895838728148761974811275894561985163094852437703080985644653666048979901975905667811053289029958524703063742007291722490298429637413913574845245364780928447142275001431370017543206188428912106120676556219532197108435997375879569102044435752697298456147512203108094030745606163915437604076966518127099543894645297945324345093247636119593298654296614887389164509070158924404441687810434488061150620012547321097786493748417764592151734279632949607485719050349385098350202294648324398902047614892248381794929374952059877187100434970751833289677556040879755065563758085919673107576808662549999202791489324437408075089456174056904323973798979207791446889016369166632636035638123394649891606479407561222474471530411700646266636732205895085248823824764170316644547100628119484733814900100986786082211477261114056206393554335903410036064553032366200714266053598548735147707681592574886559888869327771461046450774938490837810526377213647071217152427693219479552580138352651791476758476864761332281826701978038126122728967682552206820425685782165630494478519812498630475776384700259524274670258777572341538755828794632819515842335609785884327007667337426644594091547392441314523035569100326662245947022517857248412004291423280879791576077952474202068318934524092750814844945529148131063116233331840380254781283689084385600858175504170157015630699919186013526052643206240745256569669847298952477441594748635701081031979500954081732722211598460098426985932512920424237248250698541558227081975966598720056015879151923686438360541128221854058867910136449528237543680180470919685862102358708465872395643586424250239281775923511452769821487580471289910257908740451431952197725174728917413539539795856895884961513784804247268727165303942024508367184898248006123651950710237279288601317817391869969699767431782664773248447758526620050588927086506013616563459173620496200348863132442180734592661348887012997849309740799709045762939781801481205704629203758859772476278892928066844445088880207986848424855774325574728566649552154520262460969975214802828263093097997124519153537792591659204109087699977445745067857471581656151077039286563447099850537157044829081400190710358959493358343935904669416958301921942118288210835104022359479660409954097409669785908666166908117346073702337825511531650740900904200220658196171839969860945908503151878488455004283026700303698398069644419655035582904253655945381261383285097911378914794161551292914993411444083214513058414480129560671193659591364146612550890288116403596333209446976453193340267725222134755872075133141618388704912211996423838163706006930973361661094103734887312836613195349528793780496172839376426055357343094188450140671138356505144988151110902047791487250988374130384058324229250761311655685931891857894126054047458969174494155762486464149775147410127618088224310828566286409277000561087588768230619606746804073498788244935099280434916850444895829823543
real 0m10.779s
user 0m10.709s
sys 0m0.024s
Não tanto uma resposta, mais uma dica:
Observe que o padrão de dígitos mais à direita de poderes de 7 vai 1,7,9,3,1,7,9,3,1,7, ... assim você só precisa gerar cada 4º poder de 7 de 3º. Um estudo mais aprofundado pode mostrar um padrão para os dois (três, quatro, ...) dígitos mais à direita, mas eu não fiz estudá-los para você.
Esteja preparado para alguns números muito grandes, Mathematica relatos de que a próxima potência de 7 com o procurado para dígitos mais à direita é o 5007.
que eu acho que responde a sua pergunta - uma abordagem mais rápida é para postar em SO e esperar por alguém para dizer-lhe a resposta! Você poderia até tentar Wolfram Alpha se você não faz como o algoritmo de SO.
abordagem pouco do Fermat teorema é um matematicamente sensata, e apenas a multiplicação repetidamente por 7 mod 10 ^ 6 é o código mais simples, mas há uma outra abordagem que você pode tomar que é computacionalmente eficiente (mas requer um código mais complexo). Em primeiro lugar, nota que, quando multiplicando por 7 a última dígitos depende apenas da última dígito antes (ou seja, estamos fazendo tudo mod 10). Nós multiplicar várias vezes por 7 para obter
7 (4)9 (6)3 (2)1 (0)7 ...
Ok, ótimo, por isso, se queremos a 3, que começam em 7 ^ 3 e sobem a cada 7 ^ 4 de lá. Agora, notamos que quando multiplicando por 7 ^ 4, os dois últimos dígitos dependem apenas os dois últimos dígitos de 7 ^ 4 e os dois últimos dígitos da resposta anterior. 7 ^ 4 é 2401. Então, na verdade a última dois dígitos será sempre o mesmo ao subir por 7 ^ 4.
E sobre os três últimos? Bem, 7 ^ 3 = 343 e 7 ^ 4 extremidades com 401, então mod 1000 nós começamos
343 543 743 943 143 343
Nós temos nossos três primeiros dígitos na coluna # 2 (543), e vemos que as repetições de seqüência sempre 5, de modo que devemos ir acima de lá por 7 ^ 20.
Podemos jogar este truque uma e outra vez: veja como muitas vezes o próximo bloco de dígitos repete, encontrar o subsequence direito dentro desse bloco, e em seguida, multiplicar-se não por 7, mas por 7 ^ n
.O que estamos realmente fazendo é encontrar um anel (multiplicativo) sobre o dígito m'th, e depois multiplicando os tamanhos de todos os anéis em conjunto para obter a extensão entre as potências sucessivas que têm os mesmos dígitos N se seguirmos este método. Aqui está algum código Scala (2.8.0 Beta1) que faz exatamente isso:
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))
}
Então, se nós encontramos um caso dos dígitos que nós queremos, agora podemos encontrar todos eles por encontrar o tamanho do anel apropriado. No nosso caso, com 6 dígitos (ou seja, mod 10 ^ 6) e base 7, encontramos um tamanho repetição de:
scala> interval(6,7)
res0: Long = 5000
Então, nós temos a nossa resposta! 7 ^ 7 é o primeiro, 7 ^ 5007 é o segundo, 7 ^ 10007 é a terceira, etc ..
Uma vez que este é genérica, podemos tentar outras respostas ... 11 ^ 11 = 285311670611 (um número de 8 dígitos). Vamos olhar o intervalo:
scala> interval(12,11)
res1: Long = 50000000000
Então, isso nos diz que 11 ^ 50000000007 é o próximo número depois de 11 ^ 11 com o mesmo conjunto inicial de 12 dígitos. Verifique com a mão se você está curioso!
Let também verificar com 3 ^ 3 - Qual é a próxima potência de 3 cuja decimal expansão extremidades com 27
scala> interval(2,3)
res2: Long = 20
Deve ser 3 ^ 23. Verificação:
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
Sim!
(código Switched em edições de usar BigInt para que pudesse lidar com números arbitrários de dígitos. O código não detecta casos degenerados, embora, por isso certifique-se de usar um principal para o poder ....)
Outra dica: você está interessado apenas nos últimos dígitos N: você pode executar cálculos módulo 10 ^ N e manter o ajuste resultado muito bem em um inteiro
