Ennå et stort 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.

Ennå et stort tall.

Innlegg Knuta » 25/10-2007 21:03

Vi har en funksjon [tex] f(n)\ =\ \frac{10^n-1}{9} [/tex] der n er et naturlig tall.

Funksjonen gir en rekke ett-tall. f.eks [tex]f(3)=111\ \ og\ \ f(6)=111111[/tex]

Det skulle ikke by på store problemer å finne ut om [tex]f(n)[/tex] er delbar på 3 eller 11. Men er [tex]f(1000000002)[/tex] delbar på 7 og 37?
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Re: Ennå et stort tall.

Innlegg JonasBA » 25/10-2007 21:22

[tex]f(1000000002)[/tex] er delelig med [tex]3[/tex] fordi tallet [tex]1000000002[/tex] er delelig med [tex]3[/tex]. Hvorvidt det er delelig med [tex]7[/tex] var ikke like åpenbart ..
JonasBA offline
Brahmagupta
Brahmagupta
Brukerens avatar
Innlegg: 357
Registrert: 26/05-2007 21:15
Bosted: Oslo/Lambertseter

Innlegg Magnus » 26/10-2007 00:01

Vis at funksjonen aldri genererer primtall, utenom 11.
Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg daofeishi » 26/10-2007 18:33

Eventuelt kan du benytte deg av at:

10 = 3 (mod 7) har orden 6, og genererer restene {1, 3, -5, -1, -3, 5}. Delelighet på 7 avgjøres altså av 1000000002 mod 6.


[tex]10^n \pmod{37} \equiv \left\{\begin{array}{ll} 10 & \textrm{hvis } n \equiv 1 \pmod 3\\ 26 & \textrm{hvis } n \equiv 2 \pmod 3\\ 1 & \textrm{hvis } n \equiv 0 \pmod 3 \end{array} \right[/tex]
(Selvsagt for ikke-negative n)
daofeishi offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 1486
Registrert: 13/06-2006 01:00
Bosted: Cambridge, Massachusetts, USA

Innlegg Knuta » 26/10-2007 19:56

Magnus skrev:Vis at funksjonen aldri genererer primtall, utenom 11.


Vel det har i allefall jeg digre problemer med å gjøre. I følge mine algoritmer så er f(19) et primtall. Hvis det viser seg at det ikke er et primtall så må jeg revurdere litt av hvert. Jeg skal kontrollsjekke det senere om det ikke er en eller annen som kan bekrefte.
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg mrcreosote » 26/10-2007 22:37

Ser ut til å stemme det, Knuta. Ta en kikk på http://primes.utm.edu/glossary/page.php?sort=Repunit (Legg spesielt til den lekre Word Art-en øverst til høyre...)

Det som er sant (og er ei oppgave å vise for den interesserte) er at vi aldri får ut et melkebasert påleggtall om vi anvender f på et sammensatt tall.
mrcreosote offline
Guru
Guru
Brukerens avatar
Innlegg: 1995
Registrert: 10/10-2006 19:58

Innlegg Magnus » 27/10-2007 12:30

Oi, beklager. Jeg mente "vis at funksjonen aldri genererer kvadrattall":-)
Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg mrcreosote » 27/10-2007 13:59

Magnus skrev:Oi, beklager. Jeg mente "vis at funksjonen aldri genererer kvadrattall":-)


Utenom 11 sjølsagt...
mrcreosote offline
Guru
Guru
Brukerens avatar
Innlegg: 1995
Registrert: 10/10-2006 19:58

Innlegg Realist1 » 27/10-2007 17:52

Er 11 et kvadrattall da?
Realist1 offline
Euclid
Euclid
Innlegg: 1993
Registrert: 30/01-2007 20:39

Innlegg Magnus » 27/10-2007 18:36

mrcreosote skrev:
Magnus skrev:Oi, beklager. Jeg mente "vis at funksjonen aldri genererer kvadrattall":-)


Utenom 11 sjølsagt...


Skulle være 1... : p
Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg Knuta » 27/10-2007 22:52

Magnus skrev:
mrcreosote skrev:
Magnus skrev:Oi, beklager. Jeg mente "vis at funksjonen aldri genererer kvadrattall":-)


Utenom 11 sjølsagt...


Skulle være 1... : p



Med forbehold om ulovlige metoder så skal jeg gjøre et forsøk:


Det er kun tall som ender på 1 og 9 i andre som gir kvadrattall som ender på 1 så holder det med å sjekke de to siste sifferene som ender på 1 eller 9.

Jeg setter opp en liste {..01, ..11, ..21, ..31, ..41, ..51, ..61, ..71, ..81, ..91} som ved kvadrering gir {..01, ..21, ..41, ..61, ..81, ..01, ..21, ..41, ..61, ..81}.

Tilsvarede liste {..09, ..19, ..29, ..39, ..49, ..59, ..69, ..79, ..89, ..99} gir {..81, ..61, ..41, ..21, ..01, ..81, ..61, ..41, ..21 ..01,} ved kvadrering.


Siden funksjonen gir bare ett-tall og ingen av listene ved kvadrering som gir bare ett-tall så kan det ikke bli andre enn f(1) som gir kvadrattall.
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Re: Ennå et stort tall.

Innlegg Knuta » 27/10-2007 23:07

JonasBA skrev:[tex]f(1000000002)[/tex] er delelig med [tex]3[/tex] fordi tallet [tex]1000000002[/tex] er delelig med [tex]3[/tex]. Hvorvidt det er delelig med [tex]7[/tex] var ikke like åpenbart ..


Alle [tex]f(6\cdot n)[/tex] der n er et naturlig tall, er delelig med 7. Svaret blir 6 tall som gjentar seg selv inklusive en ledende null.

[tex]\frac{f(6)}{7}=015873\\ \ \\\frac{f(12)}{7}=015873015873[/tex]



[tex]\frac{f(1000000002)}{7}=015873015873...015873015873[/tex] totalt 1000000002 siffere inklusive den ene ledende nullen.


Om det er delelig på 37? Hint 3*37=111 og da er vel resten litt enklere.

Hvis man tenker på denne måten burde også være lett å finne ut om funksjonen er delelig på 41.
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg Knuta » 27/10-2007 23:10

mrcreosote skrev:Ser ut til å stemme det, Knuta. Ta en kikk på http://primes.utm.edu/glossary/page.php?sort=Repunit (Legg spesielt til den lekre Word Art-en øverst til høyre...)

Det som er sant (og er ei oppgave å vise for den interesserte) er at vi aldri får ut et melkebasert påleggtall om vi anvender f på et sammensatt tall.


Puhhh!!!! Nå vart jeg redd ja... Satt og lurte på om mine algoritmer hadde klikka helt, det hadde betydd masse ekstraarbeid. Men det var en fin side det der. Intressant.
Knuta offline
Galois
Galois
Innlegg: 567
Registrert: 31/05-2006 13:59
Bosted: Oslo

Innlegg mrcreosote » 28/10-2007 09:03

Angående kvadrattalla: Det stemmer som du har gjort, altså kikka på det modulo 100, men det er langt raskere modulo 4: 11...111 gir resten 3 når vi deler på 4, og 3 er ikke en kvadratisk rest modulo 4 (det finnes ingen tall som er sånn at når man kvadrerer det og så deler på 4 får man 3 i rest); unntaket er 1.
mrcreosote offline
Guru
Guru
Brukerens avatar
Innlegg: 1995
Registrert: 10/10-2006 19:58

Hvem er i forumet

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