Problem 3003. Mobius function

Created by goc3

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>From</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"\"><w:r><w:t>wikipedia</w:t></w:r></w:hyperlink><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>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:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>μ(n) = 0 if n has a squared prime factor.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Return numbers from the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"\"><w:r><w:t>Mobius function sequence</w:t></w:r></w:hyperlink><w:r><w:t> corresponding to the supplied indices. For example, if n = 3:7, your function should return [-1, 0, -1, 1, -1].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Hint: solving</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/3001-sphenic-number-sequence\"><w:r><w:t>Problem 3001</w:t></w:r></w:hyperlink><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/3002-not-square-free-number-sequence\"><w:r><w:t>Problem 3002</w:t></w:r></w:hyperlink><w:r><w:t> 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).</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; "><div style="block-size: 256.3px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 128.15px; transform-origin: 407px 128.15px; vertical-align: baseline; "><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 16.5px 8px; transform-origin: 16.5px 8px; unicode-bidi: normal; ">From<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; "> <a target='_blank' href = "/#null">wikipedia</a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; ">:</div><div style="block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 380px 8px; transform-origin: 380px 8px; unicode-bidi: normal; ">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:</div><ul style="block-size: 61.3px; counter-reset: list-item 0; font-family: Helvetica, Arial, sans-serif; list-style-type: square; margin-block-end: 20px; margin-block-start: 10px; margin-bottom: 20px; margin-top: 10px; perspective-origin: 391px 30.65px; transform-origin: 391px 30.65px; margin-top: 10px; margin-bottom: 20px; "><li style="block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; ">μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.</li><li style="block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; ">μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.</li><li style="block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; ">μ(n) = 0 if n has a squared prime factor.</li></ul><div style="block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 79px 8px; transform-origin: 79px 8px; unicode-bidi: normal; ">Return numbers from the<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; "> <a target='_blank' href = "/#null">Mobius function sequence</a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 214.5px 8px; transform-origin: 214.5px 8px; unicode-bidi: normal; "> corresponding to the supplied indices. For example, if n = 3:7, your function should return [-1, 0, -1, 1, -1].</div><div style="block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 38px 8px; transform-origin: 38px 8px; unicode-bidi: normal; ">Hint: solving<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; "> <a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/3001-sphenic-number-sequence">Problem 3001</a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 14px 8px; transform-origin: 14px 8px; unicode-bidi: normal; "> and<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; "> <a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/3002-not-square-free-number-sequence">Problem 3002</a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 232.5px 8px; transform-origin: 232.5px 8px; unicode-bidi: normal; "> 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).</div></div></div>

Solve

Solution Stats

94 Solutions
43 Solvers

Last Solution submitted on Mar 21, 2023

Last 200 Solutions

Problem Comments

3 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...

Problem Recent Solvers43

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 3003. Mobius function

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers43

Suggested Problems

More from this Author139

Problem Tags

Community Treasure Hunt

Problem 3003. Mobius function

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers43

Suggested Problems

More from this Author139

Problem Tags

Community Treasure Hunt

Players