2. Számok

2.1. Váltsuk aprópénzre...

Ne a tudásunkat, hanem mondjuk 1999 forintot. Az apró ne legyen teljesen apró, fillérek nem jöhetnek szóba, csak a komoly forintosok, s ezen belül is csak a létezõ címletek, azaz 1, 2, 5, 10, 20, 50, 100, 500 és 1000 forintos használható. A feladat NEM a jól ismert címletezés (szép magyar szóval a "münzölés"), hanem annak megválaszolása, hogy hány, úgynevezett lényegesen különbözõ felbontása állítható elõ a felsorolt címletekbõl az 1999-nek. Nem tekintjük különbözõnek például az 5=3+2 és az 5=2+3 felbontásokat, de ezektõl lényegesen eltérõ az 5=3+1+1 elõállítás.

2.2. Felbontások

Az additív számelmélet nehezebb problémái közül való a fenti feladat egyfajta általánosítása. Határozzuk meg, hogy egy N természetes szám hány lényegesen különbözõ módon állítható elõ K darab természetes szám összegeként. A program lehetõség szerint a felbontásokat állítsa is elõ.

2.3. A "pi" jegyei

A "pi", azaz a kör kerületének és átmérõjének hányadosa nem közönséges szám! Nem elég, hogy irracionális, azaz nem írható fel két egész szám hányadosaként, de még transzcendens is, ami annyit tesz, hogy nem található olyan racionális együtthatós algebrai egyenlet, melynek a p lenne a megoldása. (A középiskolai "minta" irracionális szám, a "gyök kettõ" nem transzcendens - úgynevezett algebrai - mivel megoldása a xx-2=0 egyenletnek.) A matematikusokat mindig is foglalkoztatta a pi egyre pontosabb meghatározása. Számos közelítõ eljárás lehetséges, például egy egységnyi sugarú körbe egyre nagyobb oldalszámú sokszögeket írva, területük a kívánt értéket fogja közelíteni. Ma már a pi-nek (nevezik Ludolf-féle számnak is) több mint egymillió jegye ismeretes. Az általunk kitûzött feladat ennél jóval szerényebb: írjunk programot, mely pi értékét 100 tizedesjegy pontossággal határozza meg, valamiféle közelítõ eljárást használva.

2.4. Különbözõ különbségek

A 0, 1, 4, 6 számnégyesnek van egy érdekes tulajdonsága. Ha a felsorolt számoknak minden lehetséges módon vesszük párosával a különbségeit, csupa különbözõ számot kapunk (mellesleg ezek egytõl hatig a természetes számok lesznek). Továbbá ha bármilyen számnégyest tekintünk, világos módon hatnál kisebb legnagyobb számra (a számnégyesen belül) ez a tulajdonság (tudniillik hogy a különbségek között nincs egyenlõ) nem teljesülhet. A feladat ezek után a következõ: minél több N-re keressük meg a legkisebb "felsõ" számmal rendelkezõ szám "n-est", melyre a páronként képzett különbségek mind különböznek. (Ne tekintsük különbözõnek a "tükrözéssel" megkapható sorozatokat, példánkban a 0, 2, 5, 6 számnégyest.)

2.5. Iker-majdnem-prímek

Egy természetes számot "majdnem prímnek" nevezünk, ha felírható két (nem feltétlenül különbözõ) prímszám szorzataként. Ha két szomszédos természetes szám is "majdnem prím", akkor nevezzük ezeket "iker-majdnem-prímeknek". Ilyen például a 9 és a 10, hiszen 9=3×3, illetve 10=2×5, azaz mindketten "majdnem prímek", és szomszédosak. A feladat olyan program írása, mely egy megadott határig elõállítja az összes "iker-majdnem-prím" párokat.

2.6. Mersenne-prímek

A Bild der Wissenschaft 1991 novemberi számában jelent meg egy híradás egy újabb prímrekordról: Michael Stromberg megtalálta az eddig ismert legnagyobb prímet, a 2756839-1 -et. Mint a cikkbõl is kiderül, Stromberg egy közel háromszázötven éves úton indult el. Mersenne francia matematikus 1644-ben közölte, hogy a 2p - 1 kifejezés 1<p<258 számok esetében csak a p=2, 3, 5, 7, 13, 17, 19, 31, 67, 127 és 257 értéknél ad prímet eredményül. A matematikusok háromszáz év alatt tisztázták, hogy a lista hibás: tartalmaz összetett számokat, s nem minden prímre vezetõ értéket adott meg Mersenne. A feladat egy olyan program írása, mely háromszáz évnél némileg rövidebb idõ alatt megtalálja a hibákat Mersenne listájában.

2.7. Bûvös prímek

Sokan találkoztak már bûvös négyzetekkel, azaz olyan számtömbökkel, melyek elemeit egy sor, oszlop vagy átló mentén összegezve mindig ugyanazt a számot kapjuk. Most ezt a közismert problémát kicsit megnehezítjük: a feladat olyan bûvös négyzetek készítése (pontosabban azokat elõállító program írása), mely csak prímszámokat tartalmaz. Hogy a feladat nem reménytelen, arra álljon itt egy 4×4-es példa:

3
61 19 37
43 31
5
41
7
11 73 29
67 17 23 13

2.8. Nagyon tökéletes számok

Suryanarayana indiai matematikus vezette be ezt a fogalmat. Nagyon tökéletesnek nevezte azt a számot, amely osztói összegének osztóit összeadva, a szám kétszeresét kapjuk. Ilyen például a 16, mert osztóinak összege 31, a 31 osztóit összeadva pedig 32-t kapunk. A feladat tehát: keressünk programmal nagyon tökéletes számokat!

2.9. Páratlan Pascal-háromszög

A biztonság kedvéért idézzük fel az úgynevezett binomiális együtthatókat tartalmazó háromszög néhány sorát:

1
1 1
1 2 1
1 3 3 1

és így tovább. A feladat az, hogy megkeressük mindazon sorokat, melyekben a nullától különbözõ elemek mind páratlanok; tehát a program a keresett sorok sorszámát és elemeit adja megoldásul.

2.10. Szerencsés számok

Nevezzünk egy számot szerencsésnek akkor, ha jegyei két csoportba oszthatók úgy, hogy a két csoportban a számok összege ugyanannyi. Ilyen szám például a 32843, mert 8+2=3+4+3. Keressük meg egy program segítségével az iker szerencsés számokat, azaz melyek különbsége egy.

2.11. Tükörszámok

D.D. Spencer "Játékok BASIC nyelven" címû könyvében található a következõ feladat. Az "indul a pap aludni" tükörmondat mintájára tükörszámoknak nevezhetjük azon számokat, melyeket visszafele olvasva, az eredetivel megegyezõ alakot kapunk. Ilyen számot természetesen elég könnyû csinálni, vagy találni. Ennél érdekesebb, hogy nem tükörszámokat tükörszámokká alakíthatunk az alábbi módon. Fordítsuk meg a számjegyek sorrendjét, s az így kapott számot adjuk az eredetihez. Ezt az eljárást addig folytassuk, míg az összeg tükörszám nem lesz. Például a 86-ból indulva: 86+68=154, 154+451=605, 605+506=1111; azaz három lépésben tükörszámhoz jutottunk. Erre az átalakításra a számok eltérõen reagálnak. Vannak, melyek egy lépésben átalakíthatók (például 43+34=77), s van olyan szám is, mely száz lépésen belül sem hajlandó átváltozni. A feladat egy olyan program írása, mely megkeresi azon N jegyû számokat, melyek N lépésben tükörszámokká varázsolhatók.

2.12. Számfordítás

Már többször szerepeltek rovatunkban számjegyek sorrendjével kapcsolatos rejtvények. Az alábbi - nem igazán nehéz - rejtvénynek némi történeti érdekessége van: eredetije a KÖMAL-ban 1980-ban (!) jelent meg, már akkor is számítástechnikai feladványként. Tehát keressük azokat az N jegyû természetes számokat, melyek minden jegye különbözõ, s a jegyek sorrendjének megfordításával kapott (valódi N jegyû) számnak osztója. Például a 2178 ilyen, mert 8712=2178×4.

2.13. Thibault-számok

Ha a számot és négyzetét a 10-es számrendszerben felírjuk, és minden 0-tól különbözõ számjegyet pontosan egyszer, magát a 0-t egyszer sem használjuk fel, akkor a számot Thibault-féle számnak nevezik. A feladat tehát egy olyan program írása, mely elõállítja az összes Thibault-számot.

2.14. Euklidesz nyomán

A megoldandó probléma a prímszámok végtelenségére Euklidesz által adott klasszikus bizonyításhoz kapcsolódik: vajon a levezetésben szereplõ

2+1=3

2×3+1=7

2×3×5+1=31

stb.

sorozatban csak prímszámok fordulnak-e elõ, vagy található-e közöttük összetett szám is? S ha igen, melyik a legkisebb?

2.15. Armstrong-számok

N-jegyû Armstrong számoknak nevezzük azokat a számokat, melyek számjegyei N-dik hatványainak összege éppen a számot adja. Például: négyjegyû Armstrong-szám a 1634, mivel 1634=1^4+6^4+3^4+4^4. A feladat a N-jegyû Armstrong-számokat elõállító program megírása.

2.16. Önreprodukáló számok

Ismert az a tény, hogy az 1-re, 5-re, 6-ra végzõdõ számok bármely hatványa szintén ezekre a számjegyekre végzõdik. Hiszen 6×6 = 36, vagy 15×15 = 225, és így tovább. Az érdekes az, hogy ezzel a tulajdonsággal kétjegyû számcsoportok is rendelkeznek, például: 76×76 = 5776, vagy 325×325 = 105625. De még itt sincs vége: találhatunk ezen tulajdonságnak eleget tevõ háromjegyû csoportokat is, egy ilyen a 376, mert 376×376 = 141376. Egy olyan programot várunk, amely egy adott N érték esetén megkeresi a fenti tulajdonságú szám-N-eseket.