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 22 × 34 × 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 \scriptstyle \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)

: \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í : \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: [url=https://oeis. +moreorg/A000079]A000079[/url] * 3hladká čísla: [url=https://oeis. org/A003586]A003586[/url] * 5hladká čísla: [url=https://oeis. org/A051037]A051037[/url] * 7hladká čísla: [url=https://oeis. org/A002473]A002473[/url] * 11hladká čísla: [url=https://oeis. org/A51038]A51038[/url] * 13hladká čísla: [url=https://oeis. org/A80197]A80197[/url] * 17hladká čísla: [url=https://oeis. org/A80681]A80681[/url] * 19hladká čísla: [url=https://oeis. org/A80682]A80682[/url] * 23hladká čísla: [url=https://oeis. org/A80683]A80683[/url].

Reference

Kategorie:Teorie čísel