Kezdőlap


Cím:	Kedvenc problémáim (1983. február)
Szerző(k):	Csirmaz László
Füzet:	1983/február, 60 - 62. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Havonta egy-egy, számomra valamilyen oknál fogva kedves feladatot mondok el. Ezek megoldása, noha a középiskolában oktatott ismeretanyagnál többet nem kíván, mégis mély, igazi matematikusi gondolkodást igényel. A problémákra a megjelenést követő számban megoldást adok, azonban nem kívánok egyetlen problémát sem teljesen lezárni. Akár a feladatokkal, akár azok megoldásával kapcsolatban minden megjegyzést örömmel veszek.
Csirmaz László

\begin{matrix} * \end{matrix}

Mutassuk meg, hogy az első

64

pozitív egészből nem lehet olyan

4 \times 4 \times 4

-es, hagyományos értelemben vett bűvös kockát előállítani, melyben az egy egyenesre eső

4 - 4

szám összege (beleértve a testátlókat is) ugyanannyi legyen.

\begin{matrix} * \end{matrix}

Tetszőleges

x

valós számra

[x]

jelöli

x

egész részét, vagyis a legnagyobb olyan egészt, mely még nem nagyobb

x

-nél. Minden

t ≧ 2

természetes számra legyen

\begin{matrix} f (t) = [\frac{1}{\sum_{i = 1}^{t - 1} [\frac{1}{1 + t - i \cdot [t / i]}]}], \end{matrix}

(1)

továbbá ha

n ≧ 1

egész, akkor

\begin{matrix} g (n) = 1 + 2^{2 n} - \sum_{i = 2}^{2^{2 n}} [\frac{1}{1 + [\frac{n - 1}{\sum_{f = 2}^{i} f (j)}]}] . \end{matrix}

(2)

Mármost a kérdés az: mit számít ki ez a"képlettel definiált''

g (n)

függvény?

t ≧ 2

és

1 ≦ i < t

természetes számok, akkor

t - i \cdot [t / i]

értéke éppen

t

-nek

i

-vel való osztásakor kapott maradék. Így

\begin{matrix} \frac{1}{1 + t - i \cdot [t / i]} \end{matrix}

(3)

értéke

1

, ha

i

osztója

t

-nek, különben pedig

1

-nél kisebb pozitív szám, hiszen ekkor a nevező

1

-nél nagyobb. Ezért (3) egész része vagy

1

vagy

0

, attól függően, hogy

i

osztója-e

t

-nek vagy sem. Tehát a

\begin{matrix} \sum_{t = 1}^{t - 1} [\frac{1}{1 + t - i \cdot [t / i]}] \end{matrix}

kifejezés megadja

t

azon

d

osztóinak számát, amikre

1 ≦ d ≦ t - 1

. Ez a szám csak akkor

1

, ha

t

prímszám (hiszen legalább egy osztója, ti. az

1

, minden számnak van), egyébként értéke legalább

2

. Ez pedig azt jelenti, hogy

f (t)

értéke akkor

1

, ha

t

prímszám, és

0

, ha

t

összetett.
Ezek után térjünk át a

g (n)

-et definiáló

(2)

formulára. Mivel

f (i) = 1

, ha

i

prím, és

f (i) = 0

egyébként, azért

\sum_{j = 2}^{i} f (j) > n - 1

pontosan akkor áll fenn, ha

i

legalább akkora, mint az

n

-edik prímszám, amit jelöljünk

p_{n}

-nel. (Így például

p_{1} = 2, p_{2} = 3, p_{3} = 5

stb.). Más szavakkal

\begin{matrix} [\frac{1}{1 + [\frac{n - 1}{\sum_{j = 2}^{} f (j)}]}] = {\begin{matrix} 0, ha i < p_{n} \\ 1, ha i ≧ p_{n} . \end{matrix} \end{matrix}

Most fogadjuk el egy pillanatra, hogy az

n

-edik prímszám kisebb

2^{2 n}

-nél, akkor

\begin{matrix} \sum_{i = 2}^{2^{2 n}} [\frac{1}{1 + [\frac{n - 1}{\sum_{j = 2}^{i} f (j)}]}] = 2^{2^{n}} - (p_{n} - 1), \end{matrix}

hiszen

i = p_{n}

-től

i = 2^{2 n}

-ig csupa egyest kellett összeadnunk. Ennek alapján

g (n) = p_{n}

,az

n

-edik prímszám. Levonhatjuk a tanulságot : igenis

v a n

olyan "képlet'', ami az

n

-edik prímszámot definiálja, bár ennek alapján az

n

-edik prím kiszámítása sokkal több munkát igényel, mintha azt a "hagyományos módon'' keresnénk meg.
Annak igazolására, hogy az

n

-edik prímszám

2^{2^{n}}

-nél kisebb, tekintsük az alábbi

n

darab számot :

\begin{matrix} 2,2 + 1, 2^{2} + 1, 2^{4} + 1, ..., 2^{2^{n - 1}} + 1. \end{matrix}

(4)

Ha megmutatjuk, hogy ezek közül semelyik kettőnek nem lehet közös prímtényezője, készen vagyunk: a (4) alatti

n

darab szám mindegyike kisebb

2^{2^{n}}

-nél, s mindegyiknek van az összes többi prímosztóitól különböző prímosztója. Így

2^{2^{n}}

előtt legalább

n

prímszám van, vagyis az

n

-edik prím kisebb

2^{2^{n}}

-nél.
Az viszont, hogy a (4) alatti számok páronként relatív prímek,egyszerűen következik abból, hogy az első kivételével az összes többi páratlan, továbbá az

a^{2} - 1 = (a + 1) (a 1)

összefüggés

i

-szeri alkalmazásával

\begin{matrix} 2^{2^{i}} - 1 = (2^{2^{i = 1}} + 1) (2^{2^{i = 2}} + 1) ... (2^{4} + 1) (2^{2} + 1) (2 + 1) (2 - 1) . \end{matrix}

Így

j < i

esetén

2^{2^{j}} + 1

összes prímosztója osztója

(2^{2^{i}} - 1)

-nek is, vagyis nem lehet osztója

(2^{2^{1}} + 1)

-nek.
Nem nehéz belátni azt sem, hogy az

n

-edik prím még

2^{n}

-nél is kisebb, tehát (2)-ben

2^{2^{n}} - t

mindkét helyen

2^{n}

-re cserélhetnénk.