Meg kellene becsülni, hogy 100000! osztóinak száma kettőnek kb.  hányadik hatványával osztható. Hogyan?

π(N) jelöli az N-nél nem nagyobb prímek számát

d(N) jelöli az N osztóinak a számát (szokták σ₀(N)-nel is jelölni)

Π aᵢ jelöli az a₁·a₂·a₃·... szorzatot természetesen.

Ha az N szám törzstényezős felbontása ez:

N = Π pᵢ^aᵢ

Akkor az N szám osztóinak száma:

d(N) = Π (aᵢ+1)

Ezek a szorzótényezők akkor adnak hozzá bármit is a 2 hatványokhoz, ha aᵢ páratlan!

Kis pᵢ-knél a kitevő eléggé megjósolhatatlan, de nézzük a nagy prímeket.

N = 100000!

Ennek a számnak a prímtényezői 100000-nél kisebbek. A legnagyobb a 99991. Annak a kitevője tuti 1, mert nincs egyetlen másik szám sem a faktoriális tényezői között, aminek ez osztója lenne. Az a prímtényező ezért az osztók számában a 2-nek egy hatványát adja.

Ugyanez igaz a többi nagy prímre is teljesen 50000-ig (50021 az ahhoz legközelebbi prím). 50000 alatt, mondjuk a 49999 már előfordul a 49999 mellett a 99998 = 2·49999-ben is, vagyis a kitevő 2 lesz, ezért az osztók számát ez megháromszorozza (vagyis nem ad semmit a 2 hatványokhoz). Viszont az összes prímnek 50000 és 100000 között 1 a kitevője!

A prímek száma ebben a tartományban π(100000)-π(50000) = 4459, tehát 2^4459-nél nagyobb lesz a becsült kettő hatvány.

100000/3-ig visszafelé menve kettő lesz a kitevő, de már a 33331-es prímszám kitevője 3 lesz, ezért az osztók száma 4-szereződik. Ez igaz az összes 100000/3 és 100000/4 közötti prímre. π(33333)-π(25000) = 807, tehát 2·807-tel emelhetjük a becsült értéket. Ez eddig 4459+2·807 = 6073.

100000/5 és 100000/6 között megint páratlan lesz a kitevő: 5. Azok a prímek darabonként egyet adnak hozzá a 2 hatvány kitevőjéhez. Abban a tartományban már csak 334 prím van. A becslés így 6407-re nő.

A 7-es kitevő izgalmasabb lesz, mert az 8-szorozza az osztók számát, ami 2³. Ez a 100000/7 és 100000/8 közötti tartomány. Ott van 184 prím, a kettő hatványok 3·184-gyel nőnek. 6407+3·184 = 6959.

Ezt így lehetne tovább folytatni, ez megadná a pontos értéket (bár √100000 alatt már kicsit máshogy kell számolni).

Nézzük most alulról is: Mennyi a p₁=2 prím kitevője 100000!-ban?

100000/2 = 50000

100000/4 = 25000

100000/8 = 12500

100000/16 = 6250

100000/32 = 3125

100000/64 = 1562 (lefelé kell kerekíteni)

100000/128 = 781 (lefelé...)

stb. Ezek összege lesz a 2 kitevője. Az látszik, hogy ez a szám pont 100000 lenne, ha nem kellene néha lefelé kerekíteni, de kell. Ezért az összeg kicsit kevesebb lesz. Excel-ben megcsináltam (csak 16 sor volt az egész, hisz 2^17 már több 100000-nél), az összeg 99994. Ez páros szám, nem lesz belőle hatványkitevő a 2-höz az osztók számában.

p₂=3-hoz: Hasonlóan a 3 hatványokkal osztva 100000-et kijön, hogy a 3 kitevője 49995, ami páratlan! Viszont 49996 = 2² · 29 · 431, vagyis csak 2-vel növeli a hatványt az osztóknál.

Ne nézzük tovább, becslésnek valószínű egész jó lesz így a 6961, illetve 7000 körüli érték.

π(x) értékeit a WolframAlpha-val számoltattam ki. Lehet becsülni az x/ln x-szel is, úgy mondjuk az első tartományban 4459 helyett 4064 prímszám jött volna ki, 10% körüli a hiba. Annál több lesz az elhagyottakból...

-----

A pontos értéket a WolframAlpha-val így lehetne kiszámolni:

factor sigma_0(100000!)

Ezt már sajnos nem tudta kiszámolni, olyan 30000! fölött túl sok idő hibaüzenettel leállt. Írtam egy programot, ami kiszámolja, ez lett a pontos eredmény:

Factorization of number of divisors of 100000! = 2^8206 * 3^2725 * 5^863 * 7^439 * 11^176 * 13^120 * 17^74 * 19^64 * 23^40 * 29^31 * 31^26 * 37^16 * 41^14 * 43^13 * 47^8 * 53^9 * 59^6 * 61^5 * 67^5 * 71^7 * 73^4 * 79^3 * 83^2 * 89^2 * 97^4 * 101^8 * 103^3 * 107^3 * 109^2 * 113^2 * 131^2 * 137 * 139 * 149 * 157 * 163 * 167^2 * 191 * 197 * 199 * 223^2 * 233 * 239 * 263 * 269 * 281 * 347^2 * 373 * 397 * 431^2 * 463 * 521 * 617 * 641^2 * 769 * 877 * 1723 * 2083 * 2381 * 2777 * 2857 * 3571 * 4999

Vagyis 8206 a pontos válasz. A 7000-es becslésnek hmm, elég nagy a hibája...

Kipróbáltam 10millió faktoriálisával is. A pontos érték 570693, az 1,8-szoros becslés pedig 568919.

Az 1,8-szoros szorzónak nincs nagy matematikai alapja, de egész jónak tűnik.

Mégiscsak igazolható ez a szorzós dolog is. √N fölötti prímekre ugyanis ilyen felváltva páros-páratlan módszerrel adódik a kettő-hatvány, ahogy írtam. √N alatt már nem, ott eléggé random, hogy páros vagy páratlan jön-e ki. Viszont abból sokkal kevesebb van, és ha páratlan is jön ki, nem adhat hozzá túl sokat a kettő-hatványokhoz, ugyanis mondjuk a p₁=2-nek a kitevője is csak legfeljebb N-1 lehet, ami N-szeres szorzót jelent az osztók számában, ami a kettő-hatványokhoz log₂(N)-et ad csak hozzá. Az pedig kicsi szám.

Vagyis bizonyítható is, hogy C·(π(N) - π(N/2)) jó becslés. C értéke valószínű 1,8 körül van; kis koncentrálással ki lehetne számolni matekosan is, de most nincs kedvem vele foglalkozni :)

Elméletileg nincs különbség a C·π(n) illetve a C·(π(n) - π(n/2)) között, hisz

 lim π(n)/π(n/2) = lim (n/ln(n)) / ((n/2)/ln(n/2)) = 2

n→∞

szóval az egyik C éppen duplája a másiknak.

Kiszámoltam az osztók száma 2-es prímtényezőjének a kitevőjét teljesen 1 milliárd faktoriálisig, ezek jöttek ki:

[link]

Az utolsó két oszlop adja az egyik illetve másik fajta C értékét. 1 milliárdnál már 0,858·π(N), de valószínű még lejjebb menne a nagyobb N-eknél.

Az N/lnN nem becslés a π(n)-re, hanem az aszimptotikus viselkedését írja le. Szóval ha N tart a végtelenhez, akkor

  lim π(N) / (N/lnN) = 1

N→∞

Kis N-ekre nem valami jó, viszont határértékben bizonyítva is van, hogy pontosan ennyi. (Mellesleg N/(lnN-1) határértékben ugyanúgy viselkedik.)

Olvasd el mondjuk ezt:

[link]