- #1

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

From the http://documents.wolfram.com/v5/Add-onsLinks/StandardPackages/NumberTheory/NumberTheoryFunctions.html [Broken]:

SquareFreeQ[n] checks to see if n has a square prime factor. This is done by computing MoebiusMu[n] and seeing if the result is zero; if it is, then n is not squarefree, otherwise it is. Computing MoebiusMu[n] involves finding the smallest prime factor q of n. If n has a small prime factor (less than or equal to 1223), this is very fast. Otherwise, FactorInteger is used to find q.

How does this work? I can't think of a way to compute mu(n) faster than:

* finding a small p for which p^2 | n, or

* finding that n is prime, or

* checking that for all p < (n)^(1/3), p^2 does not divide n

* factoring n, which can be faster than the third option for large n

Edit: I checked my copy of "Open problems in number theoretic complexity, II", which has O8: Is SQUAREFREES in P? Assuming that this is still open, any algorithm known would either be superpolynomial or of unproven complexity. But even an exponential-time improvement on the naive algorithm would be of interest.

SquareFreeQ[n] checks to see if n has a square prime factor. This is done by computing MoebiusMu[n] and seeing if the result is zero; if it is, then n is not squarefree, otherwise it is. Computing MoebiusMu[n] involves finding the smallest prime factor q of n. If n has a small prime factor (less than or equal to 1223), this is very fast. Otherwise, FactorInteger is used to find q.

How does this work? I can't think of a way to compute mu(n) faster than:

* finding a small p for which p^2 | n, or

* finding that n is prime, or

* checking that for all p < (n)^(1/3), p^2 does not divide n

* factoring n, which can be faster than the third option for large n

Edit: I checked my copy of "Open problems in number theoretic complexity, II", which has O8: Is SQUAREFREES in P? Assuming that this is still open, any algorithm known would either be superpolynomial or of unproven complexity. But even an exponential-time improvement on the naive algorithm would be of interest.

Last edited by a moderator: