Van-e olyan pozitív egész szám, amire igaz, hogy a tőle különböző pozitív osztóinak összege 2024?

Ami még biztos, hogy a keresett szám 2024^2 = 4.096.576-nál kisebb, elvégre az ezeknél nagyobb számoknak ha osztója k<=2024, akkor ennek osztópárja biztosan nagyobb lesz 2024-nél.

Szóval akár még Brute force módszerrel is lehetne rá programot írni, hogy megtalálja, ha létezik.

A brute force eredménye…

Előbb a brute force módszere. Kezdetben egy osztó van, az 1. Vegyünk egy „p” prímet, vegyük a meglévő osztókat, majd azok p-szeresét. Az utolsó elem az eddig vett prímek szorzata, azaz maga a szám lesz. Ha az új osztók összege az utolsó elem nélkül 2024, akkor kiírjuk, mint megoldást. Ha az osztók összege nagyobb, mint 2024, akkor nyilván új prímet már nem tudunk hozzávenni, mert mindenképpen 2024-nél nagyobb lesz az osztók összege. Ha az összeg 2024-nél kisebb, akkor vegyünk megint egy prímet.

Az eredmény: Nincs olyan szám, aminél valódi osztók összege az 1-gyel együtt 2024-et adna.

Közelítsük meg egy kicsit elemzőbb módon.

Egy számnak vannak osztói. Ebben benne van az 1 is, és önmaga is. Meg vannak valódi osztói, amibe az 1 és önmaga nem számít bele. A kérdező a kérdésében a keresett szám esetén a „számtól különböző” osztók összegét adja meg, ezzel ekvivalens megfogalmazás, hogy a keresett szám valódi osztóinak az összege 2023.

Ugye vannak számok, amiknek páros számú osztója van. Ha x osztható a-val, akkor nyilván osztható (x/a)-val is, így minden osztóra jut egy pár. Ez alól egyedül a négyzetszámok a kivételek, ahol ha a szám a², akkor az „a” osztónak a párja az a²/a=a lenne, ami ugyanaz a szám. A négyzetszámoknak tehát páratlan számú osztója van.

Nyilván ha egy 1-nél nagyobb számnak páros számú osztója van, akkor páros számú valódi osztója is. Ha páratlan, akkor meg páratlan. Hiszen valódi osztókat úgy kapjuk, hogy az osztók közül két számot, az 1-et és magát a vizsgált számot kizárjuk.

1. Tegyük fel, hogy a keresett számunk négyzetszám. Ekkor páratlan számú osztója és valódi osztója van, így ezek összege lehet páratlan. Ha nincs páratlan prímtényezője, akkor kizárólag 2 páros hatványai jöhetnek szóba. Így az osztók is 2 egymást követő hatványai lesznek, amiknek az összege 2ⁿ-1. A 2024 nem ilyen szám, tehát ezt az eshetőséget kilőttük. A számnak tehát vannak páratlan prímtényezői. Nyilván mivel négyzetszámról van szó, így a páros és páratlan prímtényezők is páros hatványon kell, hogy legyenek, ergo a szám 2 páros hatványának és egy páratlan szám négyzetének a szorzata. (Ebbe belefér az is, ha 2 a nulladik hatványon van, tehát a keresett szám egy páratlan szám négyzete.)

2. Tegyük fel, hogy a keresett számunk nem négyzetszám. Ekkor páros számú valódi osztója lesz. Ha minden prímtényezője páratlan, akkor minden valódi osztója is páratlan lesz, páros számú páratlan számot összeadva viszont mindenképpen páros számot kapunk, ami aligha lehet 2023-mal egyenlő, lévén az páratlan. Ergo nem lehet a szám minden prímtényezője páratlan, ergo a keresett számunk páros. Oké, most vegyük a számnak csak a páratlan prímtényezőit a megfelelő hatványon, és azokból képezzünk egy szorzatot. Ennek vegyük az összes osztóját, amik szintén mind páratlanok lesznek. Az eredeti számunk osztói ezek lesznek, meg ezeknek a 2 valahányadik hatványon lévő szorzatai. Tehát ennek a pusztán páratlan prímtényezőjű számnak az osztói egyrészt mind *valódi* osztói lesznek az eredeti számnak – maga ez a páratlan prímtényezőjű szám is, hiszen az egy páratlan szám, ennek a 2 valahányadik hatványával vett szorzata lesz az eredeti szám –, másrészt mind páratlanok lesznek. Nyilván páratlan számból páratlan darabot kell összeadni, hogy páratlan számot kapjunk, így ennek a páratlan prímtényezős számunknak páratlan osztója lehet csak, ami csak akkor lehetséges, ha az négyzetszám.

~ ~ ~

Minden lehetséges eset leszűkül egy

2ⁿ * (2m+1)²

alakú számra. Ez azért eléggé leszűkíti a keresést.

m-nek 0-nál nagyobbnak kell lennie, hiszen kizártuk az az eshetőséget, hogy a szám 2 egész hatványa. n-nek nyilván kisebbnek kell lennie 11-nél, hiszen a keresett szám valódi osztója minden n-nél kisebb hatványa a 2-nek, amiknek az összege önmagában 2ⁿ-1 lesz, ehhez jönnek még pluszban hozzá a páratlan osztók. n=11 esetén viszont eleve nagyobb az osztók összege 2047-nél.

Mivel 2m+1 valódi osztója a keresett számnak, így tudunk rá adni felső korlátot:

2m+1 < 2024

m < 1011,5

Ezzel rögtön 11*1011 = 11 121-re redukáltuk az egyáltalán lehetséges esetek számát.