Mer om store tall

[sEirik]

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

Hva er siste siffer i tallet ${2007}^{({2006}^{2005})}$ ?

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 ${2007}^{2006\cdot 2006\cdot \cdots \cdot 2006}\text{2005 ganger}=({2007}^{2006}{)}^{2006\cdots 2006}$
i modulo 10.

[daofeishi]

Ditto. Men kan man ikke modulær aritmetikk er det bare å legge merke til at siste sifferet i tallet ${2007}^{{2006}^{2005}}$ vil ha samme siste siffer som $7^{{2006}^{2005}}$, 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:

$2006=2\cdot 17\cdot 59$

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 $7^{{2006}^{2005}}$

[Knuta]

svaret er 1


Hvis jeg ikke har bomma helt:
$$\begin{gathered} {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} \end{gathered}$$

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 $(...a_3{a}_2{a}_1)$ og $(...b_3{b}_2{b}_1)$, er det bare $a_1$ og $b_1$ som påvirker hva siste siffer er i resultatet - Altså, i regnestykket $(...a_3{a}_2{a}_1)\cdot (...b_3{b}_2{b}_1)=(...c_3{c}_2{c}_1)$ er det bare $a_1$ og $b_1$ som påvirker $c_1$. (Prøve å bevise dette).

Dermed må man bare undersøke hvordan siste siffer oppfører seg i $7^n$. 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 ${2007}^n$ 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.