From the http://documents.wolfram.com/v5/Add-onsLinks/StandardPackages/NumberTheory/NumberTheoryFunctions.html [Broken]:(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Computing the Möbius function

Loading...

Similar Threads - Computing Möbius function | Date |
---|---|

A 4th order tensor inverse and double dot product computation | May 10, 2017 |

I How to Compute the EOFs by SVD? | Apr 20, 2016 |

I Some questions about eigenvector computation | Apr 12, 2016 |

Möbius inversion and number theory question | Mar 7, 2011 |

**Physics Forums - The Fusion of Science and Community**