TOPICS

# 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 , where is the Möbius function. The number 1 therefore has the somewhat curious distinction of being simultaneously a perfect square and squarefree.

Let where is squarefree and where contains one or more squares, so that . Then

 (1) (2)

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

The values of the first integers are plotted above on a 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 can be factored completely, 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 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 are squarefree only for , 3, 4, 6, 9, 10, 12, 36, ..., with no others less than . The central binomial coefficients are squarefree only for , 2, 3, 4, 5, 7, 8, 11, 17, 19, 23, 71, ... (OEIS A046098), with no others less than 1500.

Let be the number of positive squarefree numbers (Hardy and Wright 1979, p. 251). Then for , 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 include

 (3) (4) (5) (6) (7)

where is the Möbius function.

The asymptotic number of squarefree numbers is given by

 (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 (OEIS A059956; Wells 1986, p. 28; Borwein and Bailey 2003, p. 139), where is the Riemann zeta function. The values of for , 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 (OEIS A088454), where is Catalan's constant (Pegg; Collins and Johnson 1989; Finch 2003, p. 601).

The Möbius function is given by

 (9)

so indicates that is squarefree. The asymptotic formula for is equivalent to the formula

 (10)

(Hardy and Wright 1979, p. 270)

Let be the number of consecutive numbers with such that and are both squarefree. for , 1, ... are given by 1, 5, 33, 323, 3230, 32269, 322619, 3226343, 32263377, 322634281, 3226340896, ... (OEIS A087618). Then is given asymptotically by

 (11) (12)

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

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

More things to try:

## 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.

Squarefree

## Cite this as:

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