主题
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。

参见

高度合成数, 圆整数字, 粗糙数, 半素数

使用 Wolfram|Alpha 探索

参考文献

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 在 “整数序列在线百科全书” 中。

在 Wolfram|Alpha 中被引用

平滑数

请引用为

Weisstein, Eric W. “平滑数。” 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/SmoothNumber.html

主题分类