主題
Search

無平方因子數

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
Squarefree

如果一個數的素數分解不包含重複的因子，則稱該數為無平方因子數（有時也稱為 quadratfrei；Shanks 1993）。因此，所有的素數顯然都是無平方因子數。按照慣例，數字 1 也被認為是無平方因子數。無平方因子數包括 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, ... (OEIS A005117)。含平方因子數（即，包含至少一個平方因子的數）包括 4, 8, 9, 12, 16, 18, 20, 24, 25, ... (OEIS A013929)。

Wolfram 語言函式SquareFreeQ[n] 確定一個數是否為無平方因子數。請注意，出於技術原因，Wolfram 語言將 1 視為無平方因子數，這個慣例與當 mu(n)!=0 時定義一個數為無平方因子數是一致的，其中 mu(n) 是莫比烏斯函式。因此，數字 1 有一個有點奇怪的特點，即它同時是完全平方數和無平方因子數。

令 q(n)=1 其中 n 是無平方因子數，且 q(n)=0 其中 n 包含一個或多個平方因子，使得 q(n)=|mu(n)|。那麼

sum_(n=1)^(infty)(q(n))/(n^s)=sum_(n=1)^(infty)(|mu(n)|)/(n^s)
(1)
=(zeta(s))/(zeta(2s))
(2)

對於 s>1，且 zeta(s) 是黎曼 zeta 函式（Hardy 和 Wright 1979, p. 255）。

SquarefreeDensityPlot

上面繪製了前 10^4 個整數的值在一個 100×100 的網格上，其中無平方因子數值以白色顯示。清晰的模式顯現出來，其中數字的倍數各自共享一個或多個重複因子。

目前還沒有已知的多項式時間演算法來識別無平方因子整數或計算整數的無平方因子部分。事實上，這個問題可能不比整數分解的一般問題更容易（顯然，如果一個整數 n 可以完全分解，則 n 是無平方因子數 當且僅當 它不包含重複的因子）。這個問題是數論中一個重要的未解決問題，因為計算代數數域的整數環可以歸結為計算整數的無平方因子部分（Lenstra 1992, Pohst 和 Zassenhaus 1997）。

Sylvester 序列中小於 2.5×10^(15) 的所有數字都是無平方因子數，並且在該序列中尚未發現含平方因子數 (Vardi 1991)。每個卡邁克爾數都是無平方因子數。二項式係數 (2n-1; n) 僅當 n=2, 3, 4, 6, 9, 10, 12, 36, ... 時才是無平方因子數，並且在小於 n=1500 的範圍內沒有其他值。中心二項式係數僅當 n=1, 2, 3, 4, 5, 7, 8, 11, 17, 19, 23, 71, ... (OEIS A046098) 時才是無平方因子數，並且在小於 1500 的範圍內沒有其他值。

令 Q(n) 為小於 <n 的正無平方因子數的數量（Hardy 和 Wright 1979, p. 251）。那麼對於 n=1, 2, ...，前幾個值是 0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 8, 9, 10, 11, 11, ... (OEIS A013928)。Q(n) 的和包括

Q(n)=sum_(k=1)^(n-1)mu^2(k)
(3)
=sum_(k=1)^(n-1)|mu(k)|
(4)
=sum_(d=1)^(sqrt(n-1))mu(d)|_(n-1)/(d^2)_|
(5)
=sum_(k=1)^(n-1)mu(n-k) (mod 2)
(6)
=sum_(k=1)^(n-1)|mu(n-k)|,
(7)

其中 mu(n) 是莫比烏斯函式。

SquarefreeFraction

無平方因子數 <=n 的漸近數量 Q(n) 由下式給出

Q(n)=(6n)/(pi^2)+O(sqrt(n))
(8)

（Landau 1974, pp. 604-609；Nagell 1951, p. 130；Hardy 和 Wright 1979, pp. 269-270；Hardy 1999, p. 65）。因此，漸近密度為 1/zeta(2)=6/pi^2 approx 0.607927 (OEIS A059956；Wells 1986, p. 28；Borwein 和 Bailey 2003, p. 139)，其中 zeta(n) 是黎曼 zeta 函式。Q(n) 對於 n=10, 100, 1000, ... 的值分別為 7, 61, 608, 6083, 60794, 607926, 6079291, 60792694, 607927124, 6079270942, ... (OEIS A071172)。

類似地，無平方因子高斯整數的漸近密度由 6/(pi^2K)=0.66370... (OEIS A088454) 給出，其中 K 是卡塔蘭常數（Pegg；Collins 和 Johnson 1989；Finch 2003, p. 601）。

莫比烏斯函式由下式給出

mu(n)={0 if n has one or more repeated prime factors; 1 if n=1; (-1)^k if n is product of k distinct primes,
(9)

因此 mu(n)!=0 表示 n 是無平方因子數。Q(x) 的漸近公式等價於公式

sum_(n=1)^x|mu(n)|=(6x)/(pi^2)+O(sqrt(x))
(10)

（Hardy 和 Wright 1979, p. 270）

SquarefreeConsecutiveFraction

令 Q_2(n) 為滿足 (k,k+1) 且 k<=n 的連續數對 (k,k+1) 的數量，其中 k 和 k+1 都是無平方因子數。Q_2(10^n) 對於 n=0, 1, ... 的值分別為 1, 5, 33, 323, 3230, 32269, 322619, 3226343, 32263377, 322634281, 3226340896, ... (OEIS A087618)。那麼 Q_2(n)/n 的漸近值由下式給出

product_(n=1)^(infty)(1-2/(p_n^2))=2F-1
(11)
=0.3226340989...
(12)

（OEIS A065474；Carlitz 1932, Heath-Brown 1984），其中 p_n 是第 n 個素數，F 是 Feller-Tornier 常數。

另請參閱

二項式係數, 無四次冪因子數, 無憂偶, 合數, 無立方因子數, Erdős 無平方因子猜想, Feller-Tornier 常數, 斐波那契數, Korselt 判據, 莫比烏斯函式, 素數, 黎曼 Zeta 函式, Sárkőzy 定理, 平方數, 無平方因子分解, 無平方因子部分, 含平方因子數, Sylvester 序列 在 課堂中探索這個主題

使用 探索

參考文獻

Bellman, R. and Shapiro, H. N. "The Distribution of Squarefree Integers in Small Intervals." Duke Math. J. 21, 629-637, 1954.Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.Carlitz, L. "On a Problem in Additive Arithmetic. II." Quart. J. Math. 3, 273-290, 1932.Collins, G. E. and Johnson, J. R. "The Probability of Relative Primality of Gaussian Integers." Proc. 1988 Internat. Sympos. Symbolic and Algebraic Computation (ISAAC), Rome (Ed. P. Gianni). New York: Springer-Verlag, pp. 252-258, 1989.Finch, S. R. Mathematical Constants. Cambridge, England: Cambridge University Press, 2003.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. and Wright, E. M. "The Number of Squarefree Numbers." §18.6 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 269-270, 1979.Heath-Brown, D. R. "The Square Sieve and Consecutive Square-Free Numbers." Math. Ann. 266, 251-259, 1984.Landau, E. Handbuch der Lehre von der Verteilung der Primzahlen, 3rd ed. New York: Chelsea, 1974.Lenstra, H. W. Jr. "Algorithms in Algebraic Number Theory." Bull. Amer. Math. Soc. 26, 211-244, 1992.Nagell, T. Introduction to Number Theory. New York: Wiley, p. 130, 1951.Pegg, E. Jr. "The Neglected Gaussian Integers." http://www.mathpuzzle.com/Gaussians.html.Pohst, M. and Zassenhaus, H. Algorithmic Algebraic Number Theory. Cambridge, England: Cambridge University Press, p. 429, 1997.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 114, 1993.Sloane, N. J. A. Sequences A005117/M0617, A013928, A013929, A046098, A059956, A065474, A071172, A087618, and A088454 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. "Are All Euclid Numbers Squarefree?" §5.1 in Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 7-8, 82-85, and 223-224, 1991.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, 1986.

在 中被引用

無平方因子數

請引用為

Weisstein, Eric W. “無平方因子數。” 來自 Web 資源。 https://mathworld.tw/Squarefree.html

學科分類