需要设计一个数字运算算法
https://stackoverflow.com/questions/2424215
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我偶然发现了这样的问题：
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。看到此 Lua代码。
local x=1
for i=1,100000 do
x=(x*7) % 1e6
if x==823543 then print(i) end
end
其他提示
您可以使用欧拉推广的费马其应用到你的情况小定理说，对于任何数量的 不是由两个或五个整除，<强>一个以功率400000等于1个模10 ^ 6。这意味着7 ^ 400000是等于1且7 ^ 400007等于823543模10 ^ 6
有可能的7较小权力，也等于一模10 ^ 6。任何这样的动力应该是400000。除数所以，如果你搜索400000所有分频器，你应该找到答案。
在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 25461638709540284156782446957365168367138070393489656084508152816071765490828583739345420574947301301356529652113030016806506783009529977928336772622054260724106711204039012806363481521302203821096274017061906820115931889920385802499836705571461280700786627503189500663279772123190279763997339608040949194040289041117811256914511855302927500076094761237077649092849658261309060277197389760351907599243227298336309204635761799394324969277220810221310805265921431367291459357151617279190810954501590069774137519833706444943573459910208627100504003480684029216932299650285683013274883359754231186580602570771682084721896446416234857382909168309309630688331305154545352580787700878011742720440707156231891841057992434850068501355342227582074144717324718396296563918284728120322255330707786227631084119636101174217518654320128390401231343058708073280898554293777842571799775647325449392944570725467462072394864457569308219294304248413378339223195121800534783732295135735588409249690562213409520783181313960347723827308102920022860541043691808218543350580271593107019737918976365348051012746817678592727727988993175444584453532474156202438866838819565827414970029052602274354173178190323239427022953097424087683011937130778414189673555875258508014323428137406618951161046883845551087123412471364400737145434714864392224194773030522352601143771552489895838728148761974811275894561985163094852437703080985644653666048979901975905667811053289029958524703063742007291722490298429637413913574845245364780928447142275001431370017543206188428912106120676556219532197108435997375879569102044435752697298456147512203108094030745606163915437604076966518127099543894645297945324345093247636119593298654296614887389164509070158924404441687810434488061150620012547321097786493748417764592151734279632949607485719050349385098350202294648324398902047614892248381794929374952059877187100434970751833289677556040879755065563758085919673107576808662549999202791489324437408075089456174056904323973798979207791446889016369166632636035638123394649891606479407561222474471530411700646266636732205895085248823824764170316644547100628119484733814900100986786082211477261114056206393554335903410036064553032366200714266053598548735147707681592574886559888869327771461046450774938490837810526377213647071217152427693219479552580138352651791476758476864761332281826701978038126122728967682552206820425685782165630494478519812498630475776384700259524274670258777572341538755828794632819515842335609785884327007667337426644594091547392441314523035569100326662245947022517857248412004291423280879791576077952474202068318934524092750814844945529148131063116233331840380254781283689084385600858175504170157015630699919186013526052643206240745256569669847298952477441594748635701081031979500954081732722211598460098426985932512920424237248250698541558227081975966598720056015879151923686438360541128221854058867910136449528237543680180470919685862102358708465872395643586424250239281775923511452769821487580471289910257908740451431952197725174728917413539539795856895884961513784804247268727165303942024508367184898248006123651950710237279288601317817391869969699767431782664773248447758526620050588927086506013616563459173620496200348863132442180734592661348887012997849309740799709045762939781801481205704629203758859772476278892928066844445088880207986848424855774325574728566649552154520262460969975214802828263093097997124519153537792591659204109087699977445745067857471581656151077039286563447099850537157044829081400190710358959493358343935904669416958301921942118288210835104022359479660409954097409669785908666166908117346073702337825511531650740900904200220658196171839969860945908503151878488455004283026700303698398069644419655035582904253655945381261383285097911378914794161551292914993411444083214513058414480129560671193659591364146612550890288116403596333209446976453193340267725222134755872075133141618388704912211996423838163706006930973361661094103734887312836613195349528793780496172839376426055357343094188450140671138356505144988151110902047791487250988374130384058324229250761311655685931891857894126054047458969174494155762486464149775147410127618088224310828566286409277000561087588768230619606746804073498788244935099280434916850444895829823543
real 0m10.779s
user 0m10.709s
sys 0m0.024s
与其说一个答案，更一个提示：
观察到的7权力的最右边的数字模式变为1,7,9,3,1,7,9,3,1,7，......所以你只需要从生成的7每4个电源第三位。进一步的研究可能会显示为两（三，四，...），最右边的数字的模式，但我没有做研究它们。
有一些非常大的数字来制备，数学报告说，7下一个功率与所寻求的用于最右边的位是第五千○七。
我的猜测回答您的问题 - 更快的方法是SO后，等待有人来告诉你答案！你甚至可以尝试Wolfram Alpha的，如果你不喜欢的SO算法。
在费马小定理的方法是在数学上明智的一个，并且仅通过7 MOD 10 ^ 6是最简单的代码mulitplying遍地，但有你可以采取在计算上是有效的另一种方法（但需要更复杂的代码）。首先，请注意，由7乘以时的最后的数字只取决于的最后的（即我们所做的一切国防部10）之前的数字。我们一再乘以7获得
7 (4)9 (6)3 (2)1 (0)7 ...
好了，太好了，所以如果我们想要3分，我们开始在7 ^ 3并从那里每隔7 ^ 4。现在，我们注意到，7 ^ 4乘时，最后两位数字的7 ^ 4的最后两位数字和以前的答案的最后两位数字仅仅依赖。 7 ^ 4是2401所以实际上在过去的 2 数字将始终由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位数字（即模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
烨！
（在编辑切换代码中使用BigInt有因此它可以处理的数字任意数字，代码不检测退化情况，虽然，所以一定要使用主要用于电力....）
另一个提示：你只是在最后N个数字感兴趣：您可以执行计算模10 ^ N，并保持其结果很好地融入整
