Hogy lehet hatékonyan megtalálni azt a számot amelyiknek a legtöbb osztója van egy adott tartományon belül?

Huhh… Nem tűnik egyszerű kérdésnek.

Ha n-ig keressük azt a számot, aminek a legtöbb osztója van, akkor van egy alsó becslés, megkeressünk az n-nél kisebb olyan számot, ami 2 hatványa. Mondjuk ha 1000 alatt keressük azt a számot, aminek a legtöbb osztója van, akkor 512 az egyik jelölt, ami 2^9, aminek 10 osztója van. A prímtényezők multiplicitásának összege képlettel felírva: ⌊log₂n⌋, ahol ⌊x⌋ a szám lefelé kerekített értékét jelenti.

Ez a minimumra vonatkozó becslés. Tudjuk tehát, hogy a keresett számnak prímtényezőinek multiplicitásának összege maximum 9 lehet. Nyilván ha csökkentjük a multiplicitások összegét, az csak akkor fog magasabb osztószámot eredményezni, ha növeljük a prímfaktorok számát. Az is belátható, hogy egy magasabb prímfaktor multiplicitása nem lehet nagyobb, mint egy alacsonyabb prímfaktor multiplicitása, hiszen egy fordított esethez képest magasabb számot kapnánk.

Oké, tegyük fel, hogy a keresett számuk prímtényezői multiplicitásának összege nem 9, hanem csak 8. Nyilván akkor legalább 2 prímtényezőjének kell lennie, hiszen a 2^9 az már 1024 lenne, ami nagyobb 1000-nél.

Tegyük fel, hogy 2 prímtényezőnk van. Ekkor a legkisebb szám, ami felírható így, a következő:

2^7 * 3^1. Ez 384, és 16 osztója van. Ez jobb, mint az előző jelöltünk, az 512, aminek csak 10 osztója volt.

Oké, vigyünk arrébb egy hatványkitevőt:

2^6 * 3^2. Ez 576, és 21 osztója van. Még jobb jelölt.

Folytassuk:

2^5 * 3^3. Ez 864 és 24 osztója van. Még jobb.

Folytassuk?

2^4 * 3^4. Ez 1296, ami már nagyobb, mint ezer.

A két prímtényezős változatokat ezzel kivégeztük egyszer és mindenkorra. Jó, tegyük fel, hogy ugyanúgy 8 a prímtényezők multiplicitásának összege, de nem 2, hanem 3 prímtényezőnk van:

2^6 * 3^1 * 5^1. Ez 960, és 28 osztója van. Újabb rekorder…

2^5 * 3^2 * 5^1. Ez 1440, tehát ezzel is befürödtünk, itt meg is állhatunk.

Tegyük fel, hogy 4 prímtényezőnk van:

2^5 * 3^1 * 5^1 * 7^1. Ez 3360, amivel megint befürödtünk.

Ezzel megtaláltuk azt a legnagyobb osztószámmal rendelkező számot, ami prímtényezőinek a száma 8. Folytassuk 7-el. Nyilván itt már csak azokat a variációkat kell megnézni, aminél az előbb túlfutottunk 1000-nél:

2^4 * 3^3. Ez 432 és 20 osztója van.

Nézzük 3 prímtényezővel:

2^4 * 3^2 * 5^1. Ez 720 és 30 osztója van. Eddig ez a legjobb.

2^3 * 3^3 * 5^1. Ez 1080. Sok.

Nézzük 4 prímtényezővel:

2^4 * 3^1 * 5^1 * 7^1. Ez 1680. Újfent sok.

Oké, menjünk tovább, feltételezzük, hogy a prímtényezők multiplicitásának összege 6. Mivel a két prímtényezős eseteknél a legkedvezőbb esetet már lefedtük, és 1000-nél kisebb számot kaptunk, ennek minimum 3 prímtényezőjének kell lennie.

2^4 * 3^1 * 5^1. Ez 240 és 20 osztója van. Volt jobb találatunk.

2^3 * 3^2 * 5^1. Ez 360 és 24 osztója van. Volt ennél jobb találatunk.

2^2 * 3^2 * 5^2. Ez 900 és 27 osztója van. Volt jobb találatunk.

Ezzel a három prímtényezős eseteket is kilőttük, mert a legideálisabb elrendezéssel is 1000 alatt maradtunk, de az osztók számánál találtunk már magasabbat. Jöjjenek e 4 prímtényezős alakok:

2^3 * 3^1 * 5^1 * 7^1. Ez 840 és 32 osztója van. Újabb rekorder.

2^2 * 3^2 * 5^1 * 7^1. Ez 1260. Sok.

Vehetjük még azt, hogy 5 prímtényező van:

2^2 * 3^1 * 5^1 * 7^1 * 11^1. Ez 4620. Sok.

Menjünk tovább, tételezzük fel, hogy csak 5 prímtényezők multiplicitásának összege. Mivel a 3 prímtényezős alaknál elértük az ideális állapotot (a legkisebb és legnagyobb multiplicitás közötti különbség 1 vagy annál kisebb, jelen esetben pont nulla volt), ezért minimum 4 prímtényezőt kell feltételeznünk:

2^2 * 3^1 * 5^1 * 7^1. Ez 420 és 24 osztója van. Nem nyert.

Négy prímtényezővel nincs jobb lehetőség az osztók számára nézve, ezzel a négy prímtényezős alakokat is kilőttük. Maradnak az öt prímtényezős alakok, de mivel a multiplicitások összege is öt, így egyetlen lehetőség maradt csak:

2*3*5*7*11. Ez 2310, ami megint nagyobb ezernél.

Nyilván itt véget is ért a keresés. A legjobb találat a 840 = 2^3 * 3 * 5 * 7 volt, aminek 32 osztója van.

~ ~ ~

Kicsit hosszú és száraz volt, de remélem érthető a logikája. Lehetne algoritmizálni is, de most nem vállalkozok rá. A lényeg, hogy ezzel a módszerrel azért kell számolni, de nem kell minden számot prímtényezőkre bontani ahhoz, hogy megtaláljuk, hogy egy intervallumban melyik számnak van a legtöbb osztója.

> Az is biztos, hogy a legkisebb szám melynek 1000 darab osztója van az a 19 683 000 000 000 a nélkül hogy eddig a naiv módszerrel végigpróbáltuk volna az összes számot eddig. Hiszen ez pont 2^9 * 3^9 * 5^9.

Én ezt nem értem, ez miből látszik?

#2: Jogos kérdés. És tényleg nem igaz ez az állítás.

Pl.: 810 810 000 = 2^4 * 3^4 * 5^4 * 7 * 11 *13

Az osztóinak száma (5+1)*(5+1)*(5+1)*(1+1)*(1+1)*(1+1) = 1000

És ugye 810 810 000 némileg kisebb, mint 19 683 000 000 000.

Sőt a következő számok mind kisebbek, mint 19 683 000 000 000, de pontosan 1000 osztójuk van:

810 810 000

1 995 840 000

3 056 130 000

8 890 560 000

15 558 480 000

44 089 920 000

185 794 560 000

523 197 480 960

1 189 085 184 000

6 449 725 440 000

11 557 907 988 480

Illetve ha nem pont, hanem minimum ezer osztóról van szó, akkor a győztes:

245 044 800 = 2^6 * 3^2 * 5^2 * 7 * 11 * 13 * 17

Ennek (6+1)*(2+1)*(2+1)*(1+1)*(1+1)*(1+1)*(1+1) = 7*3*3*2*2*2*2 = 1008 osztója van.

Először is, sok ilyen szám van egy intervallumban. A legkisebb ilyen számokat highly composite numbernek (nagyon összetett számok?) nevezik.

„Ramanujan (1915) listed 102 highly composite numbers up to 6746328388800, but omitted 293318625600.”

[link]

Vigasztaljon az a tudat, hogy a 100 évvel ezelőtt a világ legokosabb embere nem tudta volna ezt megoldani :D (Kivéve persze, ha direkt hagyta ki ezt a számot, és nem véletlenül.)

Az oldal szerint amúgy van egy olyan megoldás, amelyre

1: a prímtényezők egymás utáni prímek

2: a prímkitevők monoton csökkenő sorozat

3: az utolsó prímkitevő 1 (kivéve N=4,36)

- - -

Egy viszonylag jó becslést nem nehéz találni.

Keresd a számodat 2^a*3^b*5*c*... alakban.

Legyen A=a+1, sít.

Ekkor A*B*C*.. -t akarod maximalizálni, úgy, hogy

2^a*3^b*5*c*.. <= n,

azaz

A*ln2 + B*ln3 + C*ln5 + .. <= ln(n)+ln2+ln3+..

Vagyis egész számokat keresel úgy, hogy egy adott egyhós lineáris kombinációjuk kisebb (feltehetjük hogy egyenlő) legyen egy adott korlátnál, és a szorzatuk legyen maximális. A szorzatot meg az A*ln2, B*ln3 stb számokra felírt számtani mértanival becsülheted felülről, egyenlőség kb akkor van, ha

A*ln2 =~ B*ln3 =~ ..

- - -

Száz szónak is egy a vége, a 2^a*3^b*5*c*.. alakú számokat kell végigpróbálgatnod (esetleg: monoton csökkenő prímkitevőkkel), ebből nincsen olyan sok. Ha nagyon nagyok a számaid és kevés az erőforrásod, akkor becslésekkel kidobod egy részüket. Ha kicsik a számaid, akkor meg kikeresed katalógusból.

Ja, amúgy itt egy lista:

[link]

Ebben a listában az az első tízezer szám szerepel, amiknek több osztójuk van, mint a listában őt megelőző számnak. Tehát ha 1000-ig keresed azt a számot, aminek a legtöbb osztója van, kikeresed a listán a legnagyobb, de 1000-nél nem nagyobb számot – 840 –, és ez lesz a keresett számod. (Lehet van több olyan szám is, ami ezen kikeresett szám és az intervallumod teteje között van, és ugyanannyi osztója van, de ez lesz a legkisebb.)

„Ebben a listában az az első tízezer szám szerepel, amiknek több osztójuk van, mint a listában őt megelőző számnak.”

[link]

#6: Trollkodunk? Trollkodunk?

Pontosítok akkor: A listán az adott helyen az a szám szerepel, ami a legkisebb olyan szám, aminek több osztója van, mint a listában előtte álló számnak.

Annyit tennék hozzá, hogy ha n "nagy" akkor kiindulásnak a prímeket összeszorozzuk, míg n-t el nem érjük, - kb. ln(n)-ig, - aztán a legnagyobb prímek rovására (lecserélésével), a kisebb prímek kitevőjét növeljük. (Ahogy #4 is írta.)

Pl. ha n=10^100 akkor a legtöbb osztójú:

9326516884061827509233332641260520263537022401378881409790204489294728443343865526159430547438720000 = 2^10 * 3^6 * 5^4 * 7^4 * 11^2 * 13^2 * 17^2 * 19^2 * 23^2 * 29 * 31 * 37 * ... * 199 * 211

ln(10^100) ~ 231 (valójában 241-ig belefér), és párat a legnagyobbak közül beáldoztunk a kisebb prímek kitevőinek növeléséhez.