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 Ψ ( x , y ) {\displaystyle \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 ψ ( x , B ) {\displaystyle \psi (x,B)}

Ψ ( x , B ) ∼ 1 π ( B ) ! ∏ p ≤ B log ⁡ x log ⁡ p . {\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}

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

Ψ ( x , y ) = x ⋅ ρ ( u ) + O ( x log ⁡ y ) {\displaystyle \Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)}

kde ρ ( u ) {\displaystyle \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

Reference

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