Re: Kilpatehtävä

[vastaus aiempaan viestiin]

Reijo Sund kirjoitti 15.3.2002 22:44 :
>Sukro antaa tulokseksi niiden syötettä pienempien tai korkeintaan
>yhtäsuurien positiivisten kokonaislukujen määrän, joilla ei ole
>ykkösen lisäksi muita samoja tekijöitä kuin syötteellä.
>terv.
>Reijo

Reijon toteamus on aivan oikea.
Kyseessä on on lukuteoriassa tunnettu Eulerin phi-funktio phi(n), josta
käytetään myös nimitystä "totienttifunktio" ja siis
phi(n) on niiden lukua n pienempien positiivisten kokonaislukujen
määrä, joilla ei ole yhteisiä tekijöitä luvun n kanssa.

Esim. luvulle 30 nämä ovat
1, 7, 11, 13, 17, 19, 23, 29   (8 kpl.)
eli phi(30)=8
kuten A-sukrokin näyttää:
/A 30
8

On helppo todeta, että jos n on alkuluku, phi(n)=n-1 ja jos n on
muotoa 2^h, phi(n)=2^(h-1) (=parittomat luvut).

Miten phi(n) sitten lasketaan yleisesti?

Olkoon luvun n jako alkutekijöihin
n = p1^i1*p2^i2*...*pk^ik .
Tällöin phi(n) saadaan suoraan kaavasta

phi(n) = n*(1-1/p1)*(1-1/p2)*...*(1-1/pk).

Yleisen esityksen voi "arvata" parhaiten kirjoittamalla sen
muotoon (varsinainen todistus vaatii pitempiä tarkasteluja)

phi(n) = n*[(p1-1)/p1]*[(p2-1)/p2]*...*[(pk-1)/pk]

ja A-sukro laskee funktion arvon juuri tämän kaavan mukaan
tyyliin:
Muodostetaan
144(10:factors)=2^4*3^2
ja siirretään alkutekijähajotelma rivin alkuun
2^4*3^2
Poistetaan eksponentit (^4 ja ^2) ja kertomerkit (*)
2   3
ja poimitaan riville jääneet alkutekijät (2 ja 3) ja
lasketaan lopuksi funktion arvo
144*(2-1)/2*(3-1)/3=48

Tarkempia tietoja löytyy lukuteorian oppikirjoista ja verkosta
mm. osoitteesta
http://mathworld.wolfram.com/TotientFunction.html 

Luettelo keskustelunaiheista

Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!