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?
Ennå et stort tall.
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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)
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)
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.Magnus skrev:Vis at funksjonen aldri genererer primtall, utenom 11.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
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.
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
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Utenom 11 sjølsagt...Magnus skrev:Oi, beklager. Jeg mente "vis at funksjonen aldri genererer kvadrattall":-)
Magnus skrev:Skulle være 1... : pmrcreosote skrev:Utenom 11 sjølsagt...Magnus skrev:Oi, beklager. Jeg mente "vis at funksjonen aldri genererer kvadrattall":-)
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.
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.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 ..
[tex]\frac{f(6)}{7}=015873\\ \ \\\frac{f(12)}{7}=015873015873[/tex]
så
[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.
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.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.
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
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.