数クランチアルゴリズムを考案する必要があります

Question

私はこの質問につまずきました

  

7電源7は、7の高い電力が823543で終わる823543.ているのですか？

私はそれについてどのように行くべき？私が思いついた1が、それは試合のために、結果の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のコードを参照してください。

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

Answer 2

あなたが使用することができます <のhref = "ののオイラーの一般化のhttp：// EN .wikipedia.org /ウィキ/フェルマー％の27s_little_theorem」relが= 『noreferrer』>お使いの場合に適用されるフェルマーの小定理には> の任意の数のためののパワー400000にするは1つのモジュロ10 ^ 6に等しいです。 7 ^ 400000一及び7 ^ 400007に等しいこと823543に等しいことを意味する

10 ^ 6を法

、一のモジュロ10 ^ 6に等しい7の小さい力があってもよいです。そのような任意の電源が400000の約数でなければなりませんので、あなたは400000のすべての約数を検索する場合は、あなたの答えを見つける必要があります。

Answer 3

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秒後、TADで実行します：

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

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

Answer 4

それほど答え、より多くのヒント：

7の力の右端の数字のパターンは、1,7,9,3,1,7,9,3,1,7を行く...ので、あなただけの7の4回ごとの電力を生成する必要があることを確認第3回。さらなる研究は、2つ（3、4、...）右端の数字のパターンを表示することがありますが、私はあなたのためにそれらを研究していなけれます。

いくつかの非常に大きな数のために準備して、のMathematicaののレポートその人気のために右端の桁である第五千七と7の次のパワーます。

どの私が推測するには、あなたの質問に答える - 速いアプローチは、SOに投稿し、あなたに答えを伝えるために誰かを待つことです！あなたはSOのアルゴリズムを好きではない場合でもウルフラムアルファを試すことができます。

Answer 5

フェルマーの小定理のアプローチは、数学的に利にかなったものであり、わずか7のmod 10 ^ 6が最も簡単なコードであることにより、何度も繰り返しmulitplyingていますが、それは計算上効率的で取ることができる別のアプローチがあります（ただし、より複雑なコードが必要）。まず、7を掛けるとき、の最後のの桁が（すなわち、私たちはMOD 10すべてをやっている）の前にのみの最後のの桁に依存していること。注意してください当社は、取得するために7によって繰り返し乗算

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

さて、偉大なので、私たちは3をしたい場合、我々は7 ^ 3で開始し、そこからすべての7 ^ 4を上がります。今、私たちは、7 ^ 4を乗じたときに、最後の2桁は7 ^ 4の最後の2桁と前の回答の最後の2桁のみに依存することに注意してください。 7 ^ 4 7 ^ 4で上がっていくときに、実際に最後のの2つのの桁は常に同じになります。

2401であります

最後の三つについては何？まあ、^ 3 = 343 7,7は^ 4は401で終わるので、MOD我々が得る1000年

343 543 743 943 143 343

私たちは、カラム＃2（543）に私たちの最初の3桁の数字を持っている、と我々は順序が今まで5を繰り返し、私たちは7 ^ 20で、そこから上がる必要があることがわかります。

数字の繰り返しの次のブロックは、そのブロック内の右のサブシーケンスを見つける頻度を見つけ、その後、7でないアップ掛けるが、7 ^ nだけ

私たちは、何度も何度もこのトリックを再生することができます。

私たちは本当に私たちは、このに従うならば、同じN桁を持つ連続した大国間のスパンを取得するために一緒にすべてのリングのサイズをm番目の数字の上に（乗法）リングを見つけ、その後、乗算されてやっています方法。ここでは、単にこれを行い、いくつかのScalaのコード（2.8.0ベータ1）があります：

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

そこで、我々は発見した場合は、の1 私たちは、私たちは今、適切なリングのサイズを見つけることによって、それらのすべてを見つけることができますしたい数字の場合。 6桁の数字（すなわち、MOD 10 ^ 6）とベース7との場合には、我々は、の繰り返しサイズを見つける

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

ですから、私たちは答えを持っています！ 7 ^ 7は、7 ^ 10007は、第三の第一、^ 5007 7は第二されるなど。

これは一般的なものでありますので、

、我々は... 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

^ 23 3である必要があります。チェック：

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型を使用するように編集して、コードを交換。コードはしかし、縮退ケースを検出するので、あなたが....電源用の素数を使用してくださいません）

Answer 6

もう一つのヒント：あなたは、最後のN桁のみに関心がある：あなたは計算が10 ^ Nを法と

整数にうまく収まる結果を保つ行うことができます