matematikk.net

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?

[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 ..

Vis at funksjonen aldri genererer primtall, utenom 11.

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)

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.

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.

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

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

Utenom 11 sjølsagt...

Er 11 et kvadrattall da?

mrcreosote skrev:

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

Utenom 11 sjølsagt...

Skulle være 1... : p

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.

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]

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.

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.

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.