Необходимо разработать ряд хруст алгоритм

Question

я наткнулся на этот вопрос:

7 мощность 7 является 823543. Какой выше мощность 7 заканчивается 823543?

Как мне это сделать? Тот, который я придумал, очень медленный, он продолжает умножаться на 7 и проверяет последние 6 цифр результата для соответствия.

Я попытался с кодом Лу:

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

И CPU звучит как скороварка, но не мог получить ответ :(

Answer 1

Умножение по модулю 10^6 см это Lua code

..

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

Answer 2

не столько ответ, еще подсказка:

Obser что образец крайних правых цифр степеней 7 равен 1,7,9,3,1,7,9,3,1,7, ... поэтому вам нужно всего лишь генерировать каждую 4-ю степень 7 от 3-го. Дальнейшее исследование может показать образец для двух (три, четыре, ...) самых правых цифр, но я не изучил их для вас.

Будьте готовы к некоторым очень большим количествам, Mathematica сообщает, что следующая мощность 7 с искомыми самыми правыми цифрами составляет 5007-й.

Который, я думаю, отвечает на ваш вопрос - более быстрый подход заключается в том, чтобы публиковать сообщения на SO и ждать, пока кто-то скажет вам ответ! Вы даже можете попробовать Wolfram Alpha, если вам не нравится алгоритм SO.

Answer 3

Другой намек: Вы заинтересованы только в последние N цифр: вы можете выполнять вычисления по модулю 10^N и сохранить результат вписывались целое

Answer 4

Вы можете использовать Euler's generalization из Fermat's little theorem, которые применяются к вашему делу говорит что для любого числа a, которое не делится на два или пять, a на мощность 400000 равно 1 по модулю 10^6. Это означает, что 7^400000 равно единице и 7^400007 равно 823543 по модулю 10^6

Могут быть меньшие степени 7, которые также равны по модулю 10^6. Любая такая мощность должна быть делителем 400000. Поэтому, если вы ищете все делители 400000, вы должны найти свой ответ.

Answer 5

решение перебором в Python:

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

if __name__ == "__main__": 
    check() 

Запускается в чуть более чем за 10 секунд на моей машине:

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

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

Answer 6

малая теорема подход Ферма является математически осмысленная один, и только mulitplying снова и снова 7 mod 10^6 - простейший код, но есть другой подход, который вы могли бы принять, что является вычислительно эффективным (но требует более сложного кода). Во-первых, обратите внимание, что при умножении на 7 цифра последней зависит только от цифры последней цифры (т. Е. Мы делаем все mod 10).Умножим раз на 7, чтобы получить

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

Хорошо, отлично, так что если мы хотим 3, мы начинаем в 7^3 и идти каждый 7^4 оттуда. Теперь заметим, что при умножении на 7^4 последние две цифры зависят только от двух последних цифр 7^4 и двух последних цифр предыдущего ответа. 7^4 - 2401. Таким образом, последние цифры всегда будут одинаковыми при увеличении на 7^4.

Как насчет последних трех? Ну, 7^3 = 343 и 7^4 заканчивается 401, поэтому мода 1000 мы получаем

343 543 743 943 143 343 

Мы получили наши первые три цифры в колонке # 2 (543), и мы видим, что последовательность повторяется 5 раз, поэтому мы должны подняться оттуда на 7:20.

Мы можем повторять этот трюк снова и снова: найдите, как часто повторяется следующий блок цифр, найдите нужную подпоследовательность внутри этого блока, а затем умножьте не на 7, а на 7^n.

То, что мы действительно делаем, это найти (мультипликативное) кольцо над меткой m'th, а затем умножить размеры всех колец вместе, чтобы получить промежуток между последовательными степенями, которые имеют одинаковые N цифр, если мы последуем Этот метод. Вот некоторые Scala код (2.8.0 Beta1), что делает именно это:

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

Таким образом, если мы нашли один случай цифр, которые мы хотим, мы можем теперь найти их все, находя размер соответствующего кольца. В нашем случае, с 6 цифр (то есть по модулю 10^6) и основания 7, мы находим размер повтора:

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

Итак, мы получили наш ответ! 7^7 является первым, 7^5007 - вторым, 7^10007 - третьим и т. Д.

Поскольку это общее, мы можем попробовать другие ответы ... 11^11 = 285311670611 (8-значный номер). Давайте посмотрим на интервале:

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

Таким образом, это говорит о том, что 11^50000000007 является следующее число после 11^11 с тем же начальным набором из 12 цифр. Проверьте вручную, если вам интересно!

Давайте также проверить с помощью 3^3 - какова следующая мощность 3, десятичное расширение которой заканчивается на 27?

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

Должно быть 3^23. Проверка:

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 код в правках использовать BigInt поэтому он может обрабатывать произвольные числа цифр. Код не обнаруживает вырожденные случаи, хотя, поэтому убедитесь, что вы используете штрих для власти ....)