Kezdőlap


Feladat:	F.3202	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Devecsery András , Gáli Gergely , Gerbicz Róbert , Gueth Krisztián , Gyenes Zoltán , Juhász András , Léka Zoltán , Lippner Gábor , Mansur Boase , Mecz Balázs , Papp Dávid , Pataki Péter , Pogány Ádám , Szabadka Zoltán , Székelyhidi Gábor , Terpai Tamás , Végh A. László , Zábrádi Gergely , Zawadowski Ádám
Füzet:	1999/január, 32 - 33. oldal		PDF \| MathML
Témakör(ök):	Prímtényezős felbontás, Feladat
Hivatkozás(ok):	Feladatok: 1997/december: F.3202

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.

Az $N^{*} = r_{1}^{2} + r_{2}^{2} + ... + r_{m}^{2}$ kifejezés értékét a logikai szita formula segítségével fogjuk meghatározni, azaz 1-től $n$ -ig összeadjuk az egész számok négyzeteit, majd kivonjuk azon számok négyzeteit, amelyeknek van közös osztójuk $n$ -nel. Ha $k$ az $n$ osztója, akkor jelölje $N (k)$ az $n$ -nél nem nagyobb, $k$ -val osztható pozitív egész számok négyzetösszegét. Ekkor a logikai szita formula szerint

\begin{matrix} \begin{matrix} N^{*} = N (1) - N (p_{1}) - N (p_{2}) - ... - N (p_{t}) + N (p_{1} p_{2}) + ... + N (p_{t - 1} p_{t}) - \\ - N (p_{1} p_{2} p_{3}) - ... - N (p_{t - 2} p_{t - 1} p_{t}) + ... + {(- 1)}^{t} N (p_{1} p_{2} ... p_{t}) . \end{matrix} \end{matrix}

Felhasználva az ismert

\begin{matrix} \begin{matrix} N (k) = k^{2} + {(2 k)}^{2} + ... + n^{2} = k^{2} (1^{2} + 2^{2} + ... + {(\frac{n}{k})}^{2}) = \\ = k^{2} \cdot \frac{\frac{n}{k} (\frac{n}{k} + 1) (2 \cdot \frac{n}{k} + 1)}{6} = \frac{n^{3}}{3 k} + \frac{n^{2}}{2} + \frac{n}{6} k \end{matrix} \end{matrix}

egyenlőséget, kapjuk, hogy

\begin{matrix} \begin{matrix} N^{*} = \frac{n^{3}}{3} (1 - \frac{1}{p_{1}} - \frac{1}{p_{2}} - ... - \frac{1}{p_{t}} + \frac{1}{p_{1} p_{2}} ... + \frac{1}{p_{t - 1} p_{t}} - \\ - \frac{1}{p_{1} p_{2} p_{3}} - ... - \frac{1}{p_{t - 2} p_{t - 1} p_{t}} + ... + {(- 1)}^{t} \frac{1}{p_{1} p_{2} ... p_{t}} + \\ + \frac{n^{2}}{2} (1 - (\binom{t}{1}) + (\binom{t}{2}) - (\binom{t}{3}) + ... + {(- t)}^{t} (\binom{t}{t})) + \frac{n}{6} (1 - p_{1} - p_{2} - ... - p_{t}) + \\ + p_{1} p_{2} + ... + p_{t - 1} t_{t} - p_{1} p_{2} p_{3} - ... - p_{t - 2} p_{t - 1} t_{p} + ... + {(- 1)}^{t} (p_{1} p_{2} ... p_{t})) . \end{matrix} \end{matrix}

A binomiális tétel szerint:

\begin{matrix} 1 - (\binom{t}{1}) + (\binom{t}{2}) - (\binom{t}{3}) + ... + {(- 1)}^{t} (\binom{t}{t}) = 0, \end{matrix}

tehát az

n

-ben másodfokú tag együtthatója 0. Az

n

-ben harmad-, illetve elsőfokú tagok együtthatója szorzattá alakítható, és így:

\begin{matrix} \begin{matrix} N^{*} = \frac{n^{3}}{3} (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) ... (1 - \frac{1}{p_{t}}) + \frac{n}{6} (1 - p_{1}) (1 - p_{2}) ... (1 - p_{t}) = \\ = \frac{n}{3} (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) ... (1 - \frac{1}{p_{t}}) (n^{2} + \frac{1}{2} {(- 1)}^{t} p_{1} p_{2} ... p_{t}) . \end{matrix} \end{matrix}

Ismert összefüggés, hogy

m = φ (n) = n (1 - \frac{1}{p_{1}}) ... (1 - \frac{1}{p_{t}})

. Ebből

\begin{matrix} N^{*} = \frac{m}{3} (n^{2} + \frac{1}{2} {(- 1)}^{t} p_{1} p_{2} ... p_{t}) \end{matrix}

valóban.