主題
Search

平滑數

一個 整數 如果沒有大於 >k 的 素因子，則稱其為 k-平滑數。下表給出了對於小的 k 的前幾個 k-平滑數。Berndt (1994, p. 52) 將 7-平滑數稱為“高度合成數”。

kOEISk-平滑數
2A0000791, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...
3A0035861, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, ...
5A0510371, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...
7A0024731, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, ...
11A0510381, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, ...

隨機 正整數 <=n 是 k-平滑數的機率為 psi(n,k)/n，其中 psi(n,k) 是小於等於 <=n 的 k-平滑數的數量。這一事實在 Kraitchik 費馬分解法的擴充套件應用中很重要，因為它與為了找到一個合適的子集（其乘積是平方數）而必須檢查的隨機數的數量有關。

由於大約需要找到 pi(k) 個 k-平滑數（其中 pi(k) 是 素數計數函式），因此必須檢查的隨機數數量約為 pi(k)n/psi(n,k)。但是因為使用 試除法 確定一個數字是否為 k-平滑數大約需要 pi(k) 步，所以找到一個乘積為平方數的數字子集所需的預期步數約為 ∼[pi(k)]^2n/psi(n,k) (Pomerance 1996)。Canfield et al. (1983) 表明，當以下條件成立時，此函式最小化：

k∼exp(1/2sqrt(lnnlnlnn))
(1)

並且最小值約為

exp(2sqrt(lnnlnlnn)).
(2)

在 連分數分解演算法 中，n 可以取為 2sqrt(n)，但在 費馬分解法 中，它為 n^(1/2+epsilon)。k 是 因子基 中最大 素數 的估計值 (Pomerance 1996)。

這個奇特的現象

11859210 approx 11859211-> 7×13×19^4 approx 2×3^4×5×11^4-> 91×19^4 approx 10×33^4-> 9.1 approx (33^4)/(19^4)-> 9.1^(1/4) approx 33/19
(3)

涉及最大的連續 19-平滑數，11859210 和 11859211。

參見

高度合成數, 圓整數字, 粗糙數, 半素數

使用 探索

參考文獻

Berndt, B. C. 拉馬努金的筆記本，第四部分。 紐約: Springer-Verlag, 1994.Blecksmith, R.; McCallum, M.; and Selfridge, J. L. "整數的 3-平滑表示。" 美國數學月刊 105, 529-543, 1998.Canfield, E. R.; Erdős, P.; and Pomerance, C. "關於 Oppenheim 關於 'Factorisation Numerorum' 的問題。" J. Number Th. 17, 1-28, 1983.Mintz, D. J. "2, 3 序列作為二元混合物。" Fib. Quart. 19, 351-360, 1981.Pomerance, C. "平滑數在數論演算法中的作用。" In 國際數學家大會論文集，蘇黎世，瑞士，1994 年，第 1 卷 (Ed. S. D. Chatterji). 巴塞爾: Birkhäuser, pp. 411-422, 1995.Pomerance, C. "兩種篩法的傳說。" Not. Amer. Math. Soc. 43, 1473-1485, 1996.Ramanujan, S. 斯里尼瓦薩·拉馬努金的論文集 (Ed. G. H. Hardy, P. V. S. Aiyar, and B. M. Wilson). 普羅維登斯，羅德島州: Amer. Math. Soc., p. xxiv, 2000.Sloane, N. J. A. 序列 A000079/M1129, A002473/M0477, A003586, A051037, 和 A051038 在 “整數序列線上百科全書” 中。

在 中被引用

平滑數

請引用為

Weisstein, Eric W. “平滑數。” 來自 --一個 資源。 https://mathworld.tw/SmoothNumber.html

主題分類