Hladké číslo

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 5-hladké, neboť žádný z jeho prvočíselných dělitelů není větší než 5. Jedná se také například o číslo 11-hladké nebo 6-hladké (na mez B není kladena podmínka, aby byla prvočíselná), ale nejedná se o číslo 4-hladké, protože má dělitele 5, který je větší než 4.

Použití[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Označíme-li \scriptstyle \Psi(x,y) počet y-hladkých celých čísel menších nebo rovných x azvolíme-li B pevné a malé, pak platí následující odhad \scriptstyle\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 = 'yu, tedy u = log x / log y, pak platí

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

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

Posloupnosti[editovat | editovat zdroj]

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

V tomto článku byl použit překlad textu z článku smooth number na anglické Wikipedii.