Brauchen Sie noch einen Zahlknirschens Algorithmus zu entwickeln,

Question

Ich stolperte über diese Frage:

  

7 Leistung 7 823543. Welche höhere Leistung von 7 mit 823.543 endet?

Wie soll ich vorgehen? Der eine kam ich mit sehr langsam ist, wird es durch 7 und Kontrollen letzten 6 Ziffern des Ergebnisses hält für ein Spiel auf multipliziert wird.

Ich habe versucht, mit Lous Code:

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

Und CPU klingt wie ein Herd Druck, konnte aber nicht die Antwort erhalten: (

Answer 1

Multiply Modulo 10 ^ 6. Sehen Sie diese Lua Code .

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

Answer 2

Sie könnten verwenden Eulers Verallgemeinerung von

Brute-Force-Lösung in Python:

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

if __name__ == "__main__":
  check()

Läuft in einem bisschen mehr als 10 Sekunden auf meinem Rechner:

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

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

Nicht so sehr eine Antwort, mehr ein Hinweis:

Beachten Sie, dass das Muster der rechten Ziffern der Potenzen von 7 geht 1,7,9,3,1,7,9,3,1,7, ... Sie müssen nur jede vierte Leistung von 7 zu erzeugen, aus die dritte. Weitere Studien könnten ein Muster zeigen, für die zwei (drei, vier, ...) Ziffern ganz rechts, aber ich habe sie nicht für dich getan untersucht.

Seien Sie bereit für einige sehr große Zahlen vorbereitet, Mathematica berichtet, dass die nächste Potenz von 7 mit den gesuchten für Ziffern ganz rechts ist die 5007..

Welche Ich glaube, Ihre Frage beantwortet - ein schneller Ansatz ist es, schreiben auf und warten, bis jemand Sie sagen, die Antwort! Sie könnten sogar Wolfram Alpha versuchen, wenn Sie nicht den SO-Algorithmus gefällt.

Der kleine Satz Ansatz von Fermat ist ein mathematisch sinnvoll ein, und nur mulitplying immer und immer wieder um 7 mod 10 ^ 6 ist der einfachste Code, aber es gibt einen anderen Ansatz, den Sie also rechnerisch effizient nehmen könnte (aber erfordert komplexere Code). Erstens ist zu beachten, dass, wenn von 7 die Multiplikation letzten Ziffer nur auf die letzte Ziffer vor abhängt (das heißt wir sind alles mod 10 tun). Wir multiplizieren wiederholt von 7 zu erhalten

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

Okay, groß, so dass, wenn wir eine 3 wollen, beginnen wir bei 7 ^ 3 und alle 7 ^ 4 gehen von dort ab. Nun stellen wir fest, dass, wenn sie von 7 ^ 4, die letzten beiden Ziffern hängen nur von den letzten beiden Ziffern von 7 ^ 4 und den letzten beiden Ziffern der vorherigen Antwort multipliziert wird. 7 ^ 4 ist 2401 in der Tat also die letzte zwei Ziffern wird immer die gleiche sein, wenn sie von 7 ^ 4 nach oben.

Was ist mit den letzten drei? Nun, 7 ^ 3 = 343 und 7 ^ 4 enden mit 401, so mod 1000 erhalten wir

343 543 743 943 143 343

Wir haben unsere ersten drei Stellen in Spalte # 2 (543) erhalten, und wir sehen, dass die die Sequenz je 5 wiederholt, also sollten wir um 7 ^ 20 gehen von dort ab.

Wir können diesen Trick über spielen und immer wieder: Finden Sie, wie oft der nächste Block von Ziffern wiederholt, das Recht Teilfolge innerhalb dieses Blocks finden, und dann nicht mit 7 multiplizieren, sondern um 7 ^ n

.

Was wir wirklich tun ein (multiplikativ) Ring über den m-ten Ziffer zu finden, und multipliziert dann die Größen aller Ringe zusammen, um die Spanne zwischen aufeinanderfolgenden Kräfte zu erhalten, die die gleichen N Ziffern haben, wenn wir diese folgen Methode. Hier einig Scala-Code (2.8.0 Beta1), die genau dies tut:

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

Also, wenn wir gefunden haben, ein Fall der Ziffern, die wir wollen, können wir jetzt alle von ihnen finden, indem die Größe des entsprechenden Ring zu finden. In unserem Fall mit 6 Ziffern (d mod 10 ^ 6) und die Basis 7 finden wir eine Wiederholung Größe:

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

So haben wir unsere Antwort bekommen! 7 ^ 7 ist das erste, 7 ^ 5007 ist die zweite, 7 ^ 10007 ist der dritte, etc ..

Da diese generisch ist, können wir andere Antworten versuchen ... 11 ^ 11 = 285311670611 (eine 8-stellige Zahl). Schauen wir uns das Intervall aussehen:

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

Also, das sagt uns, dass 11 ^ 50000000007 die nächste Nummer ist nach 11 ^ 11 mit dem gleichen Anfangssatz von 12 Stellen. Überprüfen Sie von Hand, wenn Sie neugierig sind!

Lassen Sie sich auch mit 3 ^ 3 überprüfen - was ist die nächste Potenz von 3, deren Dezimalentwicklung endet mit 27

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

Sollte seine 3 ^ 23. Überprüfung:

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 Code in Bearbeitungen BigInt zu verwenden, so dass es eine beliebige Anzahl von Ziffern umgehen konnte. Der Code nicht degenerierten Fällen erkennt, obwohl, so stellen Sie sicher, dass Sie eine erstklassige für die Macht nutzen ....)

Noch einen Hinweis: Sie sind nur daran interessieren, in den letzten Ziffern N: Sie können Berechnungen Modulo ausführen 10 ^ N und halten das Ergebnis paßt gut in eine ganzen Zahl

Answer 3

Answer 4

Answer 5

Brute-Force-Lösung in Python:

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

if __name__ == "__main__":
  check()

Läuft in einem bisschen mehr als 10 Sekunden auf meinem Rechner:

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

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

Answer 6

Nicht so sehr eine Antwort, mehr ein Hinweis:

Beachten Sie, dass das Muster der rechten Ziffern der Potenzen von 7 geht 1,7,9,3,1,7,9,3,1,7, ... Sie müssen nur jede vierte Leistung von 7 zu erzeugen, aus die dritte. Weitere Studien könnten ein Muster zeigen, für die zwei (drei, vier, ...) Ziffern ganz rechts, aber ich habe sie nicht für dich getan untersucht.

Seien Sie bereit für einige sehr große Zahlen vorbereitet, Mathematica berichtet, dass die nächste Potenz von 7 mit den gesuchten für Ziffern ganz rechts ist die 5007..

Welche Ich glaube, Ihre Frage beantwortet - ein schneller Ansatz ist es, schreiben auf und warten, bis jemand Sie sagen, die Antwort! Sie könnten sogar Wolfram Alpha versuchen, wenn Sie nicht den SO-Algorithmus gefällt.

Der kleine Satz Ansatz von Fermat ist ein mathematisch sinnvoll ein, und nur mulitplying immer und immer wieder um 7 mod 10 ^ 6 ist der einfachste Code, aber es gibt einen anderen Ansatz, den Sie also rechnerisch effizient nehmen könnte (aber erfordert komplexere Code). Erstens ist zu beachten, dass, wenn von 7 die Multiplikation letzten Ziffer nur auf die letzte Ziffer vor abhängt (das heißt wir sind alles mod 10 tun). Wir multiplizieren wiederholt von 7 zu erhalten

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

Okay, groß, so dass, wenn wir eine 3 wollen, beginnen wir bei 7 ^ 3 und alle 7 ^ 4 gehen von dort ab. Nun stellen wir fest, dass, wenn sie von 7 ^ 4, die letzten beiden Ziffern hängen nur von den letzten beiden Ziffern von 7 ^ 4 und den letzten beiden Ziffern der vorherigen Antwort multipliziert wird. 7 ^ 4 ist 2401 in der Tat also die letzte zwei Ziffern wird immer die gleiche sein, wenn sie von 7 ^ 4 nach oben.

Was ist mit den letzten drei? Nun, 7 ^ 3 = 343 und 7 ^ 4 enden mit 401, so mod 1000 erhalten wir

343 543 743 943 143 343

Wir haben unsere ersten drei Stellen in Spalte # 2 (543) erhalten, und wir sehen, dass die die Sequenz je 5 wiederholt, also sollten wir um 7 ^ 20 gehen von dort ab.

Wir können diesen Trick über spielen und immer wieder: Finden Sie, wie oft der nächste Block von Ziffern wiederholt, das Recht Teilfolge innerhalb dieses Blocks finden, und dann nicht mit 7 multiplizieren, sondern um 7 ^ n

.

Was wir wirklich tun ein (multiplikativ) Ring über den m-ten Ziffer zu finden, und multipliziert dann die Größen aller Ringe zusammen, um die Spanne zwischen aufeinanderfolgenden Kräfte zu erhalten, die die gleichen N Ziffern haben, wenn wir diese folgen Methode. Hier einig Scala-Code (2.8.0 Beta1), die genau dies tut:

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

Also, wenn wir gefunden haben, ein Fall der Ziffern, die wir wollen, können wir jetzt alle von ihnen finden, indem die Größe des entsprechenden Ring zu finden. In unserem Fall mit 6 Ziffern (d mod 10 ^ 6) und die Basis 7 finden wir eine Wiederholung Größe:

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

So haben wir unsere Antwort bekommen! 7 ^ 7 ist das erste, 7 ^ 5007 ist die zweite, 7 ^ 10007 ist der dritte, etc ..

Da diese generisch ist, können wir andere Antworten versuchen ... 11 ^ 11 = 285311670611 (eine 8-stellige Zahl). Schauen wir uns das Intervall aussehen:

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

Also, das sagt uns, dass 11 ^ 50000000007 die nächste Nummer ist nach 11 ^ 11 mit dem gleichen Anfangssatz von 12 Stellen. Überprüfen Sie von Hand, wenn Sie neugierig sind!

Lassen Sie sich auch mit 3 ^ 3 überprüfen - was ist die nächste Potenz von 3, deren Dezimalentwicklung endet mit 27

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

Sollte seine 3 ^ 23. Überprüfung:

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 Code in Bearbeitungen BigInt zu verwenden, so dass es eine beliebige Anzahl von Ziffern umgehen konnte. Der Code nicht degenerierten Fällen erkennt, obwohl, so stellen Sie sicher, dass Sie eine erstklassige für die Macht nutzen ....)

Noch einen Hinweis: Sie sind nur daran interessieren, in den letzten Ziffern N: Sie können Berechnungen Modulo ausführen 10 ^ N und halten das Ergebnis paßt gut in eine ganzen Zahl

Answer 7

Nicht so sehr eine Antwort, mehr ein Hinweis:

Beachten Sie, dass das Muster der rechten Ziffern der Potenzen von 7 geht 1,7,9,3,1,7,9,3,1,7, ... Sie müssen nur jede vierte Leistung von 7 zu erzeugen, aus die dritte. Weitere Studien könnten ein Muster zeigen, für die zwei (drei, vier, ...) Ziffern ganz rechts, aber ich habe sie nicht für dich getan untersucht.

Seien Sie bereit für einige sehr große Zahlen vorbereitet, Mathematica berichtet, dass die nächste Potenz von 7 mit den gesuchten für Ziffern ganz rechts ist die 5007..

Welche Ich glaube, Ihre Frage beantwortet - ein schneller Ansatz ist es, schreiben auf und warten, bis jemand Sie sagen, die Antwort! Sie könnten sogar Wolfram Alpha versuchen, wenn Sie nicht den SO-Algorithmus gefällt.

Answer 8

Der kleine Satz Ansatz von Fermat ist ein mathematisch sinnvoll ein, und nur mulitplying immer und immer wieder um 7 mod 10 ^ 6 ist der einfachste Code, aber es gibt einen anderen Ansatz, den Sie also rechnerisch effizient nehmen könnte (aber erfordert komplexere Code). Erstens ist zu beachten, dass, wenn von 7 die Multiplikation letzten Ziffer nur auf die letzte Ziffer vor abhängt (das heißt wir sind alles mod 10 tun). Wir multiplizieren wiederholt von 7 zu erhalten

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

Okay, groß, so dass, wenn wir eine 3 wollen, beginnen wir bei 7 ^ 3 und alle 7 ^ 4 gehen von dort ab. Nun stellen wir fest, dass, wenn sie von 7 ^ 4, die letzten beiden Ziffern hängen nur von den letzten beiden Ziffern von 7 ^ 4 und den letzten beiden Ziffern der vorherigen Antwort multipliziert wird. 7 ^ 4 ist 2401 in der Tat also die letzte zwei Ziffern wird immer die gleiche sein, wenn sie von 7 ^ 4 nach oben.

Was ist mit den letzten drei? Nun, 7 ^ 3 = 343 und 7 ^ 4 enden mit 401, so mod 1000 erhalten wir

343 543 743 943 143 343

Wir haben unsere ersten drei Stellen in Spalte # 2 (543) erhalten, und wir sehen, dass die die Sequenz je 5 wiederholt, also sollten wir um 7 ^ 20 gehen von dort ab.

Wir können diesen Trick über spielen und immer wieder: Finden Sie, wie oft der nächste Block von Ziffern wiederholt, das Recht Teilfolge innerhalb dieses Blocks finden, und dann nicht mit 7 multiplizieren, sondern um 7 ^ n

.

Was wir wirklich tun ein (multiplikativ) Ring über den m-ten Ziffer zu finden, und multipliziert dann die Größen aller Ringe zusammen, um die Spanne zwischen aufeinanderfolgenden Kräfte zu erhalten, die die gleichen N Ziffern haben, wenn wir diese folgen Methode. Hier einig Scala-Code (2.8.0 Beta1), die genau dies tut:

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

Also, wenn wir gefunden haben, ein Fall der Ziffern, die wir wollen, können wir jetzt alle von ihnen finden, indem die Größe des entsprechenden Ring zu finden. In unserem Fall mit 6 Ziffern (d mod 10 ^ 6) und die Basis 7 finden wir eine Wiederholung Größe:

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

So haben wir unsere Antwort bekommen! 7 ^ 7 ist das erste, 7 ^ 5007 ist die zweite, 7 ^ 10007 ist der dritte, etc ..

Da diese generisch ist, können wir andere Antworten versuchen ... 11 ^ 11 = 285311670611 (eine 8-stellige Zahl). Schauen wir uns das Intervall aussehen:

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

Also, das sagt uns, dass 11 ^ 50000000007 die nächste Nummer ist nach 11 ^ 11 mit dem gleichen Anfangssatz von 12 Stellen. Überprüfen Sie von Hand, wenn Sie neugierig sind!

Lassen Sie sich auch mit 3 ^ 3 überprüfen - was ist die nächste Potenz von 3, deren Dezimalentwicklung endet mit 27

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

Sollte seine 3 ^ 23. Überprüfung:

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 Code in Bearbeitungen BigInt zu verwenden, so dass es eine beliebige Anzahl von Ziffern umgehen konnte. Der Code nicht degenerierten Fällen erkennt, obwohl, so stellen Sie sicher, dass Sie eine erstklassige für die Macht nutzen ....)

Answer 9

Noch einen Hinweis: Sie sind nur daran interessieren, in den letzten Ziffern N: Sie können Berechnungen Modulo ausführen 10 ^ N und halten das Ergebnis paßt gut in eine ganzen Zahl

Answer 10

Answer 11