Körülbelül mekkora az a legkisebb pozitív egész szám, amelyiknek legalább 10^100 pozitív osztója van?

Nem lehet, hogy itt 10^100 faktoriálisáról van szó? Annak éppen ennyi osztója van.

Ennek a nagyságrendje 10^(10^102) körül van.

Amit előbb írtam, az a pontos értéke az első 333 prímszám szorzatának. (Egy másik gyk.hu kérdéshez csináltam egy programot nemrég, azzal számoltam ki.)

Ha közelítő érték kell valamilyen elméleti megfontolásból, akkor érdemes rákeresni a primoriálisra (primorial). Ez a faktoriálishoz hasonló függvény, de csak a prímeket szorozza össze. A jele p#, az összes p-nél kisebb-egyenlő prímek szorzatát jelenti:

  n

 Π p(k) = p(n)#

k=1

Itt van egy nagyon jó tételgyüjtemény sokféle prímmel kapcsolatos függvényhez:

[link]

Ebben pl. a 4. tétel (3.14 és 3.15 összefüggések) foglalkozik a prímek szorzatával (illetve a szorzat logaritmusával). Primoriális jelöléssel a lényege ez:

  p# ≈ e^p

A jelen esetben p(333) = 2239, így a prímek szorzatára ez a becslés adódik:

2339# ≈ e^2239 = 2.4285 × 10^972

A pontos érték, ami az előző válaszomból kiszámolható, 1.6501 × 10^942, szóval a becslés jó 50 számjegyet téved...

A 4. tétel szerinti egyenlőtlenségekkel számolva ez jön ki:

e^(p·(1 - 1/(2·ln p)) < p# < e^(p·(1 + 1/(2·ln p))

2.27130 × 10^909 < 2239# < 2.59666 × 10^1035

Vagy ugyanott a 29. tétel (6.6 összefüggés) ad egy élesebb közelítést p>1451 esetére:

e^(p·(1 - 0.31/ln p) < p# < e^(p·(1 + 0.31/ln p)

2.02918 × 10^933 < 2239# < 2.90649 × 10^1011

Csináltam egy programot, ami kiszámolja az osztók számát 1-től kezdve minden számra, és kiírja, amikor d(n) nagyobb lesz, mint a korábbi n-ekhez tartozó d(n)-ek. Ilyen sorozat jött ki n = egymillióig:

2 divisors of 2 = 2

3 divisors of 4 = 2^2

4 divisors of 6 = 2 * 3

6 divisors of 12 = 2^2 * 3

8 divisors of 24 = 2^3 * 3

9 divisors of 36 = 2^2 * 3^2

10 divisors of 48 = 2^4 * 3

12 divisors of 60 = 2^2 * 3 * 5

16 divisors of 120 = 2^3 * 3 * 5

18 divisors of 180 = 2^2 * 3^2 * 5

20 divisors of 240 = 2^4 * 3 * 5

24 divisors of 360 = 2^3 * 3^2 * 5

30 divisors of 720 = 2^4 * 3^2 * 5

32 divisors of 840 = 2^3 * 3 * 5 * 7

36 divisors of 1260 = 2^2 * 3^2 * 5 * 7

40 divisors of 1680 = 2^4 * 3 * 5 * 7

48 divisors of 2520 = 2^3 * 3^2 * 5 * 7

60 divisors of 5040 = 2^4 * 3^2 * 5 * 7

64 divisors of 7560 = 2^3 * 3^3 * 5 * 7

72 divisors of 10080 = 2^5 * 3^2 * 5 * 7

80 divisors of 15120 = 2^4 * 3^3 * 5 * 7

84 divisors of 20160 = 2^6 * 3^2 * 5 * 7

90 divisors of 25200 = 2^4 * 3^2 * 5^2 * 7

96 divisors of 27720 = 2^3 * 3^2 * 5 * 7 * 11

100 divisors of 45360 = 2^4 * 3^4 * 5 * 7

108 divisors of 50400 = 2^5 * 3^2 * 5^2 * 7

120 divisors of 55440 = 2^4 * 3^2 * 5 * 7 * 11

128 divisors of 83160 = 2^3 * 3^3 * 5 * 7 * 11

144 divisors of 110880 = 2^5 * 3^2 * 5 * 7 * 11

160 divisors of 166320 = 2^4 * 3^3 * 5 * 7 * 11

168 divisors of 221760 = 2^6 * 3^2 * 5 * 7 * 11

180 divisors of 277200 = 2^4 * 3^2 * 5^2 * 7 * 11

192 divisors of 332640 = 2^5 * 3^3 * 5 * 7 * 11

200 divisors of 498960 = 2^4 * 3^4 * 5 * 7 * 11

216 divisors of 554400 = 2^5 * 3^2 * 5^2 * 7 * 11

224 divisors of 665280 = 2^6 * 3^3 * 5 * 7 * 11

240 divisors of 720720 = 2^4 * 3^2 * 5 * 7 * 11 * 13

Aztán megkerestem ezt a sorozatot az On-line Encyclopedia of Integer Sequences-ben:

[link]

és kiderült, hogy az ilyen számoknak Highly Composite Number a neve. A híres Ramanujan vizsgálta őket intenzíven 100 évvel ezelőtt, és "persze" Erdősnek is vannak tételei HCN-ekkel kapcsolatban.

Szóval az a HCN kell neked, aminek 10^100 osztója van.

Az első 1200 HCN listája itt van:

[link]

de az utolsónak is csak 4×10^15 osztója van.

Itt sok érdekesség van a HCN-ekről:

[link]

És találtam egy jó cikket a HCN-ek generálásáról is:

[link]

Ramanujan munkái között biztos lesz közelítő képlet is a d(N)-re:

[link]

Találtam egy nagyon jó módszert a közelítésre:

A HCN-eknél szigorúbb feltételt teljesítő számokat is vizsgált Ramanujan: Superior Highly Composite Numbers, SHCN.

Ezek is HCN-ek, vagyis az osztóik száma több, mint bármelyik kisebb szám osztóinak a száma, de ezen felül saját magukhoz relatívan nézve is több az osztók száma.

[link]

Ritkábban jönnek, mint a HCN-ek. Két egymást követő HCN hányadosa biztos, hogy legfeljebb 2 lehet (tipikusan p/q, vagyis két prím hányadosa, ami egy 1-nél kicsivel nagyobb szám), ezzel szemben két egymást követő SHCN hányadosa egy prímszám, legtöbbször egy közepesen nagy (mondjuk 10^4 nagyságrensdű) prím.

Viszont nagyon jó tulajdonságuk, hogy sokkal könnyebb generálni őket! Sőt, generálható az egymást követő SHCN-ek hányadosa is (ami mindig egy prím). Itt van egy link az első 10000 ilyen prímre:

[link]

Letöltöttem ezt a listát és kibővítettem a programomat, hogy tudja kezelni őket. Közel sem kell 10ezer SHCN, hogy az osztók száma 10^100 legyen, már a 366-odik SHCN is olyan. Maga a szám 4.851650×10^917, az osztók száma pedig 1.023023×10^100.

Az ezt megelőző SHCN a 2.363200×10^914, annak 5.115117×10^99 osztója van. A kettő között van egy csomó HCN, azok valamelyike lenne a pontos keresett érték, de azokat nem lehet kiszámolni gyorsan. Közelítésnek viszont ez az 5×10^917 nagyságrend is nagyon jó.

A primoriálisos közelítéshez (2239# = 1.6501 × 10^942) képest nem is olyan nagy a változás... Ezt meg lehet érteni, ha kiírjuk ennek az SHCN számnak (4.851650×10^917) a prímtényezős felbontását:

2^15 * 3^9 * 5^6 * 7^5 * 11^4 * 13^3 * 17^3 * 19^3 * 23^3 * 29^2 * 31^2 * 37^2 * 41^2 * 43^2 * 47^2 * 53^2 * 59^2 * 61^2 * 67^2 * 71^2 * 73^2 * 79^2 * 83^2 * 89 * 97 * 101 * 103 * 107 * 109 * ... * 2039 * 2053

ahol a ... helyén van az összes 109 és 2039 közé eső prímszám első hatványa. Vagyis alig néhány prímnek van 1-nél nagyobb hatványa, tehát a szám nagyon hasonlít a 2239 pontosabban 2053 primoriálishoz.

Szóval a pontos érték 10^914 és 10^918 közé esik, de a primoriálissal sokkal egyszerűbben számolható a 10^942-es közelítő érték.