Oletetaanpa, että meillä on jokin lukua 1 suurempi kokonaisluku. Jos tästä luvusta lähtien muodostetaan kokonaislukujono laskemalla jonon seuraava luku edeltäjästään aina Eulerin phi-funktiota käyttäen, päädytään aina lopulta lukuun 1. Voidaanko sille askelmäärälle, jolla tämä tapahtuu, määrätä jokin yleinen yläraja?
Merkitään tätä askelmäärää vaikkapa f(n).
Esim.
phi(83)=82
phi(82)=40
phi(40)=16
phi(16)=8
phi(8)=4
phi(4)=2
phi(2)=1
Seitsemällä askeleella päädyttiin lukuun 1. Siis f(83)=7.
Selvästi ainakin f(n) 2.
Tiukempia ylärajoja kuitenkin kaivattaisiin.
Merkitään tätä askelmäärää vaikkapa f(n).
Esim.
phi(83)=82
phi(82)=40
phi(40)=16
phi(16)=8
phi(8)=4
phi(4)=2
phi(2)=1
Seitsemällä askeleella päädyttiin lukuun 1. Siis f(83)=7.
Selvästi ainakin f(n) 2.
Tiukempia ylärajoja kuitenkin kaivattaisiin.
Vastaukset 4
Vanhimmat
Olkoon luvun n alkutekijäesitys
n = p_1^{e_1} p_2^{e_2} * ... * p_r^{e_r}.
Tällöin tunnetusti Eulerin funktion arvoksi saadaan
phi(n) = (p_1-1)p_1^{e_1-1} (p_2-1)p_2^{e_2-1} * ... * (p_r-1)p_r^{e_r-1}.
Nyt havaitaan seuraavaa:
1. jos n on parillinen, phi(n) 2, niin phi(n) on parillinen,
3. phi(n) 1.
Täten laskettaessa f rekurssiivisesti, otetaan phi parillisesta luvusta vähintään toisesta askeleesta alkaen. Näin ollen askeleiden f(n) ylärajaksi tulee kaksi kantainen logaritmi luvusta n-1. Tämä raja on paras mahdollinen silloin, kun n on muotoa 2^m 1 oleva alkuluku.
Sori, pitää tietenkin olla f(n)
Erinomaista, nimimerkki 'Tiukempi raja'
Sain tähän asettamaani pikkupähkinään matemaattisesti täsmällisen ratkaisun paljon nopeammin, kuin osasin arvatakaan.
On hienoa, että täältä löytyy myös lukuteorian perusteiden osaajia.
Tuosta lukujonosta jotain lisätietoa löytyy mm. osoitteesta:
http://oeis.org/search?q=2,3,5,11,17,41,83&language=english&go=Search
Varmaan tätäkin probleemaa voidaan yleistään moneen suuntaan. Esimerkiksi iteroidun Eulerin funktion summalle on kehitetty asymptoottinen kaava. http://link.springer.com/article/10.1007/s00013-011-0314-6 .