Mer om store tall

[sEirik]

Dette var ei oppgave på Abel-konkurransen i fjor.

Hva er siste siffer i tallet [tex]2007^{(2006^{2005})}[/tex] ?

Alternativ:

A: 1
B: 3
C: 7
D: 9
E: ingen av disse tallene

[fbhdif]

tulla. Så ikke på oppgaven din da jeg regnet det ut, så jeg brukte gale tall.

[Magnus]

Jeg løste den ved å betrakte [tex]2007^{2006\cdot 2006\cdot\cdots\cdot 2006}\ \text{2005 ganger} = (2007^{2006})^{2006\cdots 2006} [/tex]
i modulo 10.

[daofeishi]

Ditto. Men kan man ikke modulær aritmetikk er det bare å legge merke til at siste sifferet i tallet [tex]2007^{2006^{2005}}[/tex] vil ha samme siste siffer som [tex]7^{2006^{2005}}[/tex], og finne en smart måte å redusere problemet på.

[Charlatan]

Det er vel en måte å regne dette ut uten modulær aritmetikk?

[Magnus]

Ja, er nøyaktig det samme.. bare litt annen notasjon egentlig:p

[Charlatan]

Hmm, observerer at når man ganger 7 med seg selv, så vil siste sifferet bli 7,9,3,1 og igjen. Og jeg kan bare anta at dette fortsetter i det uendelige. Så var det å finne ut hva man kan dele 2006 på av 1,2,3,4. Vi primtallsfaktoriserer og får:

[tex]2006=2 \cdot 17 \cdot 59[/tex]

Vi ser at 2 er det eneste av disse tallene det kan deles på, og derfor må siste tallet være nummer to i rekken, altså 9.

Jeg er aldeles ikke sikker på dette her altså.

Men hvordan observerer man at tallet slutter på det samme som [tex]7^{2006^{2005}}[/tex]

[Knuta]

svaret er 1


Hvis jeg ikke har bomma helt:
[tex] 2007^{2006^{2005}} = \\ \ \\ 2007^{2006^{2003}\cdot 2006\cdot 2006}=\\ \ \\2007^{2006^{2003}\cdot 1003\cdot 1003\cdot 2\cdot 2}=\\ \ \\ 4028049^{2006^{2003}\cdot 1003\cdot 1003\cdot 2}=\\ \ \\16225178746401^{2006^{2003}\cdot 1003\cdot 1003} [/tex]

Nå kan du gange tallet med seg selv uendelig antall ganger. det siste sifferet blir alltid 1. Neste spørsmål er antall nuller foran det siste sifferet :lol:

[Magnus]

Riktig svar, men sært måte å løse den på. Lukter data!

[Knuta]

Helt plain kalkulator. Det eneste den ble brukt til var 2007^2 og 4028049^2 Men det var sikkert ikke lov? Jeg pleier å ha min helt egen måte løse ting på. Problemet ligner veldig på den oppgaven jeg gjør nå. Fjern alle de bakerste nullene og finn de fem siste sifrene i 1000000000000! Den viste seg å være vanskligere enn jeg trodde. Der er det ikke bare å bruke de fem siste siffrene og gange de med hverandre.

http://projecteuler.net/index.php?section=view&id=160

[sEirik]

Helt plain kalkulator. Det eneste den ble brukt til var 2007^2 og 4028049^2 Men det var sikkert ikke lov? Jeg pleier å ha min helt egen måte løse ting på. Problemet ligner veldig på den oppgaven jeg gjør nå. Fjern alle de bakerste nullene og finn de fem siste sifrene i 1000000000000! Den viste seg å være vanskligere enn jeg trodde. Der er det ikke bare å bruke de fem siste siffrene og gange de med hverandre.

http://projecteuler.net/index.php?section=view&id=160

Vet ikke om det hjelper, men jeg og TrulsBR kom en gang i tiden frem til et uttrykk for hvor mange nuller det er på slutten av n!.

[Knuta]

Akkurat det er ikke det største problemet. Å finne ut hvor mange nuller 10[sup]12[/sup]! har er en ganske enkel prosess. Det jeg startet med var å ta alle tallene, skrellet for nuller bak og ta de siste 5 sifrene og multiplisere de med hverandre. For hver multiplikasjon ble samme prosessen gjentatt. Men det jeg observerte var at jeg rant totalt ut på tid. Det hadde tatt år på å gjennomføre oppgaven.

Så fant jeg heller ut hvor mange 1,2,3,4 og 5 sifret tall det dreide seg om når nuller og foranliggende siffre som var fjernet og kjørte en lignende opperasjon som jeg gjorde ovenfor. Programmet kjørte igjennom i løpet 0.5 sekunder.

Men det jeg glemte var f.eks. tallet 5[sup]8[/sup] som er lik 390625. Når det ble skrelt bort i prosessen, ble det til 90625. Det er jo 5[sup]5[/sup]*29. Dette gir et feil resultat, 3 nuller for lite og en faktor på 29 i svaret. Problemet er definert, nå er det bare jobben igjen.

Men problemet lignet litt på oppgaven.

[daofeishi]

Poenget her er at dersom du multipliserer sammen to tall [tex](...a_3a_2a_1)[/tex] og [tex](...b_3b_2b_1)[/tex], er det bare [tex]a_1[/tex] og [tex]b_1[/tex] som påvirker hva siste siffer er i resultatet - Altså, i regnestykket [tex](...a_3a_2a_1) \cdot (...b_3b_2b_1) = (...c_3c_2c_1)[/tex] er det bare [tex]a_1[/tex] og [tex]b_1[/tex] som påvirker [tex]c_1[/tex]. (Prøve å bevise dette).

Dermed må man bare undersøke hvordan siste siffer oppfører seg i [tex]7^n[/tex]. Man vil se at siste siffer i tallet skifter syklisk med periode 4. (Prøv å bevise dette og.)

Dermed ser man at dersom n i [tex]2007^n[/tex] gir rest 1 ved deling på 4 blir siste sifferet 7. Dersom n gir rest 2 ved deling på 4 er siste siffer 9. Dersom resten er 3 er siste siffer 3, og dersom resten er 0, er siste siffer 1.

Siden 4 helt tydelig er faktor av eksponenten, vil siste siffer være 1.