Squarefree

A number is said to be squarefree (or sometimes Quadratfrei; Shanks 1993) if its Prime decomposition contains norepeated factors. All Primes are therefore trivially squarefree. The squarefree numbers are 1, 2, 3, 5, 6, 7, 10, 11, 13,14, 15, ... (Sloane's A005117). The Squareful numbers (i.e., those that contain at least one square) are 4, 8, 9, 12,16, 18, 20, 24, 25, ... (Sloane's A013929).

The asymptotic number of squarefree numbers is given by

(1)

The Möbius Function is given by

(2)

(3)

There is no known polynomial-time algorithm for recognizing squarefree Integers or for computing thesquarefree 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 analgebraic number field is reducible to computing the squarefree part of an Integer (Lenstra 1992, Pohst and Zassenhaus1997). The Mathematica (Wolfram Research, Champaign, IL) function NumberTheory`NumberTheoryFunctions`SquareFreeQ[n] determines whether a number is squarefree.

All numbers less than in Sylvester'sSequence are squarefree, and no Squareful numbers in this sequence are known (Vardi 1991). Every CarmichaelNumber 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, ... (Sloane's A046098), withno others less than 1500.

References

Bellman, R. and Shapiro, H. N. ``The Distribution of Squarefree Integers in Small Intervals.'' Duke Math. J. 21, 629-637, 1954.

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.

Lenstra, H. W. Jr. ``Algorithms in Algebraic Number Theory.'' Bull. Amer. Math. Soc. 26, 211-244, 1992.

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.A013929,A046098, andA005117/M0617in ``An On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html.

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.

• Just One
• Kabon Triangles
• Kac Formula
• Kac Matrix
• Kakeya Needle Problem
• Kakutani's Fixed Point Theorem
• Kakutani's Problem
• Kalman Filter
• Kampyle of Eudoxus
• KAM Theorem
• Kanizsa Triangle
• Kantorovich Inequality
• Kaplan-Yorke Conjecture
• Kaplan-Yorke Dimension
• Kaplan-Yorke Map
• Kappa Curve
• Kaprekar Number
• Kaprekar Routine
• Kaps-Rentrop Methods
• Kapteyn Series
• Karatsuba Multiplication
• k-ary Divisor
• Katona's Problem
• Kauffman Polynomial F
• Kauffman Polynomial X