La necesidad de idear un algoritmo de cálculo de números

Question

Me topé con esta pregunta:

  

7 de potencia 7 es 823543. ¿Qué más alta potencia de 7 termina con 823.543?

¿Cómo debo hacerlo? El único que se me ocurrió es muy lento, sigue multiplicando por 7 y comprueba los últimos 6 dígitos del resultado de un partido.

He intentado con 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);}
            }

Y CPU suena como una olla a presión, pero no pudo obtener la respuesta: (

Answer 1

Multiply módulo 10 ^ 6. Ver este Lua código .

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

Answer 2

Se puede usar generalización de Euler de pequeño teorema de Fermat que se aplica a su caso dice que para cualquier número de a que no es divisible por dos o cinco , a a la potencia 400000 es igual a 1 modulo 10 ^ 6. Lo que significa que 7 ^ 400000 es igual a uno y 7 ^ 400007 es igual a 823.543 modulo 10 ^ 6

Puede haber potencias más pequeñas de 7 que también son igual a un módulo 10 ^ 6. Dicha alimentación debe ser un divisor de 400000. Por lo tanto, si usted busca todos los divisores de 400.000 que debe encontrar su respuesta.

Answer 3

solución de fuerza bruta en Python:

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

if __name__ == "__main__":
  check()

Se ejecuta en un poco más de 10 segundos en mi máquina:

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

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

Answer 4

No tanto una respuesta, más una pista:

Tenga en cuenta que el patrón de dígitos de la derecha de potencias de 7 va 1,7,9,3,1,7,9,3,1,7, ... por lo que sólo necesita generar cada cuarta potencia de 7 de la tercera. El estudio adicional podría mostrar un patrón para los dos (tres, cuatro, ...) dígitos de la derecha, pero no lo han hecho los estudió para usted.

Esté preparado para algunos números muy grandes, Mathematica informa que la siguiente potencia de 7 con la buscada dígitos de la derecha es la 5007a.

Lo que supongo que responda a su pregunta - un enfoque más rápido es escribir en el SO y esperar a que alguien le diga la respuesta! Usted podría incluso intentar Wolfram Alpha, si no te gusta el SO algoritmo.

Answer 5

poco enfoque teorema de Fermat es una forma matemática sensible, y justo mulitplying una y otra vez por 7 mod 10 ^ 6 es el código más simple, pero hay otro enfoque que podría tomar es computacionalmente eficiente (pero requiere un código más complejo). En primer lugar, tenga en cuenta que cuando se multiplican por 7 última dígitos depende sólo de la última dígito antes (es decir, estamos haciendo todo lo mod 10). Se multiplica repetidamente por 7 para obtener

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

Muy bien, muy bien, así que si queremos un 3, empezamos a las 7 ^ 3 y subir cada 7 ^ 4 a partir de ahí. Ahora, observamos que al multiplicar por 7 ^ 4, los dos últimos dígitos dependen sólo de los dos últimos dígitos de 7 ^ 4 y los dos últimos dígitos de la respuesta anterior. 7 ^ 4 es 2401. Así que, de hecho, la última dos dígitos siempre será el mismo al subir un 7 ^ 4.

¿Qué hay de los tres últimos? Bueno, 7 ^ 3 = 343 y 7 ^ 4 termina con 401, de modo mod 1000 obtenemos

343 543 743 943 143 343

Tenemos nuestros primeros tres dígitos en la columna # 2 (543), y vemos que la secuencia se repite cada vez el 5, por lo que hemos de subir desde allí por 7 ^ 20.

Podemos jugar este truco una y otra vez: encontrar la frecuencia con el siguiente bloque de repeticiones dígitos, encontrar la subsecuencia derecha dentro de ese bloque, y luego multiplicar por no por 7, pero por 7 ^ n

.

Lo que estamos haciendo en realidad es encontrar un anillo (multiplicativo) sobre el dígito m'th, y luego multiplicando los tamaños de todos los anillos juntos para conseguir el lapso entre las sucesivas potencias que tienen los mismos dígitos N si seguimos este método. Aquí hay un código Scala (2.8.0 Beta 1) que hace precisamente esto:

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))
}

Por lo tanto, si hemos encontrado un caso de los dígitos que queremos, ahora podemos encontrar todos ellos por encontrar el tamaño del anillo apropiado. En nuestro caso, con 6 dígitos (es decir, mod 10 ^ 6) y la base 7, nos encontramos con un tamaño de repetición:

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

Por lo tanto, tenemos nuestra respuesta! 7 ^ 7 es la primera, 7 ^ 5007 es el segundo, 7 ^ 10007 es la tercera, etc ..

Dado que este es genérico, podemos tratar otras respuestas ... 11 ^ 11 = 285 311 670 611 (un número de 8 dígitos). Veamos el intervalo:

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

Por lo tanto, esto nos dice que 11 ^ 50000000007 es el número siguiente después de 11 ^ 11 con el mismo conjunto inicial de 12 dígitos. Compruebe con la mano si usted es curioso!

También vamos a comprobar con 3 ^ 3 - ¿cuál es la siguiente potencia de 3 cuya expansión decimal termina con 27

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

debe ser de 3 ^ 23. Comprobación:

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

Sí

---

(código conmutada en las ediciones de usar Bigint por lo que podía manejar un número arbitrario de dígitos. El código no detecta casos degenerados, aunque, por lo que asegúrese de usar un número primo para el poder ....)

Answer 6

Otra pista: Usted sólo está interesado en los últimos dígitos N: se puede realizar cálculos modulo 10 ^ N y mantener el resultado encajan muy bien en un entero