Are there any simple algorithms for computing the Möbius function of any number? The other questions on this topic do not answer this. How do I find the answer without prime factorizing?
Asked
Active
Viewed 56 times
1
-
2$$\mu(n) = \sum_{\stackrel{1\le k \le n }{ \gcd(k,,n)=1}} e^{2\pi i \frac{k}{n}}$$ is one way to do it. Not the fastest, but it's one way to do it. – Brevan Ellefsen Apr 02 '17 at 22:55
-
It is not easy to compute $\mu(n)$ for a single $n$. My favorite one is to compute $M(n) = \sum_{k \le n} \mu(k)$ and $M(n+1)$ with the formula $ \sum_{k=1}^n M(n/k) = 1$. It is highly recursive and encodes everything about the Riemann hypothesis. – reuns Apr 02 '17 at 23:25
-
@BrevanEllefsen Indeed $\sum_{1\le k \le n , \gcd(k,,n)=1} e^{2\pi i \frac{k}{n}} = \sum_{d | n}\mu(d)\sum_{1\le k \le n/d } e^{2\pi i \frac{k d}{n}}$ and so this formula is more or less the same as $\sum_{d | n} \mu(d)= 0$ which means we are really factorizing $n$ – reuns Apr 02 '17 at 23:28
-
Are there any other ways to do it? It gets a little complicated with the less-than/equal-to functions. I am looking to explain this to someone with very little math experience, and I'm not sure how. – I_Am_The_Ion_Man Apr 05 '17 at 00:16