Möbius function: Difference between revisions
(Add Factor) |
(Added Go) |
||
Line 53: | Line 53: | ||
0 1 0 -1 0 -1 1 -1 0 0 -1 0 0 -1 -1 0 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 |
0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 |
||
</pre> |
|||
=={{header|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> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
Revision as of 19:22, 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
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