Möbius function: Difference between revisions
Thundergnat (talk | contribs) m (Clarify task description) |
Thundergnat (talk | contribs) m (More clarification) |
||
Line 6: | Line 6: | ||
A fairly straightforward method is to find the prime factors of a positive integer '''n''', then define '''μ(n)''' based on the sum of the primitive factors. It has the values '''{−1, 0, 1}''' depending on the factorization of '''n''': |
A fairly straightforward method is to find the prime factors of a positive integer '''n''', then define '''μ(n)''' based on the sum of the primitive factors. It has the values '''{−1, 0, 1}''' depending on the factorization of '''n''': |
||
:* '''μ(1)''' is defined to be '''1'''. |
|||
:* '''μ(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 '''even''' number of prime factors. |
Revision as of 20:40, 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) based on the sum of the primitive factors. It has the values {−1, 0, 1} depending on the factorization of n:
- μ(1) is defined to be 1.
- μ(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
Go
<lang go>package main
import "fmt"
func möbius(to int) []int {
if to < 1 { to = 1 } mobs := make([]int, to+1) // all zero by default primes := []int{2} for i := 1; i <= to; i++ { j := i cp := 0 // counts prime factors spf := false // true if there is a square prime factor for _, p := range primes { if p > j { break } if j%p == 0 { j /= p cp++ } if j%p == 0 { spf = true break } } if cp == 0 && i > 2 { cp = 1 primes = append(primes, i) } if !spf { if cp%2 == 0 { mobs[i] = 1 } else { mobs[i] = -1 } } } return mobs
}
func main() {
mobs := möbius(199) fmt.Println("Möbius sequence - First 199 terms:") for i := 0; i < 200; i++ { if i == 0 { fmt.Print(" ") continue } if i%20 == 0 { fmt.Println() } fmt.Printf(" % d", mobs[i]) }
}</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
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