Mer om store tall

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Mer om store tall

Innlegg sEirik » 20/09-2007 19:41

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
sEirik offline
Guru
Guru
Brukerens avatar
Innlegg: 1551
Registrert: 12/06-2006 20:30
Bosted: Oslo

Innlegg fbhdif » 20/09-2007 20:47

tulla. Så ikke på oppgaven din da jeg regnet det ut, så jeg brukte gale tall.
fbhdif offline
Cayley
Cayley
Innlegg: 74
Registrert: 22/03-2007 17:48

Innlegg Magnus » 20/09-2007 21:22

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.
Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg daofeishi » 21/09-2007 11:43

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å.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg Charlatan » 21/09-2007 15:36

Det er vel en måte å regne dette ut uten modulær aritmetikk?
Charlatan offline
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Innlegg Magnus » 21/09-2007 15:46

Ja, er nøyaktig det samme.. bare litt annen notasjon egentlig:p
Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg Charlatan » 24/09-2007 20:58

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]
Charlatan offline
Guru
Guru
Innlegg: 2499
Registrert: 25/02-2007 17:19

Innlegg Knuta » 01/10-2007 21:20

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:
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg Magnus » 01/10-2007 22:38

Riktig svar, men sært måte å løse den på. Lukter data!
Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg Knuta » 02/10-2007 15:10

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
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg sEirik » 02/10-2007 15:16

Knuta skrev: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!.
sEirik offline
Guru
Guru
Brukerens avatar
Innlegg: 1551
Registrert: 12/06-2006 20:30
Bosted: Oslo

Innlegg Knuta » 02/10-2007 18:37

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.
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg daofeishi » 05/10-2007 09:36

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.
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 33 gjester