Möbius function: Difference between revisions
Thundergnat (talk | contribs) m Clarify wording |
Add Factor |
||
Line 31: | Line 31: | ||
=={{header|Factor}}== |
|||
The <code>mobius</code> word exists in the <code>math.extras</code> vocabulary. See the implementation [https://docs.factorcode.org/content/word-mobius%2Cmath.extras.html here]. |
|||
{{works with|Factor|0.99 2020-01-23}} |
|||
<lang factor>USING: formatting grouping io math.extras math.ranges sequences ; |
|||
"First 199 terms of the Möbius sequence:" print |
|||
199 [1,b] [ mobius ] map " " prefix 20 group |
|||
[ [ "%3s" printf ] each nl ] each</lang> |
|||
{{out}} |
|||
<pre> |
|||
First 199 terms of the Möbius sequence: |
|||
1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 |
|||
0 1 1 -1 0 0 1 0 0 -1 -1 -1 0 1 1 1 0 -1 1 1 |
|||
0 -1 -1 -1 0 0 1 -1 0 0 0 1 0 -1 0 1 0 1 1 -1 |
|||
0 -1 1 0 0 1 -1 -1 0 1 -1 -1 0 -1 1 0 0 1 -1 -1 |
|||
0 0 1 -1 0 1 1 1 0 -1 0 1 0 1 1 1 0 -1 0 0 |
|||
0 -1 -1 -1 0 -1 1 -1 0 -1 -1 1 0 -1 -1 1 0 0 1 1 |
|||
0 0 1 1 0 0 0 -1 0 1 -1 -1 0 1 1 0 0 -1 -1 -1 |
|||
0 1 1 1 0 1 1 0 0 -1 0 -1 0 0 -1 1 0 -1 1 1 |
|||
0 1 0 -1 0 -1 1 -1 0 0 -1 0 0 -1 -1 0 0 1 1 -1 |
|||
0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 19:07, 25 January 2020
The classical Möbius function: μ(n) is an important multiplicative function in number theory and combinatorics.
There are several ways to implement a Möbius function.
A fairly straightforward method is to find the prime factors of a positive integer n, then define μ(n) as the sum of the primitive factors. It has the values {−1, 0, 1} depending on the factorization of n:
- μ(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.
- Task
- Write a routine (function, procedure, whatever) μ(n) to find the Möbius number for a positive integer n.
- Use that routine to find and display here, on this page, at least the first 99 terms in a grid layout. (Not just one long line or column of numbers.)
- See also
- Related Tasks
Factor
The mobius
word exists in the math.extras
vocabulary. See the implementation here.
<lang factor>USING: formatting grouping io math.extras math.ranges sequences ;
"First 199 terms of the Möbius sequence:" print 199 [1,b] [ mobius ] map " " prefix 20 group [ [ "%3s" printf ] each nl ] each</lang>
- Output:
First 199 terms of the Möbius sequence: 1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 0 1 1 -1 0 0 1 0 0 -1 -1 -1 0 1 1 1 0 -1 1 1 0 -1 -1 -1 0 0 1 -1 0 0 0 1 0 -1 0 1 0 1 1 -1 0 -1 1 0 0 1 -1 -1 0 1 -1 -1 0 -1 1 0 0 1 -1 -1 0 0 1 -1 0 1 1 1 0 -1 0 1 0 1 1 1 0 -1 0 0 0 -1 -1 -1 0 -1 1 -1 0 -1 -1 1 0 -1 -1 1 0 0 1 1 0 0 1 1 0 0 0 -1 0 1 -1 -1 0 1 1 0 0 -1 -1 -1 0 1 1 1 0 1 1 0 0 -1 0 -1 0 0 -1 1 0 -1 1 1 0 1 0 -1 0 -1 1 -1 0 0 -1 0 0 -1 -1 0 0 1 1 -1 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1
Perl 6
Möbius number is not defined for n == 0. Perl 6 arrays are indexed from 0 so store a blank value at position zero to keep n and μ(n) aligned.
<lang perl6>use Prime::Factor;
sub μ (Int \n) {
my @p = prime-factors(n); +@p == +Bag(@p).keys ?? +@p %% 2 ?? 1 !! -1 !! 0
}
my @möbius = lazy flat ' ', 1, (2..*).map: -> \n { μ(n) };
- The Task
put "Möbius sequence - First 199 terms:\n",
@möbius[^200]».fmt('%3s').rotor(20).join("\n");</lang>
- Output:
Möbius sequence - First 199 terms: 1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 0 1 1 -1 0 0 1 0 0 -1 -1 -1 0 1 1 1 0 -1 1 1 0 -1 -1 -1 0 0 1 -1 0 0 0 1 0 -1 0 1 0 1 1 -1 0 -1 1 0 0 1 -1 -1 0 1 -1 -1 0 -1 1 0 0 1 -1 -1 0 0 1 -1 0 1 1 1 0 -1 0 1 0 1 1 1 0 -1 0 0 0 -1 -1 -1 0 -1 1 -1 0 -1 -1 1 0 -1 -1 1 0 0 1 1 0 0 1 1 0 0 0 -1 0 1 -1 -1 0 1 1 0 0 -1 -1 -1 0 1 1 1 0 1 1 0 0 -1 0 -1 0 0 -1 1 0 -1 1 1 0 1 0 -1 0 -1 1 -1 0 0 -1 0 0 -1 -1 0 0 1 1 -1 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1