숫자 분석 알고리즘 고안 필요

StackOverflow https://stackoverflow.com/questions/2424215

  •  19-09-2019
  •  | 
  •  

문제

나는 이런 질문을 우연히 발견했습니다.

7제곱 7은 823543입니다.7의 거듭제곱이 823543으로 끝나는 것은 무엇입니까?

어떻게 해야 합니까?제가 생각해낸 것은 매우 느립니다. 계속해서 7을 곱하고 결과의 마지막 6자리 숫자를 확인하여 일치하는지 확인합니다.

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

그리고 CPU는 압력솥처럼 들리지만 대답을 얻을 수 없습니다 :(

도움이 되었습니까?

해결책

모듈로 10^6을 곱하십시오. 이것 좀 봐 루아 코드.

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

다른 팁

당신은 사용할 수 있습니다 Euler의 일반화 의 Fermat의 작은 정리 귀하의 사건에 적용한 것은 모든 번호에 대해 ㅏ 그것은 2 ~ 5 명으로 나눌 수 없습니다. ㅏ 전원 400000은 1 모듈로 10^6과 같습니다. 즉, 7^400000은 1과 7^400007이 823543 Modulo 10^6과 같음을 의미합니다.

하나의 모듈로 10^6과 같은 7의 더 작은 전력이있을 수 있습니다. 그러한 전력은 400000의 제수가되어야합니다. 따라서 400000의 모든 제수를 검색하면 답을 찾아야합니다.

파이썬의 무차별 용액 :

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 25461638709540284156782446957365168367138070393489656084508152816071765490828583739345420574947301301356529652113030016806506783009529977928336772622054260724106711204039012806363481521302203821096274017061906820115931889920385802499836705571461280700786627503189500663279772123190279763997339608040949194040289041117811256914511855302927500076094761237077649092849658261309060277197389760351907599243227298336309204635761799394324969277220810221310805265921431367291459357151617279190810954501590069774137519833706444943573459910208627100504003480684029216932299650285683013274883359754231186580602570771682084721896446416234857382909168309309630688331305154545352580787700878011742720440707156231891841057992434850068501355342227582074144717324718396296563918284728120322255330707786227631084119636101174217518654320128390401231343058708073280898554293777842571799775647325449392944570725467462072394864457569308219294304248413378339223195121800534783732295135735588409249690562213409520783181313960347723827308102920022860541043691808218543350580271593107019737918976365348051012746817678592727727988993175444584453532474156202438866838819565827414970029052602274354173178190323239427022953097424087683011937130778414189673555875258508014323428137406618951161046883845551087123412471364400737145434714864392224194773030522352601143771552489895838728148761974811275894561985163094852437703080985644653666048979901975905667811053289029958524703063742007291722490298429637413913574845245364780928447142275001431370017543206188428912106120676556219532197108435997375879569102044435752697298456147512203108094030745606163915437604076966518127099543894645297945324345093247636119593298654296614887389164509070158924404441687810434488061150620012547321097786493748417764592151734279632949607485719050349385098350202294648324398902047614892248381794929374952059877187100434970751833289677556040879755065563758085919673107576808662549999202791489324437408075089456174056904323973798979207791446889016369166632636035638123394649891606479407561222474471530411700646266636732205895085248823824764170316644547100628119484733814900100986786082211477261114056206393554335903410036064553032366200714266053598548735147707681592574886559888869327771461046450774938490837810526377213647071217152427693219479552580138352651791476758476864761332281826701978038126122728967682552206820425685782165630494478519812498630475776384700259524274670258777572341538755828794632819515842335609785884327007667337426644594091547392441314523035569100326662245947022517857248412004291423280879791576077952474202068318934524092750814844945529148131063116233331840380254781283689084385600858175504170157015630699919186013526052643206240745256569669847298952477441594748635701081031979500954081732722211598460098426985932512920424237248250698541558227081975966598720056015879151923686438360541128221854058867910136449528237543680180470919685862102358708465872395643586424250239281775923511452769821487580471289910257908740451431952197725174728917413539539795856895884961513784804247268727165303942024508367184898248006123651950710237279288601317817391869969699767431782664773248447758526620050588927086506013616563459173620496200348863132442180734592661348887012997849309740799709045762939781801481205704629203758859772476278892928066844445088880207986848424855774325574728566649552154520262460969975214802828263093097997124519153537792591659204109087699977445745067857471581656151077039286563447099850537157044829081400190710358959493358343935904669416958301921942118288210835104022359479660409954097409669785908666166908117346073702337825511531650740900904200220658196171839969860945908503151878488455004283026700303698398069644419655035582904253655945381261383285097911378914794161551292914993411444083214513058414480129560671193659591364146612550890288116403596333209446976453193340267725222134755872075133141618388704912211996423838163706006930973361661094103734887312836613195349528793780496172839376426055357343094188450140671138356505144988151110902047791487250988374130384058324229250761311655685931891857894126054047458969174494155762486464149775147410127618088224310828566286409277000561087588768230619606746804073498788244935099280434916850444895829823543

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

그다지 대답이 아니라 더 많은 힌트 :

7의 가장 오른쪽 숫자의 패턴은 1,7,9,3,1,7,9,3,1,7, ... 3의 4 번째 전력을 세 번째로만 생성하면됩니다. 추가 연구는 가장 큰 숫자 (3, 4, ...)에 대한 패턴을 보여줄 수 있지만, 나는 당신을 위해 연구하지 않았습니다.

매우 많은 숫자를 준비하십시오. 수학 가장 인기있는 가장 오른쪽 자릿수를 가진 다음 7의 힘은 5007 번째라고보고합니다.

나는 당신의 질문에 대한 답을 추측합니다. 더 빠른 접근 방식은 그렇게 게시하고 누군가가 당신에게 답을 말할 때까지 기다리는 것입니다! So 알고리즘이 마음에 들지 않으면 Wolfram Alpha를 사용해 볼 수도 있습니다.

페르마의 작은 정리 접근 방식은 수학적으로 합리적인 접근 방식이며 7 mod 10^6을 계속해서 곱하는 것이 가장 간단한 코드이지만 계산적으로 효율적이면서도 사용할 수 있는 또 다른 접근 방식이 있습니다(그러나 더 복잡한 코드가 필요함).먼저 7을 곱하면 마지막 숫자에만 의존 마지막 앞에 숫자(예:우리는 모든 모드 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로 끝나므로 mod 1000을 얻습니다.

343 543 743 943 143 343

열 #2(543)에 처음 세 자리 숫자가 있고 시퀀스가 ​​5번 반복되는 것을 볼 수 있으므로 거기에서 7^20만큼 올라가야 합니다.

우리는 이 트릭을 계속해서 사용할 수 있습니다.다음 숫자 블록이 얼마나 자주 반복되는지 확인하고 해당 블록 내에서 올바른 부분 수열을 찾은 다음 7이 아닌 7^n을 곱하세요.

우리가 실제로 하고 있는 일은 m번째 숫자에 대한 (곱셈) 링을 찾은 다음 이 방법을 따르면 모든 링의 크기를 함께 곱하여 동일한 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자리 숫자(예:mod 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이 동일한 초기 12자리 숫자 집합을 갖는 11^11 다음의 숫자임을 알려줍니다.궁금하다면 손으로 확인해보세요!

3^3에 대해서도 확인해 보겠습니다. 소수 확장이 27로 끝나는 3의 다음 거듭제곱은 무엇입니까?

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

예!

(임의의 자릿수를 처리할 수 있도록 편집에서 BigInt를 사용하도록 코드를 전환했습니다.하지만 코드는 퇴화 사례를 감지하지 못하므로 거듭제곱에 소수를 사용해야 합니다....)

또 다른 힌트 : 마지막 N 자리에만 관심이 있습니다. 계산 모듈로 10^n을 수행하고 결과를 정수에 잘 맞출 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top