Kezdőlap


Feladat:	Gy.2463	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	1988/november, 381. oldal		PDF \| MathML
Témakör(ök):	Diofantikus egyenletek, Exponenciális egyenletek, Egészrész, törtrész függvények, Kombinatorikai leszámolási problémák, Gyakorlat
Hivatkozás(ok):	Feladatok: 1988/február: Gy.2463

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A feladat azt kérdezi, hogy hány valódi hatvány található az $[1, 10^{6}]$ intervallumban. Mivel $2^{20} > 10^{6} > 2^{19}$ , ezért egyetlen hatványkitevő sem lehet $19$ -nél nagyobb. Elegendő csupán a prímszám kitevőjű hatványokat összeszámolni, hiszen tetszőleges $y = u \cdot v$ összetett számra $x^{y}$ előáll ${(x^{u})}^{v}$ alakban.
Bármilyen $p$ kitevőhöz $h (p) = [\sqrt[p]{10^{6}}] - 1$ darab $p$ -edik hatvány esik az $[1, 10^{6}]$ intervallumba. (Az $1$ -et azért vontuk le, mert az $1^{p} = 1$ megoldás nem elégíti ki a feladat feltételét.) A $h (p)$ megfelelő értékeit az alábbi táblázat tartalmazza:

\begin{matrix} p & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 \\ h(p) & 999 & 99 & 14 & 6 & 2 & 1 & 1 & 1 \end{matrix}

Ez összesen

1123

darab számot jelent, ám vegyük észre, hogy bizonyos hatványokat ‐ ilyen például

64 = 8^{2} = 4^{3}

‐ még így is többször számoltunk. Egy hatványt pontosan akkor számoltunk többször, ha az előáll

x_{1}^{p_{1}}

és

x_{2}^{p_{2}}

alakban is, ahol

p_{1}

és

p_{2}

két különböző prímszám. Ha

p (m)

-mel jelöljük egy

p

prímszám kitevőjét az

m

prímtényezős felbontásában, akkor

x_{1}^{p_{1}} = x_{2}^{p_{2}}

esetén

p_{1} \cdot p (x_{1}) = p_{2} \cdot p (x_{2})

, minden

p

prímre. Mivel

p_{1} \neq p_{2}

, ezért

p (x_{2})

osztható

p_{1}

-gyel,

p (x_{1})

pedig

p_{2}

-vel, vagyis

x_{1} = x^{p_{2}}

és

x_{2} = x^{p_{1}}

, valamilyen

x

egészre. A fenti számlálás során tehát azokat az

x^{y}

hatványokat számoltuk többször, amelyekben az

y

kitevőnek egynél több prímosztója is van; mindegyiküket éppen annyiszor vettük számításba, ahány prímszámmal a kitevő osztható. Azok a

19

-nél nem nagyobb összetett számok, amelyeknek egynél több prímosztójuk van, a következők:

6

10

12

14

15

18

. Mivel ezek mindegyike pontosan két prímmel osztható, ezért az

x^{6}

x^{10}

x^{12}

x^{14}

x^{15}

x^{18}

-alakú hatványokat számoltuk kétszer. Közülük

x^{12} = {(x^{2})}^{6}

és

x^{18} = {(x^{3})}^{6}

lévén, csupán az

x^{6}

x^{10}

x^{14}

és

x^{15}

alakúakkal kell foglalkoznunk. Az ilyen hatványok száma az

[1, 10^{6}]

intervallumban rendre

9

2

1

1

. A valódi hatványok száma így

1123 - 13 = 1110

. Ehhez hozzá kell még vennünk az

1

-et is, hiszen pl.

1 = 2^{0}

. Összesen tehát

1111

olyan szám van az

[1, 10^{6}]

intervallumban, amely előállítható a kívánt alakban.