Problem 3003. Mobius function
For any positive integer n, define μ(n) as the sum of the primitive n-th roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:
- μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
- μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
- μ(n) = 0 if n has a squared prime factor.
Return numbers from the Mobius function sequence corresponding to the supplied indices. For example, if n = 3:7, your function should return [-1, 0, -1, 1, -1].
Hint: solving Problem 3001 and Problem 3002 will provide much of the code needed for this problem. You'll need to add prime numbers to the sphenic number set (resulting from Problem 3001).
Solution Stats
Problem Comments
-
3 Comments
Jan Orwat
on 11 Feb 2015
Hello Grant. It's a nice set, but for problems 3001 and 3002 lookup tables are "always win" solutions. For this problem you can avoid this by using some randomness in the test suite.
goc3
on 11 Feb 2015
I'm glad you like them, and thanks for the feedback. I just added a random test case to all three problems.
rifat
on 11 Feb 2015
Yeah, the series is good. After a few rounds of spam-storm, Cody seems to be back on track...
Solution Comments
Show commentsProblem Recent Solvers50
Suggested Problems
-
Project Euler: Problem 2, Sum of even Fibonacci
2292 Solvers
-
Back to basics 22 - Rotate a matrix
901 Solvers
-
804 Solvers
-
253 Solvers
-
4633 Solvers
More from this Author139
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!