Zadanie
S pravým Marťanom na palube sa vrátili na obežnú dráhu. Teraz boli na rade pokusy, lenže ako na to? Potrebovali poradiť. Na Marse nebolo publikum, ktorého pomoci by rozumeli, a hádať s pravdepodobnosťou \(50:50\) bol vo vesmíre priveľký risk. Rozhodli sa teda pre priateľa na telefóne. Astronaut Patricks už zdvíhal slúchadlo, keď sa zháčil.
„Počuj, Pat, akú má Zem predvoľbu?“
Predvoľba Zeme je celé číslo \(n \geq 2\). Astronaut Matthews si pamätá, že \(p(k)\) označuje najväčšieho prvočíselného deliteľa čísla \(k\), \(\lfloor k \rfloor\) označuje dolnú celú časť reálneho čísla \(k\) (teda najväčšie celé číslo menšie alebo rovné \(k\)) a navyše platí \[p(n) + \left\lfloor \sqrt{n} \right\rfloor = p(n+1) + \left\lfloor \sqrt{n+1} \right\rfloor.\]
Patricksovi tak nezostáva nič iné ako vyskúšať všetky možné predvoľby. Pomôžte mu tým, že určíte, ktoré všetky \(n\) má vyskúšať.
Pozrime sa najskôr, ako funguje funkcia \(\left\lfloor \sqrt k \right\rfloor\). Nech \(k\) je prirodzené číslo. Potom \(k^2\) sa odmocní na \(k\), \((k+1)^2\) sa odmocní na \(k+1\). Medzi \(k\) a \(k+1\) nie je žiadne prirodzené číslo, takže pre všetky čísla \(l\) také, že \(k^2\leq l<(k+1)^2\) je odmocnina ,,niekde medzi" \(k\) a \(k+1\), takže \(\left \lfloor \sqrt l \right\rfloor = k.\) Pre dve po sebe idúce čísla \(n\) a \(n+1\) to znamená, že buď sú obe ,,medzi" dvoma štvorcami, teda \(k^2\leq n<n+1<(k+1)^2\), a teda \(\left \lfloor \sqrt{n} \right\rfloor=\left \lfloor\sqrt{n+1} \right\rfloor\) alebo je väčšie z nich štvorec, a v tom prípade \(\left \lfloor \sqrt{n} \right\rfloor+1=\left \lfloor \sqrt{n+1} \right\rfloor\).
Ak by platilo \(\left \lfloor \sqrt{n} \right\rfloor=\left \lfloor \sqrt{n+1} \right\rfloor\), muselo by platiť aj \(p(n)=p(n+1)\). Lenže \(n\) a \(n+1\) sú nesúdeliteľné, nemôžu mať rovnakého prvočíselného deliteľa. Táto možnosť teda nemôže nastať.
Keď \(\left \lfloor\sqrt{n}\right\rfloor+1=\left \lfloor \sqrt{n} \right\rfloor\), tak musí platiť \(p(n)=p(n+1)+1\). Hľadáme teda 2 prvočísla s rozdielom 1, to sú nevyhnutne 2 a 3. Takže \(p(n)=3, p(n+1)=2\).
Keďže najväčším prvočíselným deliteľom čísla \(n+1\) je 2, \(n+1\) musí byť mocninou dvojky. Navyše vieme, že \(n+1\) je štvorec, takže musí byť párnou mocninou. \[\begin{align} n+1=2^{2k}\\ n=2^{2k}-1\\ n=(2^k-1)(2^k+1)\end{align}\] O čísle \(n\) vieme, že jeho najväčší prvočíslený deliteľ je 3, a zároveň je nepárne (keďže \(n+1\) je párne). Musí byť teda mocninou 3. Vieme tiež, že \((2^k-1)\) a \((2^k+1)\) sú deliteľmi \(n\), no keďže ich rozdiel je 2, nemôžu byť obe súčasne deliteľné 3. Preto jedno (menšie) z nich musí byť rovné 1, a z toho už druhé je nevyhnutné rovné 3. Potom \(n=1\cdot3\), takže jediná vhodná predvoľba je 3.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.