Möbius function: Difference between revisions
Alpha bravo (talk | contribs) (Added AutoHotkey) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 32: | Line 32: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{Trans|C}} |
{{Trans|C}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN |
||
# show the first 199 values of the moebius function # |
# show the first 199 values of the moebius function # |
||
INT sq root = 1 000; |
INT sq root = 1 000; |
||
Line 58: | Line 58: | ||
IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI |
IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 76: | Line 76: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">mobius: function [n][ |
||
if n=0 -> return "" |
if n=0 -> return "" |
||
if n=1 -> return 1 |
if n=1 -> return 1 |
||
Line 87: | Line 87: | ||
loop split.every:20 map 0..199 => mobius 'a -> |
loop split.every:20 map 0..199 => mobius 'a -> |
||
print map a => [pad to :string & 3]</ |
print map a => [pad to :string & 3]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 103: | Line 103: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">loop 100 |
||
result .= SubStr(" " Möbius(A_Index), -1) . (Mod(A_Index, 10) ? " " : "`n") |
result .= SubStr(" " Möbius(A_Index), -1) . (Mod(A_Index, 10) ? " " : "`n") |
||
MsgBox, 262144, , % result |
MsgBox, 262144, , % result |
||
Line 148: | Line 148: | ||
ans.push(Format("{:d}", n)) |
ans.push(Format("{:d}", n)) |
||
return ans |
return ans |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 -1 -1 0 -1 1 -1 0 0 1 |
<pre> 1 -1 -1 0 -1 1 -1 0 0 1 |
||
Line 162: | Line 162: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f MOBIUS_FUNCTION.AWK |
# syntax: GAWK -f MOBIUS_FUNCTION.AWK |
||
# converted from Java |
# converted from Java |
||
Line 209: | Line 209: | ||
return(MU[n]) |
return(MU[n]) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 228: | Line 228: | ||
=={{header|BASIC256}}== |
=={{header|BASIC256}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang="basic256">function mobius(n) |
||
if n = 1 then return 1 |
if n = 1 then return 1 |
||
for d = 2 to int(sqr(n)) |
for d = 2 to int(sqr(n)) |
||
Line 248: | Line 248: | ||
end if |
end if |
||
next i |
next i |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 257: | Line 257: | ||
=={{header|C}}== |
=={{header|C}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="c">#include <math.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 311: | Line 311: | ||
free(mu); |
free(mu); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 199 terms of the m÷bius function are as follows: |
<pre>First 199 terms of the m÷bius function are as follows: |
||
Line 327: | Line 327: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="cpp">#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
#include <vector> |
#include <vector> |
||
Line 381: | Line 381: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 199 terms of the m÷bius function are as follows: |
<pre>First 199 terms of the m÷bius function are as follows: |
||
Line 397: | Line 397: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<syntaxhighlight lang="d">import std.math; |
||
import std.stdio; |
import std.stdio; |
||
Line 452: | Line 452: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 199 terms of the m├╢bius function are as follows: |
<pre>First 199 terms of the m├╢bius function are as follows: |
||
Line 468: | Line 468: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]] |
This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Möbius function. Nigel Galloway: January 31st., 2021 |
// Möbius function. Nigel Galloway: January 31st., 2021 |
||
let fN g=let n=primes32() |
let fN g=let n=primes32() |
||
Line 478: | Line 478: | ||
let mobius=seq{yield 1; yield! Seq.initInfinite((+)2>>fN)} |
let mobius=seq{yield 1; yield! Seq.initInfinite((+)2>>fN)} |
||
mobius|>Seq.take 500|>Seq.chunkBySize 25|>Seq.iter(fun n->Array.iter(printf "%3d") n;printfn "") |
mobius|>Seq.take 500|>Seq.chunkBySize 25|>Seq.iter(fun n->Array.iter(printf "%3d") n;printfn "") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 506: | Line 506: | ||
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]. |
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}} |
{{works with|Factor|0.99 2020-01-23}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting grouping io math.extras math.ranges sequences ; |
||
"First 199 terms of the Möbius sequence:" print |
"First 199 terms of the Möbius sequence:" print |
||
199 [1,b] [ mobius ] map " " prefix 20 group |
199 [1,b] [ mobius ] map " " prefix 20 group |
||
[ [ "%3s" printf ] each nl ] each</ |
[ [ "%3s" printf ] each nl ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 528: | Line 528: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{Trans|C}} |
{{Trans|C}} |
||
< |
<syntaxhighlight lang="fortran"> |
||
program moebius |
program moebius |
||
use iso_fortran_env, only: output_unit |
use iso_fortran_env, only: output_unit |
||
Line 570: | Line 570: | ||
end do |
end do |
||
end program moebius |
end program moebius |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 588: | Line 588: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">function mobius( n as uinteger ) as integer |
||
if n = 1 then return 1 |
if n = 1 then return 1 |
||
for d as uinteger = 2 to int(sqr(n)) |
for d as uinteger = 2 to int(sqr(n)) |
||
Line 607: | Line 607: | ||
outstr = "" |
outstr = "" |
||
end if |
end if |
||
next i</ |
next i</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 633: | Line 633: | ||
=={{header|FutureBasic}}== |
=={{header|FutureBasic}}== |
||
< |
<syntaxhighlight lang="futurebasic">local fn IsPrime( n as long ) as BOOL |
||
BOOL result = YES |
BOOL result = YES |
||
long i |
long i |
||
Line 678: | Line 678: | ||
next |
next |
||
HandleEvents</ |
HandleEvents</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 690: | Line 690: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 745: | Line 745: | ||
fmt.Printf(" % d", mobs[i]) |
fmt.Printf(" % d", mobs[i]) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 763: | Line 763: | ||
=={{header|GW-BASIC}}== |
=={{header|GW-BASIC}}== |
||
< |
<syntaxhighlight lang="gwbasic">10 FOR T = 0 TO 9 |
||
20 FOR U = 1 TO 10 |
20 FOR U = 1 TO 10 |
||
30 N = 10*T + U |
30 N = 10*T + U |
||
Line 781: | Line 781: | ||
170 M = -M |
170 M = -M |
||
180 N = N/F |
180 N = N/F |
||
190 RETURN</ |
190 RETURN</syntaxhighlight> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (intercalate) |
||
import Data.List.Split (chunksOf) |
import Data.List.Split (chunksOf) |
||
import Data.Vector.Unboxed (toList) |
import Data.Vector.Unboxed (toList) |
||
Line 812: | Line 812: | ||
putStrLn ("μ(n) for 1 ≤ n ≤ " ++ show n ++ ":\n") >> |
putStrLn ("μ(n) for 1 ≤ n ≤ " ++ show n ++ ":\n") >> |
||
putStrLn (showMoebiusBlock cols $ moebiusBlock n) |
putStrLn (showMoebiusBlock cols $ moebiusBlock n) |
||
_ -> hPutStrLn stderr $ "Usage: " ++ prog ++ " num-columns maximum-number"</ |
_ -> hPutStrLn stderr $ "Usage: " ++ prog ++ " num-columns maximum-number"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 834: | Line 834: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">mu=: ({{*/1-y>1}} * _1 ^ 2|+/)@q:~&_</syntaxhighlight> |
||
Explanation: _ q: n gives the list of exponents of prime factors of n. (This is an empty list for the number 1, is 2 0 2 for the number 100 and is 3 1 1 for the number 120.) |
Explanation: _ q: n gives the list of exponents of prime factors of n. (This is an empty list for the number 1, is 2 0 2 for the number 100 and is 3 1 1 for the number 120.) |
||
Line 842: | Line 842: | ||
Task example: |
Task example: |
||
< |
<syntaxhighlight lang="j"> mu 1+i.10 20 |
||
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 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 0 0 _1 _1 _1 0 1 1 1 0 _1 1 1 0 |
||
Line 852: | Line 852: | ||
1 1 1 0 1 1 0 0 _1 0 _1 0 0 _1 1 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 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 0</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java"> |
||
public class MöbiusFunction { |
public class MöbiusFunction { |
||
Line 915: | Line 915: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 939: | Line 939: | ||
====Using a Sieve==== |
====Using a Sieve==== |
||
'''Adapted from [[#C|C]]''' |
'''Adapted from [[#C|C]]''' |
||
< |
<syntaxhighlight lang="jq"># Input: a non-negative integer, $n |
||
# Output: an array of size $n + 1 such that the nth-mobius number is .[$n] |
# Output: an array of size $n + 1 such that the nth-mobius number is .[$n] |
||
# i.e. $n|mobius_array[-1] |
# i.e. $n|mobius_array[-1] |
||
Line 963: | Line 963: | ||
# For one-off computations: |
# For one-off computations: |
||
def mu($n): $n | mobius_array[-1];</ |
def mu($n): $n | mobius_array[-1];</syntaxhighlight> |
||
'''The Task''' |
'''The Task''' |
||
< |
<syntaxhighlight lang="jq">def nwise($n): |
||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
||
n; |
n; |
||
Line 977: | Line 977: | ||
| join(" ") ) ; |
| join(" ") ) ; |
||
task</ |
task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 995: | Line 995: | ||
Note that the following solution to the task at hand (computing a range of Mobius numbers is inefficient as it does not cache the primes array. |
Note that the following solution to the task at hand (computing a range of Mobius numbers is inefficient as it does not cache the primes array. |
||
'''Preliminaries''' |
'''Preliminaries''' |
||
< |
<syntaxhighlight lang="jq"># relatively_prime(previous) tests whether the input integer is prime |
||
# relative to the primes in the array "previous": |
# relative to the primes in the array "previous": |
||
def relatively_prime(previous): |
def relatively_prime(previous): |
||
Line 1,048: | Line 1,048: | ||
else . as $in |
else . as $in |
||
| pf( [ primes( (1+$in) | sqrt | floor) ] ) |
| pf( [ primes( (1+$in) | sqrt | floor) ] ) |
||
end;</ |
end;</syntaxhighlight> |
||
'''Mu''' |
'''Mu''' |
||
< |
<syntaxhighlight lang="jq">def isSquareFree: |
||
. as $n |
. as $n |
||
| 2 |
| 2 |
||
Line 1,070: | Line 1,070: | ||
else 0 |
else 0 |
||
end |
end |
||
end;</ |
end;</syntaxhighlight> |
||
'''The Task''' |
'''The Task''' |
||
< |
<syntaxhighlight lang="jq">def nwise($n): |
||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
||
n; |
n; |
||
Line 1,083: | Line 1,083: | ||
| join(" ") ) ; |
| join(" ") ) ; |
||
task</ |
task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
As above. |
As above. |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
# modified from reinermartin's PR at https://github.com/JuliaMath/Primes.jl/pull/70/files |
# modified from reinermartin's PR at https://github.com/JuliaMath/Primes.jl/pull/70/files |
||
Line 1,102: | Line 1,102: | ||
print(lpad(μ(n), 3), n % 20 == 19 ? "\n" : "") |
print(lpad(μ(n), 3), n % 20 == 19 ? "\n" : "") |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
First 199 terms of the Möbius sequence: |
First 199 terms of the Möbius sequence: |
||
Line 1,119: | Line 1,119: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">import kotlin.math.sqrt |
||
fun main() { |
fun main() { |
||
Line 1,176: | Line 1,176: | ||
} |
} |
||
return MU!![n] |
return MU!![n] |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 199 terms of the möbius function are as follows: |
<pre>First 199 terms of the möbius function are as follows: |
||
Line 1,192: | Line 1,192: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="lua">function buildArray(size, value) |
||
local tbl = {} |
local tbl = {} |
||
for i=1, size do |
for i=1, size do |
||
Line 1,236: | Line 1,236: | ||
print() |
print() |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 199 terms of the mobius function are as follows: |
<pre>First 199 terms of the mobius function are as follows: |
||
Line 1,251: | Line 1,251: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Grid[Partition[MoebiusMu[Range[99]], UpTo[10]]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 -1 -1 0 -1 1 -1 0 0 1 |
<pre>1 -1 -1 0 -1 1 -1 0 0 1 |
||
Line 1,267: | Line 1,267: | ||
Uses the prime decomposition method from https://rosettacode.org/wiki/Prime_decomposition#Nim |
Uses the prime decomposition method from https://rosettacode.org/wiki/Prime_decomposition#Nim |
||
< |
<syntaxhighlight lang="nim">import std/[math, sequtils, strformat] |
||
func getStep(n: int): int {.inline.} = |
func getStep(n: int): int {.inline.} = |
||
Line 1,320: | Line 1,320: | ||
if i mod 20 == 0: |
if i mod 20 == 0: |
||
echo "" # print newline |
echo "" # print newline |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>The first 199 möbius numbers are: |
<pre>The first 199 möbius numbers are: |
||
Line 1,338: | Line 1,338: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use utf8; |
||
use strict; |
use strict; |
||
use warnings; |
use warnings; |
||
Line 1,361: | Line 1,361: | ||
say "Möbius sequence - First $upto terms:\n" . |
say "Möbius sequence - First $upto terms:\n" . |
||
(' 'x4 . sprintf "@{['%4d' x $upto]}", @möebius) =~ s/((.){80})/$1\n/gr;</ |
(' 'x4 . sprintf "@{['%4d' x $upto]}", @möebius) =~ s/((.){80})/$1\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Möbius sequence - First 199 terms: |
<pre>Möbius sequence - First 199 terms: |
||
Line 1,376: | Line 1,376: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">Moebius</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">Moebius</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
||
Line 1,390: | Line 1,390: | ||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">199</span> <span style="color: #008080;">do</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">Moebius</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">199</span> <span style="color: #008080;">do</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">Moebius</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,415: | Line 1,415: | ||
< |
<syntaxhighlight lang="python"> |
||
# Python Program to evaluate |
# Python Program to evaluate |
||
# Mobius def M(N) = 1 if N = 1 |
# Mobius def M(N) = 1 if N = 1 |
||
Line 1,483: | Line 1,483: | ||
if i % 20 == 0: print() |
if i % 20 == 0: print() |
||
# This code is contributed by |
# This code is contributed by |
||
# Manish Shaw(manishshaw1)</ |
# Manish Shaw(manishshaw1)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Mobius numbers from 1..99: |
<pre>Mobius numbers from 1..99: |
||
Line 1,495: | Line 1,495: | ||
The idea is based on efficient program to print all prime factors of a given number. The interesting thing is, we do not need inner while loop here because if a number divides more than once, we can immediately return 0. |
The idea is based on efficient program to print all prime factors of a given number. The interesting thing is, we do not need inner while loop here because if a number divides more than once, we can immediately return 0. |
||
< |
<syntaxhighlight lang="python"># Python Program to evaluate |
||
# Mobius def M(N) = 1 if N = 1 |
# Mobius def M(N) = 1 if N = 1 |
||
# M(N) = 0 if any prime factor |
# M(N) = 0 if any prime factor |
||
Line 1,558: | Line 1,558: | ||
print(f"{mobius(i):>4}", end = '') |
print(f"{mobius(i):>4}", end = '') |
||
# This code is contributed by |
# This code is contributed by |
||
# Manish Shaw(manishshaw1)</ |
# Manish Shaw(manishshaw1)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Mobius numbers from 1..99: |
<pre>Mobius numbers from 1..99: |
||
Line 1,573: | Line 1,573: | ||
Möbius number is not defined for n == 0. Raku arrays are indexed from 0 so store a blank value at position zero to keep n and μ(n) aligned. |
Möbius number is not defined for n == 0. Raku arrays are indexed from 0 so store a blank value at position zero to keep n and μ(n) aligned. |
||
<lang |
<syntaxhighlight lang="raku" line>use Prime::Factor; |
||
sub μ (Int \n) { |
sub μ (Int \n) { |
||
Line 1,585: | Line 1,585: | ||
# The Task |
# The Task |
||
put "Möbius sequence - First 199 terms:\n", |
put "Möbius sequence - First 199 terms:\n", |
||
@möbius[^200]».fmt('%3s').batch(20).join: "\n";</ |
@möbius[^200]».fmt('%3s').batch(20).join: "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Möbius sequence - First 199 terms: |
<pre>Möbius sequence - First 199 terms: |
||
Line 1,610: | Line 1,610: | ||
The function to computer some prime numbers is a bit of an overkill, but the goal was to keep it general (in case of larger/higher ranges for a Möbius sequence). |
The function to computer some prime numbers is a bit of an overkill, but the goal was to keep it general (in case of larger/higher ranges for a Möbius sequence). |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm computes & shows a value grid of the Möbius function for a range of integers.*/ |
||
parse arg LO HI grp . /*obtain optional arguments from the CL*/ |
parse arg LO HI grp . /*obtain optional arguments from the CL*/ |
||
if LO=='' | LO=="," then LO= 0 /*Not specified? Then use the default.*/ |
if LO=='' | LO=="," then LO= 0 /*Not specified? Then use the default.*/ |
||
Line 1,655: | Line 1,655: | ||
end /*k*/ /* [↓] a prime (J) has been found. */ |
end /*k*/ /* [↓] a prime (J) has been found. */ |
||
nP= nP+1; if nP<=HI then @.nP= j /*bump prime count; assign prime to @.*/ |
nP= nP+1; if nP<=HI then @.nP= j /*bump prime count; assign prime to @.*/ |
||
end /*j*/; return</ |
end /*j*/; return</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
Line 1,675: | Line 1,675: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
{{Trans|FreeBASIC}} |
{{Trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang="ring"> |
||
mobStr = " . " |
mobStr = " . " |
||
Line 1,706: | Line 1,706: | ||
next |
next |
||
return -1 |
return -1 |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 1,732: | Line 1,732: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require 'prime' |
||
def μ(n) |
def μ(n) |
||
Line 1,742: | Line 1,742: | ||
([" "] + (1..199).map{|n|"%2s" % μ(n)}).each_slice(20){|line| puts line.join(" ") } |
([" "] + (1..199).map{|n|"%2s" % μ(n)}).each_slice(20){|line| puts line.join(" ") } |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,760: | Line 1,760: | ||
Built-in: |
Built-in: |
||
< |
<syntaxhighlight lang="ruby">say moebius(53) #=> -1 |
||
say moebius(54) #=> 0 |
say moebius(54) #=> 0 |
||
say moebius(55) #=> 1</ |
say moebius(55) #=> 1</syntaxhighlight> |
||
Simple implementation: |
Simple implementation: |
||
< |
<syntaxhighlight lang="ruby">func μ(n) { |
||
var f = n.factor_exp.map { .tail } |
var f = n.factor_exp.map { .tail } |
||
f.any { _ > 1 } ? 0 : ((-1)**f.sum) |
f.any { _ > 1 } ? 0 : ((-1)**f.sum) |
||
Line 1,775: | Line 1,775: | ||
say line.map { '%2s' % _ }.join(' ') |
say line.map { '%2s' % _ }.join(' ') |
||
}) |
}) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,794: | Line 1,794: | ||
Tiny BASIC is not suited for printing tables, so this is limited to prompting for a single number and calculating its Mobius number. |
Tiny BASIC is not suited for printing tables, so this is limited to prompting for a single number and calculating its Mobius number. |
||
< |
<syntaxhighlight lang="tinybasic"> PRINT "Enter an integer" |
||
INPUT N |
INPUT N |
||
IF N < 0 THEN LET N = -N |
IF N < 0 THEN LET N = -N |
||
Line 1,813: | Line 1,813: | ||
END |
END |
||
101 PRINT "1" |
101 PRINT "1" |
||
END</ |
END</syntaxhighlight> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt |
||
import "/math" for Int |
import "/math" for Int |
||
Line 1,850: | Line 1,850: | ||
} |
} |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,868: | Line 1,868: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func Mobius(N); |
||
int N, Cnt, F, K; |
int N, Cnt, F, K; |
||
[Cnt:= 0; |
[Cnt:= 0; |
||
Line 1,890: | Line 1,890: | ||
if rem(N/20) = 19 then CrLf(0); |
if rem(N/20) = 19 then CrLf(0); |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,908: | Line 1,908: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang="yabasic">outstr$ = " . " |
||
for i = 1 to 200 |
for i = 1 to 200 |
||
if mobius(i) >= 0 then outstr$ = outstr$ + " " : fi |
if mobius(i) >= 0 then outstr$ = outstr$ + " " : fi |
||
Line 1,928: | Line 1,928: | ||
next d |
next d |
||
return -1 |
return -1 |
||
end sub</ |
end sub</syntaxhighlight> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn mobius(n){ |
||
pf:=primeFactors(n); |
pf:=primeFactors(n); |
||
sq:=pf.filter1('wrap(f){ (n % (f*f))==0 }); // False if square free |
sq:=pf.filter1('wrap(f){ (n % (f*f))==0 }); // False if square free |
||
Line 1,949: | Line 1,949: | ||
if(n!=m) acc.append(n/m); // opps, missed last factor |
if(n!=m) acc.append(n/m); // opps, missed last factor |
||
else acc; |
else acc; |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">[1..199].apply(mobius) |
||
.pump(Console.println, T(Void.Read,19,False), |
.pump(Console.println, T(Void.Read,19,False), |
||
fcn{ vm.arglist.pump(String,"%3d".fmt) });</ |
fcn{ vm.arglist.pump(String,"%3d".fmt) });</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 23:20, 27 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
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
ALGOL 68
BEGIN
# show the first 199 values of the moebius function #
INT sq root = 1 000;
INT mu max = sq root * sq root;
[ 1 : mu max ]INT mu;
FOR i FROM LWB mu TO UPB mu DO mu[ i ] := 1 OD;
FOR i FROM 2 TO sq root DO
IF mu[ i ] = 1 THEN
# for each factor found, swap + and - #
FOR j FROM i BY i TO UPB mu DO mu[ j ] *:= -i OD;
FOR j FROM i * i BY i * i TO UPB mu DO mu[ j ] := 0 OD
FI
OD;
FOR i FROM 2 TO UPB mu DO
IF mu[ i ] = i THEN mu[ i ] := 1
ELIF mu[ i ] = -i THEN mu[ i ] := -1
ELIF mu[ i ] < 0 THEN mu[ i ] := 1
ELIF mu[ i ] > 0 THEN mu[ i ] := -1
# ELSE mu[ i ] = 0 so no change #
FI
OD;
print( ( "First 199 terms of the möbius function are as follows:", newline, " " ) );
FOR i TO 199 DO
print( ( whole( mu[ i ], -4 ) ) );
IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI
OD
END
- Output:
First 199 terms of the möbius function are as follows: 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
Arturo
mobius: function [n][
if n=0 -> return ""
if n=1 -> return 1
f: factors.prime n
if f <> unique f -> return 0
if? odd? size f -> return neg 1
else -> return 1
]
loop split.every:20 map 0..199 => mobius 'a ->
print map a => [pad to :string & 3]
- Output:
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
AutoHotkey
loop 100
result .= SubStr(" " Möbius(A_Index), -1) . (Mod(A_Index, 10) ? " " : "`n")
MsgBox, 262144, , % result
return
Möbius(n){
if n=1
return 1
x := prime_factors(n)
c := x.Count()
sq := []
for i, v in x
if sq[v]
return 0
else
sq[v] := 1
return (c/2 = floor(c/2)) ? 1 : -1
}
prime_factors(n) {
if (n <= 3)
return [n]
ans := [], done := false
while !done {
if !Mod(n, 2)
ans.push(2), n /= 2
else if !Mod(n, 3)
ans.push(3), n /= 3
else if (n = 1)
return ans
else {
sr := sqrt(n), done := true, i := 6
while (i <= sr+6) {
if !Mod(n, i-1) { ; is n divisible by i-1?
ans.push(i-1), n /= i-1, done := false
break
}
if !Mod(n, i+1) { ; is n divisible by i+1?
ans.push(i+1), n /= i+1, done := false
break
}
i += 6
}}}
ans.push(Format("{:d}", n))
return ans
}
- Output:
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
AWK
# syntax: GAWK -f MOBIUS_FUNCTION.AWK
# converted from Java
BEGIN {
printf("first 199 terms of the mobius sequence:\n ")
for (n=1; n<200; n++) {
printf("%3d",mobius(n))
if ((n+1) % 20 == 0) {
printf("\n")
}
}
exit(0)
}
function mobius(n, i,j,mu_max) {
if (n in MU) {
return(MU[n])
}
mu_max = 1000000
for (i=0; i<mu_max; i++) { # populate array
MU[i] = 1
}
for (i=2; i<=int(sqrt(mu_max)); i++ ) {
if (MU[i] == 1) {
for (j=i; j<=mu_max; j+=i) { # for each factor found, swap + and -
MU[j] *= -i
}
for (j=i*i; j<=mu_max; j+=i*i) { # square factor = 0
MU[j] = 0
}
}
}
for (i=2; i<=mu_max; i++) {
if (MU[i] == i) {
MU[i] = 1
}
else if (MU[i] == -i) {
MU[i] = -1
}
else if (MU[i] < 0) {
MU[i] = 1
}
else if (MU[i] > 0) {
MU[i] = -1
}
}
return(MU[n])
}
- Output:
first 199 terms of the mobius 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
BASIC256
function mobius(n)
if n = 1 then return 1
for d = 2 to int(sqr(n))
if n mod d = 0 then
if n mod (d*d) = 0 then return 0
return -mobius(n/d)
end if
next d
return -1
end function
outstr$ = " . "
for i = 1 to 200
if mobius(i) >= 0 then outstr$ += " "
outstr$ += string(mobius(i)) + " "
if i mod 10 = 9 then
print outstr$
outstr$ = ""
end if
next i
end
- Output:
Igual que la entrada de FreeBASIC.
C
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
const int MU_MAX = 1000000;
int i, j;
int *mu;
int sqroot;
sqroot = (int)sqrt(MU_MAX);
mu = malloc((MU_MAX + 1) * sizeof(int));
for (i = 0; i < MU_MAX;i++) {
mu[i] = 1;
}
for (i = 2; i <= sqroot; i++) {
if (mu[i] == 1) {
// for each factor found, swap + and -
for (j = i; j <= MU_MAX; j += i) {
mu[j] *= -i;
}
// square factor = 0
for (j = i * i; j <= MU_MAX; j += i * i) {
mu[j] = 0;
}
}
}
for (i = 2; i <= MU_MAX; i++) {
if (mu[i] == i) {
mu[i] = 1;
} else if (mu[i] == -i) {
mu[i] = -1;
} else if (mu[i] < 0) {
mu[i] = 1;
} else if (mu[i] > 0) {
mu[i] = -1;
}
}
printf("First 199 terms of the möbius function are as follows:\n ");
for (i = 1; i < 200; i++) {
printf("%2d ", mu[i]);
if ((i + 1) % 20 == 0) {
printf("\n");
}
}
free(mu);
return 0;
}
- Output:
First 199 terms of the m÷bius function are as follows: 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
C++
#include <iomanip>
#include <iostream>
#include <vector>
constexpr int MU_MAX = 1'000'000;
std::vector<int> MU;
int mobiusFunction(int n) {
if (!MU.empty()) {
return MU[n];
}
// Populate array
MU.resize(MU_MAX + 1, 1);
int root = sqrt(MU_MAX);
for (int i = 2; i <= root; i++) {
if (MU[i] == 1) {
// for each factor found, swap + and -
for (int j = i; j <= MU_MAX; j += i) {
MU[j] *= -i;
}
// square factor = 0
for (int j = i * i; j <= MU_MAX; j += i * i) {
MU[j] = 0;
}
}
}
for (int i = 2; i <= MU_MAX; i++) {
if (MU[i] == i) {
MU[i] = 1;
} else if (MU[i] == -i) {
MU[i] = -1;
} else if (MU[i] < 0) {
MU[i] = 1;
} else if (MU[i] > 0) {
MU[i] = -1;
}
}
return MU[n];
}
int main() {
std::cout << "First 199 terms of the möbius function are as follows:\n ";
for (int n = 1; n < 200; n++) {
std::cout << std::setw(2) << mobiusFunction(n) << " ";
if ((n + 1) % 20 == 0) {
std::cout << '\n';
}
}
return 0;
}
- Output:
First 199 terms of the m÷bius function are as follows: 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
D
import std.math;
import std.stdio;
immutable MU_MAX = 1_000_000;
int mobiusFunction(int n) {
static initialized = false;
static int[MU_MAX + 1] MU;
if (initialized) {
return MU[n];
}
// populate array
MU[] = 1;
int root = cast(int) sqrt(cast(real) MU_MAX);
for (int i = 2; i <= root; i++) {
if (MU[i] == 1) {
// for each factor found, swap + and -
for (int j = i; j <= MU_MAX; j += i) {
MU[j] *= -i;
}
// square factor = 0
for (int j = i * i; j <= MU_MAX; j += i * i) {
MU[j] = 0;
}
}
}
for (int i = 2; i <= MU_MAX; i++) {
if (MU[i] == i) {
MU[i] = 1;
} else if (MU[i] == -i) {
MU[i] = -1;
} else if (MU[i] < 0) {
MU[i] = 1;
} else if (MU[i] > 0) {
MU[i] = -1;
}
}
initialized = true;
return MU[n];
}
void main() {
writeln("First 199 terms of the möbius function are as follows:");
write(" ");
for (int n = 1; n < 200; n++) {
writef("%2d ", mobiusFunction(n));
if ((n + 1) % 20 == 0) {
writeln;
}
}
}
- Output:
First 199 terms of the m├╢bius function are as follows: 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
F#
This task uses Extensible Prime Generator (F#)
// Möbius function. Nigel Galloway: January 31st., 2021
let fN g=let n=primes32()
let rec fN i g e l=match (l/g,l%g,e) with (1,0,false)->i
|(n,0,false)->fN (0-i) g true n
|(_,0,true) ->0
|_ ->fN i (Seq.head n) false l
fN -1 (Seq.head n) false g
let mobius=seq{yield 1; yield! Seq.initInfinite((+)2>>fN)}
mobius|>Seq.take 500|>Seq.chunkBySize 25|>Seq.iter(fun n->Array.iter(printf "%3d") n;printfn "")
- Output:
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 0 1 1 1 0 1 1 0 0 1 1 -1 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 0 0 0 0 -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 0 -1 1 0 0 -1 1 0 0 -1 -1 -1 0 -1 -1 1 0 0 -1 1 0 -1 0 1 0 0 1 1 0 1 1 1 0 1 0 -1 0 1 -1 -1 0 -1 1 0 0 -1 -1 1 0 1 -1 1 0 0 1 1 0 1 1 -1 0 0 1 1 0 -1 0 1 0 1 0 0 0 -1 1 -1 0 -1 0 0 0 -1 -1 1 0 -1 1 -1 0 0 1 0 0 1 -1 -1 0 0 -1 1 0 -1 -1 0 0 1 0 -1 0 1 1 -1 0 -1 1 0 0 -1 1 1 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 0 0 0 -1 1 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 0 0 -1 1 -1 0 -1 1 -1 0 1 -1 1 0 1 -1 0 0 0 1 -1 0 1 1 -1 0 1 0 -1 0 1 0 -1 0 1 -1 0 0 1 -1 -1 0
Factor
The mobius
word exists in the math.extras
vocabulary. See the implementation here.
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
- 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
Fortran
program moebius
use iso_fortran_env, only: output_unit
integer, parameter :: mu_max=1000000, line_break=20
integer, parameter :: sqroot=int(sqrt(real(mu_max)))
integer :: i, j
integer, dimension(mu_max) :: mu
mu = 1
do i = 2, sqroot
if (mu(i) == 1) then
do j = i, mu_max, i
mu(j) = mu(j) * (-i)
end do
do j = i**2, mu_max, i**2
mu(j) = 0
end do
end if
end do
do i = 2, mu_max
if (mu(i) == i) then
mu(i) = 1
else if (mu(i) == -i) then
mu(i) = -1
else if (mu(i) < 0) then
mu(i) = 1
else if (mu(i) > 0) then
mu(i) = -1
end if
end do
write(output_unit,*) "The first 199 terms of the Möbius sequence are:"
write(output_unit,'(3x)', advance="no") ! Alignment of first number
do i = 1, 199
write(output_unit,'(I2,x)', advance="no") mu(i)
if (modulo(i+1, line_break) == 0) write(output_unit,*)
end do
end program moebius
- Output:
The first 199 terms of the Möbius sequence are: 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
FreeBASIC
function mobius( n as uinteger ) as integer
if n = 1 then return 1
for d as uinteger = 2 to int(sqr(n))
if n mod d = 0 then
if n mod (d*d) = 0 then return 0
return -mobius(n/d)
end if
next d
return -1
end function
dim as string outstr = " . "
for i as uinteger = 1 to 200
if mobius(i)>=0 then outstr += " "
outstr += str(mobius(i))+" "
if i mod 10 = 9 then
print outstr
outstr = ""
end if
next i
- Output:
. 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
FutureBasic
local fn IsPrime( n as long ) as BOOL
BOOL result = YES
long i
if ( n < 2 ) then result = NO : exit fn
for i = 2 to n + 1
if ( i * i <= n ) and ( n mod i == 0 )
result = NO : exit fn
end if
next
end fn = result
local fn Mobius( n as long ) as long
long i, p = 0, result = 0
if ( n == 1 ) then result = 1 : exit fn
for i = 1 to n + 1
if ( n mod i == 0 ) and ( fn IsPrime( i ) == YES )
if ( n mod ( i * i ) == 0 )
result = 0 : exit fn
else
p++
end if
end if
next
if( p mod 2 != 0 )
result = -1
else
result = 1
end if
end fn = result
window 1, @"Möbius function", (0,0,600,300)
printf @"First 100 terms of Mobius sequence:"
long i
for i = 1 to 100
printf @"%2ld\t", fn Mobius(i)
if ( i mod 20 == 0 ) then print
next
HandleEvents
- Output:
First 100 terms of Mobius 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
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])
}
}
- 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
GW-BASIC
10 FOR T = 0 TO 9
20 FOR U = 1 TO 10
30 N = 10*T + U
40 GOSUB 100
50 PRINT USING "## ";M;
60 NEXT U
70 PRINT
80 NEXT T
90 END
100 IF N = 1 THEN M = 1 : RETURN
110 M = 1 : F = 2
120 IF N MOD (F*F) = 0 THEN M = 0 : RETURN
130 IF N MOD F = 0 THEN GOSUB 170
140 F = F + 1
150 IF F <= N THEN GOTO 120
160 RETURN
170 M = -M
180 N = N/F
190 RETURN
Haskell
import Data.List (intercalate)
import Data.List.Split (chunksOf)
import Data.Vector.Unboxed (toList)
import Math.NumberTheory.ArithmeticFunctions.Moebius (Moebius(..),
sieveBlockMoebius)
import System.Environment (getArgs, getProgName)
import System.IO (hPutStrLn, stderr)
import Text.Read (readMaybe)
-- Calculate the Möbius function, μ(n), for a sequence of values starting at 1.
moebiusBlock :: Word -> [Moebius]
moebiusBlock = toList . sieveBlockMoebius 1
showMoebiusBlock :: Word -> [Moebius] -> String
showMoebiusBlock cols = intercalate "\n" . map (concatMap showMoebius) .
chunksOf (fromIntegral cols)
where showMoebius MoebiusN = " -1"
showMoebius MoebiusZ = " 0"
showMoebius MoebiusP = " 1"
main :: IO ()
main = do
prog <- getProgName
args <- map readMaybe <$> getArgs
case args of
[Just cols, Just n] ->
putStrLn ("μ(n) for 1 ≤ n ≤ " ++ show n ++ ":\n") >>
putStrLn (showMoebiusBlock cols $ moebiusBlock n)
_ -> hPutStrLn stderr $ "Usage: " ++ prog ++ " num-columns maximum-number"
- Output:
μ(n) for 1 ≤ n ≤ 200: 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 0
J
Implementation:
mu=: ({{*/1-y>1}} * _1 ^ 2|+/)@q:~&_
Explanation: _ q: n gives the list of exponents of prime factors of n. (This is an empty list for the number 1, is 2 0 2 for the number 100 and is 3 1 1 for the number 120.)
In this context +/ is the sum of that list, 2 | +/ is 1 if the sum is odd and 0 if the sum is even. _1^0 is 1 and _1^1 is _1. And, {{*/1-y>1}} returns zero if any exponent is at least 2 in magnitude.
Task example:
mu 1+i.10 20
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 0
Java
public class MöbiusFunction {
public static void main(String[] args) {
System.out.printf("First 199 terms of the möbius function are as follows:%n ");
for ( int n = 1 ; n < 200 ; n++ ) {
System.out.printf("%2d ", möbiusFunction(n));
if ( (n+1) % 20 == 0 ) {
System.out.printf("%n");
}
}
}
private static int MU_MAX = 1_000_000;
private static int[] MU = null;
// Compute mobius function via sieve
private static int möbiusFunction(int n) {
if ( MU != null ) {
return MU[n];
}
// Populate array
MU = new int[MU_MAX+1];
int sqrt = (int) Math.sqrt(MU_MAX);
for ( int i = 0 ; i < MU_MAX ; i++ ) {
MU[i] = 1;
}
for ( int i = 2 ; i <= sqrt ; i++ ) {
if ( MU[i] == 1 ) {
// for each factor found, swap + and -
for ( int j = i ; j <= MU_MAX ; j += i ) {
MU[j] *= -i;
}
// square factor = 0
for ( int j = i*i ; j <= MU_MAX ; j += i*i ) {
MU[j] = 0;
}
}
}
for ( int i = 2 ; i <= MU_MAX ; i++ ) {
if ( MU[i] == i ) {
MU[i] = 1;
}
else if ( MU[i] == -i ) {
MU[i] = -1;
}
else if ( MU[i] < 0 ) {
MU[i] = 1;
}
else if ( MU[i] > 0 ) {
MU[i] = -1;
}
}
return MU[n];
}
}
- Output:
First 199 terms of the möbius function are as follows: 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
jq
Works with gojq, the Go implementation of jq
Using a Sieve
Adapted from C
# Input: a non-negative integer, $n
# Output: an array of size $n + 1 such that the nth-mobius number is .[$n]
# i.e. $n|mobius_array[-1]
# For example, the first mobius number could be evaluated by 1|mobius_array[-1].
def mobius_array:
. as $n
| ($n|sqrt) as $sqrt
| reduce range(2; 1 + $sqrt) as $i ([range(0; $n + 1) | 1];
if .[$i] == 1
then # for each factor found, swap + and -
reduce range($i; $n + 1; $i) as $j (.; .[$j] *= -$i)
| ($i*$i) as $isq # square factor = 0
| reduce range($isq; $n + 1; $isq) as $j (.; .[$j] = 0 )
else .
end )
| reduce range(2; 1 + $n) as $i (.;
if .[$i] == $i then .[$i] = 1
elif .[$i] == -$i then .[$i] = -1
elif .[$i] < 0 then .[$i] = 1
elif .[$i] > 0 then .[$i] = -1
else .[$i] = 0 # avoid "-0"
end);
# For one-off computations:
def mu($n): $n | mobius_array[-1];
The Task
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def task:
def pp: if . >=0 then " \(.)" else tostring end;
(199 | mobius_array) as $mu
| "The first 199 Möbius numbers are:",
([" ", (range(1; 200) | $mu[.] | pp )]
| nwise(20)
| join(" ") ) ;
task
- Output:
The first 199 Möbius numbers are: 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
Prime Factors
Note that the following solution to the task at hand (computing a range of Mobius numbers is inefficient as it does not cache the primes array. Preliminaries
# relatively_prime(previous) tests whether the input integer is prime
# relative to the primes in the array "previous":
def relatively_prime(previous):
. as $in
| (previous|length) as $plen
# state: [found, ix]
| [false, 0]
| until( .[0] or .[1] >= $plen;
[ ($in % previous[.[1]]) == 0, .[1] + 1] )
| .[0] | not ;
# Emit a stream in increasing order of all primes (from 2 onwards)
# that are less than or equal to mx:
def primes(mx):
# The helper function, next, has arity 0 for tail recursion optimization;
# it expects its input to be the array of previously found primes:
def next:
. as $previous
| ($previous | .[length-1]) as $last
| if ($last >= mx) then empty
else ((2 + $last)
| until( relatively_prime($previous) ; . + 2)) as $nextp
| if $nextp <= mx
then $nextp, (( $previous + [$nextp] ) | next)
else empty
end
end;
if mx <= 1 then empty
elif mx == 2 then 2
else (2, 3, ([2,3] | next))
end ;
# Return an array of the distinct prime factors of . in increasing order
def prime_factors:
# Return an array of prime factors of . given that "primes"
# is an array of relevant primes:
def pf($primes):
if . <= 1 then []
else . as $in
| if ($in | relatively_prime($primes)) then [$in]
else reduce $primes[] as $p
([];
if ($in % $p) != 0 then .
else . + [$p] + (($in / $p) | pf($primes))
end)
end
| unique
end;
if . <= 1 then []
else . as $in
| pf( [ primes( (1+$in) | sqrt | floor) ] )
end;
Mu
def isSquareFree:
. as $n
| 2
| until ( (. * . > $n) or . == 0;
if ($n % (.*.) == 0) then 0 # i.e. stop
elif . > 2 then . + 2
else . + 1
end )
| . != 0;
def mu:
. as $n
| if . < 1 then "Argument to mu must be a positive integer" | error
elif . == 1 then 1
else if isSquareFree
then if ((prime_factors|length) % 2 == 0) then 1
else -1
end
else 0
end
end;
The Task
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def task:
def pp: if . >=0 then " \(.)" else tostring end;
"The first 199 Möbius numbers are:",
([" ", (range(1; 200) | mu | pp )]
| nwise(20)
| join(" ") ) ;
task
- Output:
As above.
Julia
using Primes
# modified from reinermartin's PR at https://github.com/JuliaMath/Primes.jl/pull/70/files
function moebius(n::Integer)
@assert n > 0
m(p, e) = p == 0 ? 0 : e == 1 ? -1 : 0
reduce(*, m(p, e) for (p, e) in factor(n) if p ≥ 0; init=1)
end
μ(n) = moebius(n)
print("First 199 terms of the Möbius sequence:\n ")
for n in 1:199
print(lpad(μ(n), 3), n % 20 == 19 ? "\n" : "")
end
- 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
Kotlin
import kotlin.math.sqrt
fun main() {
println("First 199 terms of the möbius function are as follows:")
print(" ")
for (n in 1..199) {
print("%2d ".format(mobiusFunction(n)))
if ((n + 1) % 20 == 0) {
println()
}
}
}
private const val MU_MAX = 1000000
private var MU: IntArray? = null
// Compute mobius function via sieve
private fun mobiusFunction(n: Int): Int {
if (MU != null) {
return MU!![n]
}
// Populate array
MU = IntArray(MU_MAX + 1)
val sqrt = sqrt(MU_MAX.toDouble()).toInt()
for (i in 0 until MU_MAX) {
MU!![i] = 1
}
for (i in 2..sqrt) {
if (MU!![i] == 1) {
// for each factor found, swap + and -
for (j in i..MU_MAX step i) {
MU!![j] *= -i
}
// square factor = 0
for (j in i * i..MU_MAX step i * i) {
MU!![j] = 0
}
}
}
for (i in 2..MU_MAX) {
when {
MU!![i] == i -> {
MU!![i] = 1
}
MU!![i] == -i -> {
MU!![i] = -1
}
MU!![i] < 0 -> {
MU!![i] = 1
}
MU!![i] > 0 -> {
MU!![i] = -1
}
}
}
return MU!![n]
}
- Output:
First 199 terms of the möbius function are as follows: 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
Lua
function buildArray(size, value)
local tbl = {}
for i=1, size do
table.insert(tbl, value)
end
return tbl
end
MU_MAX = 1000000
sqroot = math.sqrt(MU_MAX)
mu = buildArray(MU_MAX, 1)
for i=2, sqroot do
if mu[i] == 1 then
-- for each factor found, swap + and -
for j=i, MU_MAX, i do
mu[j] = mu[j] * -i
end
-- square factor = 0
for j=i*i, MU_MAX, i*i do
mu[j] = 0
end
end
end
for i=2, MU_MAX do
if mu[i] == i then
mu[i] = 1
elseif mu[i] == -i then
mu[i] = -1
elseif mu[i] < 0 then
mu[i] = 1
elseif mu[i] > 0 then
mu[i] = -1
end
end
print("First 199 terms of the mobius function are as follows:")
io.write(" ")
for i=1, 199 do
io.write(string.format("%2d ", mu[i]))
if (i + 1) % 20 == 0 then
print()
end
end
- Output:
First 199 terms of the mobius function are as follows: 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
Mathematica/Wolfram Language
Grid[Partition[MoebiusMu[Range[99]], UpTo[10]]]
- Output:
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
Nim
Uses the prime decomposition method from https://rosettacode.org/wiki/Prime_decomposition#Nim
import std/[math, sequtils, strformat]
func getStep(n: int): int {.inline.} =
result = 1 + n shl 2 - n shr 1 shl 1
func primeFac(n: int): seq[int] =
var
maxq = int(sqrt(float(n)))
d = 1
q: int = 2 + (n and 1) # Start with 2 or 3 according to oddity.
while q <= maxq and n %% q != 0:
q = getStep(d)
inc d
if q <= maxq:
let q1 = primeFac(n /% q)
let q2 = primeFac(q)
result = concat(q2, q1, result)
else:
result.add(n)
func squareFree(num: int): bool =
let fact = primeFac num
for i in fact:
if fact.count(i) > 1:
return false
return true
func mobius(num: int): int =
if num == 1: return num
let fact = primeFac num
for i in fact:
## check if it has a squared prime factor
if fact.count(i) == 2:
return 0
if num.squareFree:
if fact.len mod 2 == 0:
return 1
else:
return -1
when isMainModule:
echo "The first 199 möbius numbers are:"
for i in 1..199:
stdout.write fmt"{mobius(i):4}"
if i mod 20 == 0:
echo "" # print newline
- Output:
The first 199 möbius numbers are: 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 0
Pascal
See Mertens_function#Pascal
Perl
use utf8;
use strict;
use warnings;
use feature 'say';
use List::Util 'uniq';
sub prime_factors {
my ($n, $d, @factors) = (shift, 1);
while ($n > 1 and $d++) {
$n /= $d, push @factors, $d until $n % $d;
}
@factors
}
sub μ {
my @p = prime_factors(shift);
@p == uniq(@p) ? 0 == @p%2 ? 1 : -1 : 0;
}
my @möebius;
push @möebius, μ($_) for 1 .. (my $upto = 199);
say "Möbius sequence - First $upto terms:\n" .
(' 'x4 . sprintf "@{['%4d' x $upto]}", @möebius) =~ s/((.){80})/$1\n/gr;
- 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
Phix
with javascript_semantics function Moebius(integer n) if n=1 then return 1 end if sequence f = prime_factors(n,true) for i=2 to length(f) do if f[i] = f[i-1] then return 0 end if end for return iff(odd(length(f))?-1:+1) end function sequence s = {" ."} for i=1 to 199 do s = append(s,sprintf("%3d",Moebius(i))) end for puts(1,join_by(s,1,20," "))
- Output:
. 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
Python
Everything verbatim from: https://www.geeksforgeeks.org/program-mobius-function/
All code by: Manish Shaw
Method 1
We iterate through all numbers i smaller than or equal to N. For every number we check if it divides N. If yes, we check if it’s also prime. If both conditions are satisfied, we check if its square also divides N. If yes, we return 0. If the square doesn’t divide, we increment count of prime factors. Finally, we return 1 if there are an even number of prime factors and return -1 if there are odd number of prime factors.
# Python Program to evaluate
# Mobius def M(N) = 1 if N = 1
# M(N) = 0 if any prime factor
# of N is contained twice
# M(N) = (-1)^(no of distinct
# prime factors)
# Python Program to
# evaluate Mobius def
# M(N) = 1 if N = 1
# M(N) = 0 if any
# prime factor of
# N is contained twice
# M(N) = (-1)^(no of
# distinct prime factors)
# def to check if
# n is prime or not
def isPrime(n) :
if (n < 2) :
return False
for i in range(2, n + 1) :
if (i * i <= n and n % i == 0) :
return False
return True
def mobius(N) :
# Base Case
if (N == 1) :
return 1
# For a prime factor i
# check if i^2 is also
# a factor.
p = 0
for i in range(1, N + 1) :
if (N % i == 0 and
isPrime(i)) :
# Check if N is
# divisible by i^2
if (N % (i * i) == 0) :
return 0
else :
# i occurs only once,
# increase f
p = p + 1
# All prime factors are
# contained only once
# Return 1 if p is even
# else -1
if(p % 2 != 0) :
return -1
else :
return 1
# Driver Code
print("Mobius numbers from 1..99:")
for i in range(1, 100):
print(f"{mobius(i):>4}", end = '')
if i % 20 == 0: print()
# This code is contributed by
# Manish Shaw(manishshaw1)
- Output:
Mobius numbers from 1..99: 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
Method 2 (Efficient)
The idea is based on efficient program to print all prime factors of a given number. The interesting thing is, we do not need inner while loop here because if a number divides more than once, we can immediately return 0.
# Python Program to evaluate
# Mobius def M(N) = 1 if N = 1
# M(N) = 0 if any prime factor
# of N is contained twice
# M(N) = (-1)^(no of distinct
# prime factors)
import math
# def to check if n
# is prime or not
def isPrime(n) :
if (n < 2) :
return False
for i in range(2, n + 1) :
if (n % i == 0) :
return False
i = i * i
return True
def mobius(n) :
p = 0
# Handling 2 separately
if (n % 2 == 0) :
n = int(n / 2)
p = p + 1
# If 2^2 also
# divides N
if (n % 2 == 0) :
return 0
# Check for all
# other prime factors
for i in range(3, int(math.sqrt(n)) + 1) :
# If i divides n
if (n % i == 0) :
n = int(n / i)
p = p + 1
# If i^2 also
# divides N
if (n % i == 0) :
return 0
i = i + 2
if(p % 2 == 0) :
return -1
else :
return 1
# Driver Code
print("Mobius numbers from 1..99:")
for i in range(1, 100):
print(f"{mobius(i):>4}", end = '')
# This code is contributed by
# Manish Shaw(manishshaw1)
- Output:
Mobius numbers from 1..99: -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
Raku
(formerly Perl 6)
Möbius number is not defined for n == 0. Raku arrays are indexed from 0 so store a blank value at position zero to keep n and μ(n) aligned.
use Prime::Factor;
sub μ (Int \n) {
return 0 if n %% 4 or n %% 9 or n %% 25 or n %% 49 or n %% 121;
my @p = prime-factors(n);
+@p == +@p.unique ?? +@p %% 2 ?? 1 !! -1 !! 0
}
my @möbius = lazy flat '', 1, (2..*).hyper.map: -> \n { μ(n) };
# The Task
put "Möbius sequence - First 199 terms:\n",
@möbius[^200]».fmt('%3s').batch(20).join: "\n";
- 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
REXX
Note that the Möbius function is also spelled Mobius and/or Moebius, and it is also known as the mu function, where mu is the Greek symbol μ.
Programming note: This REXX version supports the specifying of the low and high values to be generated,
as well as the group size for the grid (it can be specified as 1 which will show a vertical list).
A null value will be shown as a bullet (•) when showing the Möbius value of for zero (this can be changed in the 2nd line of the mobius function).
The above "feature" was added to make the grid to be aligned with other solutions.
The function to computer some prime numbers is a bit of an overkill, but the goal was to keep it general (in case of larger/higher ranges for a Möbius sequence).
/*REXX pgm computes & shows a value grid of the Möbius function for a range of integers.*/
parse arg LO HI grp . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 0 /*Not specified? Then use the default.*/
if HI=='' | HI=="," then HI= 199 /* " " " " " " */
if grp=='' | grp=="," then grp= 20 /* " " " " " " */
/* ______ */
call genP HI /*generate primes up to the √ HI */
say center(' The Möbius sequence from ' LO " ──► " HI" ", max(50, grp*3), '═') /*title*/
$= /*variable holds output grid of GRP #s.*/
do j=LO to HI; $= $ right( mobius(j), 2) /*process some numbers from LO ──► HI.*/
if words($)==grp then do; say substr($, 2); $= /*show grid if fully populated,*/
end /* and nullify it for more #s.*/
end /*j*/ /*for small grids, using wordCnt is OK.*/
if $\=='' then say substr($, 2) /*handle any residual numbers not shown*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
mobius: procedure expose @.; parse arg x /*obtain a integer to be tested for mu.*/
if x<1 then return '∙' /*special? Then return symbol for null.*/
#= 0 /*start with a value of zero. */
do k=1; p= @.k /*get the Kth (pre─generated) prime.*/
if p>x then leave /*prime (P) > X? Then we're done. */
if p*p>x then do; #= #+1; leave /*prime (P**2 > X? Bump # and leave.*/
end
if x//p==0 then do; #= #+1 /*X divisible by P? Bump mu number. */
x= x % p /* Divide by prime. */
if x//p==0 then return 0 /*X÷by P? Then return zero*/
end
end /*k*/ /*# (below) is almost always small, <9*/
if #//2==0 then return 1 /*Is # even? Then return postive 1 */
return -1 /* " " odd? " " negative 1. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6= 13; nP=6 /*assign low primes; # primes.*/
do lim=nP until lim*lim>=HI /*only keep primes up to the sqrt(HI).*/
end /*lim*/
do j=@.nP+4 by 2 to HI /*only find odd primes from here on. */
parse var j '' -1 _;if _==5 then iterate /*Is last digit a "5"? Then not prime*/
if j// 3==0 then iterate /*is J divisible by 3? " " " */
if j// 7==0 then iterate /* " " " " 7? " " " */
if j//11==0 then iterate /* " " " " 11? " " " */
if j//13==0 then iterate /* " " " " 13? " " " */
do k=7 while k*k<=j /*divide by some generated odd primes. */
if j // @.k==0 then iterate j /*Is J divisible by P? Then not prime*/
end /*k*/ /* [↓] a prime (J) has been found. */
nP= nP+1; if nP<=HI then @.nP= j /*bump prime count; assign prime to @.*/
end /*j*/; return
- output when using the default inputs:
Output note: note the use of a bullet (•) to signify that a "null" is being shown (for the 0th entry).
══════════ The Möbius sequence from 0 ──► 199 ═══════════ ∙ 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
Ring
mobStr = " . "
for i = 1 to 200
if mobius(i) >= 0
mobStr + = " "
ok
temp = string(mobius(i))
if left(temp,2) = "-0"
temp = right(temp,len(temp)-1)
ok
mobStr += temp + " "
if i % 10 = 9
see mobStr + nl
mobStr = " "
ok
next
func mobius(n)
if n = 1
return 1
ok
for d = 2 to ceil(sqrt(n))
if n % d = 0
if n % (d*d) = 0
return 0
ok
return -mobius(n/d)
ok
next
return -1
Output:
. 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
Ruby
require 'prime'
def μ(n)
pd = n.prime_division
return 0 unless pd.map(&:last).all?(1)
pd.size.even? ? 1 : -1
end
([" "] + (1..199).map{|n|"%2s" % μ(n)}).each_slice(20){|line| puts line.join(" ") }
- Output:
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
Sidef
Built-in:
say moebius(53) #=> -1
say moebius(54) #=> 0
say moebius(55) #=> 1
Simple implementation:
func μ(n) {
var f = n.factor_exp.map { .tail }
f.any { _ > 1 } ? 0 : ((-1)**f.sum)
}
with (199) { |n|
say "Values of the Möbius function for numbers in the range 1..#{n}:"
[' '] + (1..n->map(μ)) -> each_slice(20, {|*line|
say line.map { '%2s' % _ }.join(' ')
})
}
- Output:
Values of the Möbius function for numbers in the range 1..199: 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
Tiny BASIC
Tiny BASIC is not suited for printing tables, so this is limited to prompting for a single number and calculating its Mobius number.
PRINT "Enter an integer"
INPUT N
IF N < 0 THEN LET N = -N
IF N < 2 THEN GOTO 100 + N
LET C = 1
LET F = 2
10 IF ((N/F)/F)*F*F = N THEN GOTO 100
IF (N/F)*F = N THEN GOTO 30
20 LET F = F + 1
IF F<=N THEN GOTO 10
GOTO 100 + C
30 LET N = N / F
LET C = -C
GOTO 20
99 PRINT "-1"
END
100 PRINT "0"
END
101 PRINT "1"
END
Wren
import "/fmt" for Fmt
import "/math" for Int
var isSquareFree = Fn.new { |n|
var i = 2
while (i * i <= n) {
if (n%(i*i) == 0) return false
i = (i > 2) ? i + 2 : i + 1
}
return true
}
var mu = Fn.new { |n|
if (n < 1) Fiber.abort("Argument must be a positive integer")
if (n == 1) return 1
var sqFree = isSquareFree.call(n)
var factors = Int.primeFactors(n)
if (sqFree && factors.count % 2 == 0) return 1
if (sqFree) return -1
return 0
}
System.print("The first 199 Möbius numbers are:")
for (i in 0..9) {
for (j in 0..19) {
if (i == 0 && j == 0) {
System.write(" ")
} else {
System.write("%(Fmt.dm(3, mu.call(i*20 + j))) ")
}
}
System.print()
}
- Output:
The first 199 Möbius numbers are: 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
XPL0
func Mobius(N);
int N, Cnt, F, K;
[Cnt:= 0;
F:= 2; K:= 0;
repeat if rem(N/F) = 0 then
[Cnt:= Cnt+1;
N:= N/F;
K:= K+1;
if K >= 2 then return 0;
]
else [F:= F+1; K:= 0];
until F > N;
return if Cnt&1 then -1 else 1;
];
int N;
[Format(3, 0);
Text(0, " ");
for N:= 1 to 199 do
[RlOut(0, float(Mobius(N)));
if rem(N/20) = 19 then CrLf(0);
];
]
- Output:
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
Yabasic
outstr$ = " . "
for i = 1 to 200
if mobius(i) >= 0 then outstr$ = outstr$ + " " : fi
outstr$ = outstr$ + str$(mobius(i)) + " "
if mod(i, 10) = 9 then
print outstr$
outstr$ = ""
end if
next i
end
sub mobius(n)
if n = 1 then return 1 : fi
for d = 2 to int(sqr(n))
if mod(n, d) = 0 then
if mod(n, (d*d)) = 0 then return 0 : fi
return -mobius(n/d)
end if
next d
return -1
end sub
zkl
fcn mobius(n){
pf:=primeFactors(n);
sq:=pf.filter1('wrap(f){ (n % (f*f))==0 }); // False if square free
if(sq==False){ if(pf.len().isEven) 1 else -1 }
else 0
}
fcn primeFactors(n){ // Return a list of prime factors of n
acc:=fcn(n,k,acc,maxD){ // k is 2,3,5,7,9,... not optimum
if(n==1 or k>maxD) acc.close();
else{
q,r:=n.divr(k); // divr-->(quotient,remainder)
if(r==0) return(self.fcn(q,k,acc.write(k),q.toFloat().sqrt()));
return(self.fcn(n,k+1+k.isOdd,acc,maxD)) # both are tail recursion
}
}(n,2,Sink(List),n.toFloat().sqrt());
m:=acc.reduce('*,1); // mulitply factors
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}
[1..199].apply(mobius)
.pump(Console.println, T(Void.Read,19,False),
fcn{ vm.arglist.pump(String,"%3d".fmt) });
- Output:
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