TOPICS
Search

Squarefree


Squarefree

A number is said to be squarefree (or sometimes quadratfrei; Shanks 1993) if its prime decomposition contains no repeated factors. All primes are therefore trivially squarefree. The number 1 is by convention taken to be squarefree. The squarefree numbers are 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, ... (OEIS A005117). The squareful numbers (i.e., those that contain at least one square) are 4, 8, 9, 12, 16, 18, 20, 24, 25, ... (OEIS A013929).

The Wolfram Language function SquareFreeQ[n] determines whether a number is squarefree. Note that for technical reasons, the Wolfram Language considers 1 to be squarefree, a convention that is consistent with defining a number to be squarefree when mu(n)!=0, where mu(n) is the Möbius function. The number 1 therefore has the somewhat curious distinction of being simultaneously a perfect square and squarefree.

Let q(n)=1 where n is squarefree and q(n)=0 where n contains one or more squares, so that q(n)=|mu(n)|. Then

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

for s>1 and zeta(s) is the Riemann zeta function (Hardy and Wright 1979, p. 255).

SquarefreeDensityPlot

The values of the first 10^4 integers are plotted above on a 100×100 grid, with squarefree values shown in white. Clear patterns emerge where multiples of numbers each share one or more repeated factor.

There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer. In fact, this problem may be no easier than the general problem of integer factorization (obviously, if an integer n can be factored completely, n is squarefree iff it contains no duplicated factors). This problem is an important unsolved problem in number theory because computing the ring of integers of an algebraic number field is reducible to computing the squarefree part of an integer (Lenstra 1992, Pohst and Zassenhaus 1997).

All numbers less than 2.5×10^(15) in Sylvester's sequence are squarefree, and no squareful numbers in this sequence are known (Vardi 1991). Every Carmichael number is squarefree. The binomial coefficients (2n-1; n) are squarefree only for n=2, 3, 4, 6, 9, 10, 12, 36, ..., with no others less than n=1500. The central binomial coefficients are squarefree only for n=1, 2, 3, 4, 5, 7, 8, 11, 17, 19, 23, 71, ... (OEIS A046098), with no others less than 1500.

Let Q(n) be the number of positive squarefree numbers <n (Hardy and Wright 1979, p. 251). Then for n=1, 2, ..., the first few values are 0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 8, 9, 10, 11, 11, ... (OEIS A013928). Sums for Q(n) include

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)

where mu(n) is the Möbius function.

SquarefreeFraction

The asymptotic number Q(n) of squarefree numbers <=n is given by

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

(Landau 1974, pp. 604-609; Nagell 1951, p. 130; Hardy and Wright 1979, pp. 269-270; Hardy 1999, p. 65). The asymptotic density is therefore 1/zeta(2)=6/pi^2 approx 0.607927 (OEIS A059956; Wells 1986, p. 28; Borwein and Bailey 2003, p. 139), where zeta(n) is the Riemann zeta function. The values of Q(n) for n=10, 100, 1000, ... are 7, 61, 608, 6083, 60794, 607926, 6079291, 60792694, 607927124, 6079270942, ... (OEIS A071172).

Similarly, the asymptotic density of squarefree Gaussian integers is given by 6/(pi^2K)=0.66370... (OEIS A088454), where K is Catalan's constant (Pegg; Collins and Johnson 1989; Finch 2003, p. 601).

The Möbius function is given by

 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)

so mu(n)!=0 indicates that n is squarefree. The asymptotic formula for Q(x) is equivalent to the formula

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

(Hardy and Wright 1979, p. 270)

SquarefreeConsecutiveFraction

Let Q_2(n) be the number of consecutive numbers (k,k+1) with k<=n such that k and k+1 are both squarefree. Q_2(10^n) for n=0, 1, ... are given by 1, 5, 33, 323, 3230, 32269, 322619, 3226343, 32263377, 322634281, 3226340896, ... (OEIS A087618). Then Q_2(n)/n is given asymptotically by

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

(OEIS A065474; Carlitz 1932, Heath-Brown 1984), where p_n is the nth prime and F is the Feller-Tornier constant.


See also

Binomial Coefficient, Biquadratefree, Carefree Couple, Composite Number, Cubefree, Erdős Squarefree Conjecture, Feller-Tornier Constant, Fibonacci Number, Korselt's Criterion, Möbius Function, Prime Number, Riemann Zeta Function, Sárkőzy's Theorem, Square Number, Squarefree Factorization, Squarefree Part, Squareful, Sylvester's Sequence Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Squarefree

Cite this as:

Weisstein, Eric W. "Squarefree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Squarefree.html

Subject classifications