Hladké číslo

Hladké číslo je pojem z teorie čísel. Jako B-hladké se označuje takové celé číslo, že žádný z jeho prvočíselných dělitelů není větší než B.

Například číslo 1620 má prvočíselný rozklad 2² × 3⁴ × 5, je tedy 5hladké, neboť žádný z jeho prvočíselných dělitelů není větší než 5. Jedná se také například o číslo 11hladké nebo 6hladké (na mez B není kladena podmínka, aby byla prvočíselná), ale nejedná se o číslo 4hladké, protože má dělitele 5, který je větší než 4.

Použití

Hladká čísla jsou významná pro běh a analýzu různých algoritmů z teorie čísel. Příkladem jsou Pollardův p-1 algoritmus pro počítání prvočíselného rozkladu nebo Pohligův-Hellmanův algoritmus pro výpočet diskrétního logaritmu.

Rozložení hladkých čísel

Označíme-li $\mathrm{\Psi }(x,y)$ počet yhladkých celých čísel menších nebo rovných x a zvolíme-li B pevné a malé, pak platí následující odhad $\psi (x,B)$

$\mathrm{\Psi }(x,B)\sim \frac{1}{\pi (B)!}\prod _{p\le B}\frac{\log x}{\log p}.$

Pokud definujeme parametr $u$ rovností $x=y^u$, tedy $u=\frac{\log x}{\log y}$, pak platí

$\mathrm{\Psi }(x,y)=x\cdot \rho (u)+O\left(\frac{x}{\log y}\right)$

kde $\rho (u)$ je Dickmanova funkce.

Posloupnosti

Pro dané B můžeme uvažovat posloupnost přirozených Bhladkých čísel. Několik takových posloupností pro malá B je zahrnuto v On-line encyklopedii celočíselných posloupností:

• 2hladká čísla: A000079
• 3hladká čísla: A003586
• 5hladká čísla: A051037
• 7hladká čísla: A002473
• 11hladká čísla: A51038
• 13hladká čísla: A80197
• 17hladká čísla: A80681
• 19hladká čísla: A80682
• 23hladká čísla: A80683