Möbius function: Difference between revisions

← Older edit

Möbius function (view source)

Revision as of 22:43, 3 May 2024

42,863 bytes added , 2 months ago

Added various BASIC dialects (Gambas, MSX Basic, PureBasic and XBasic)

Jjuanhdez

2,170

edits

Revision as of 16:40, 25 June 2021 (view source) Shuisman (talk \| contribs) m (Switches to make it alphabetical) ← Older edit		Latest revision as of 22:43, 3 May 2024 (view source) Jjuanhdez (talk \| contribs) (Added various BASIC dialects (Gambas, MSX Basic, PureBasic and XBasic))
(64 intermediate revisions by 24 users not shown)
Line 1: {{~~draft~~ task\|Prime Numbers}} The classical '''Möbius function: μ(n)''' is an important multiplicative function in number theory and combinatorics. Line 29: :; [[Mertens function]] <br><br> =={{header\|11l}}== {{trans\|Python}} <syntaxhighlight lang="11l"> F isPrime(n) I n < 2 R 0B L(i) 2 .. n I i i <= n & n % i == 0 R 0B R 1B F mobius(n) I n == 1 R 1 V p = 0 L(i) 1 .. n I n % i == 0 & isPrime(i) I n % (i * i) == 0 R 0 E p = p + 1 I p % 2 != 0 R -1 E R 1 print(‘Mobius numbers from 1..99:’) L(i) 1..99 print(f:‘{mobius(i):4}’, end' ‘’) I i % 20 == 0 print() </syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|ALGOL 68}}== {{Trans\|C}} <~~lang~~syntaxhighlight lang="algol68">BEGIN # show the first 199 values of the moebius function # INT sq root = 1 000; Line 58 ⟶ 106: IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI OD END</~~lang~~syntaxhighlight> {{out}} <pre> Line 72 ⟶ 120: 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\|Amazing Hopper}}== {{Trans\|Python}} <syntaxhighlight lang="c"> #include <basico.h> #proto cálculodeMobius(_X_) #synon _cálculodeMobius calcularMobius algoritmo imprimir ("Mobius numbers from 1..199\n") i=0, s=1 iterar grupo( ++i, #(i<=199), calcular Mobius (i), \ solo si (#( iszero(s%20) ), NL;s=0 ), imprimir, ++s ) saltar terminar subrutinas cálculo de Mobius (n) si( #(n==0) ) ; tomar '" "' sino si( #(n==1) ); tomar '" 1"' sino; p=0 iterar para (i=1, #(i<=n+1), ++i) si ( #( iszero(n%i) && isprime(i)) ) cuando ( #( iszero(n%(ii)) ) ){ tomar '" 0"'; ir a (herejía) / ¡! / } ++p fin si siguiente tomar si ( es impar(p), " -1", " 1" ) fin si / ¡Dios! ¡Purifica esta mierda! ----+ / / \| / herejía: / <----------------------+ / retornar </syntaxhighlight> {{out}} <pre> Mobius numbers from 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 </pre> =={{header\|Arturo}}== <~~lang~~syntaxhighlight lang="rebol">mobius: function [n][ if n=0 -> return "" if n=1 -> return 1 Line 87 ⟶ 188: loop split.every:20 map 0..199 => mobius 'a -> print map a => [pad to :string & 3]</~~lang~~syntaxhighlight> {{out}} Line 101 ⟶ 202: 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\|AutoHotkey}}== <syntaxhighlight lang="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 }</syntaxhighlight> {{out}} <pre> 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</pre> =={{header\|AWK}}== <syntaxhighlight lang="awk"> ~~<lang AWK>~~ # syntax: GAWK -f MOBIUS_FUNCTION.AWK # converted from Java Line 150 ⟶ 310: return(MU[n]) } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 165 ⟶ 325: 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 </pre> =={{header\|BASIC}}== ==={{header\|Applesoft BASIC}}=== <syntaxhighlight lang="qbasic">10 HOME 20 FOR t = 0 TO 9 30 FOR u = 1 TO 10 40 n = 10t+u 50 GOSUB 130 60 IF STR$(m) = "0" THEN PRINT " 0"; 70 IF STR$(m) = "1" THEN PRINT " 1"; 80 IF STR$(m) = "-1" THEN PRINT " -1"; 90 NEXT u 100 PRINT 110 NEXT t 120 END 130 IF n = 1 THEN m = 1 : RETURN 140 m = 1 : f = 2 150 IF (n-INT(n/(ff))(ff)) = 0 THEN m = 0 : RETURN 160 IF (n-INT(n/(f))(f)) = 0 THEN GOSUB 200 170 f = f+1 180 IF f <= n THEN GOTO 150 190 RETURN 200 m = -m 210 n = n/f 220 RETURN 230 END</syntaxhighlight> {{out}} <pre>Same as GW-BASIC entry.</pre> ==={{header\|BASIC256}}=== {{trans\|FreeBASIC}} <syntaxhighlight lang="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 (dd) = 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</syntaxhighlight> {{out}} <pre>Igual que la entrada de FreeBASIC.</pre> ==={{header\|Chipmunk Basic}}=== {{works with\|Chipmunk Basic\|3.6.4}} {{works with\|GW-BASIC}} {{works with\|QBasic}} {{trans\|GW-BASIC}} <syntaxhighlight lang="qbasic">10 CLS 20 FOR t = 0 TO 9 30 FOR u = 1 TO 10 40 n = 10 t + u 50 GOSUB 110 60 PRINT USING "## "; m; 70 NEXT u 80 PRINT 90 NEXT t 100 END 110 IF n = 1 THEN m = 1: RETURN 120 m = 1: f = 2 130 IF n MOD (f * f) = 0 THEN m = 0: RETURN 140 IF n MOD f = 0 THEN GOSUB 180 150 f = f + 1 160 IF f <= n THEN GOTO 130 170 RETURN 180 m = -m 190 n = n / f 200 RETURN 210 END</syntaxhighlight> {{out}} <pre>Same as GW-BASIC entry.</pre> ==={{header\|FreeBASIC}}=== <syntaxhighlight lang="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 (dd) = 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</syntaxhighlight> {{out}} <pre> . 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\|FutureBasic}}=== <syntaxhighlight lang="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</syntaxhighlight> {{output}} <pre> 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 </pre> ==={{header\|Gambas}}=== {{trans\|FreeBASIC}} {{works with\|Windows}} <syntaxhighlight lang="vbnet">Public Sub Main() Dim outstr As String = " . " For i As Integer = 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 End Function mobius(n As Integer) As Integer If n = 1 Then Return 1 For d As Integer = 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 Return -1 End Function</syntaxhighlight> {{out}} <pre>Same as FreeBASIC entry.</pre> ==={{header\|GW-BASIC}}=== {{works with\|BASICA}} <syntaxhighlight lang="gwbasic">10 FOR T = 0 TO 9 20 FOR U = 1 TO 10 30 N = 10T + 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 (FF) = 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</syntaxhighlight> {{out}} <pre> 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 </pre> ==={{header\|Minimal BASIC}}=== {{trans\|GW-BASIC}} {{works with\|Applesoft BASIC}} {{works with\|Chipmunk Basic\|3.6.4}} {{works with\|Commodore BASIC\|3.5}} {{works with\|Nascom ROM BASIC\|4.7}} <syntaxhighlight lang="basic">10 REM Moebius function 20 FOR T = 0 TO 9 30 FOR U = 1 TO 10 40 LET N = 10T+U 50 GOSUB 110 60 PRINT M;" "; 70 NEXT U 80 PRINT 90 NEXT T 100 END 110 LET M = 1 120 IF N = 1 THEN 230 130 LET F = 2 140 LET F2 = FF 150 IF INT(N/F2)F2 <> N THEN 180 160 LET M = 0 170 GOTO 230 180 IF INT(N/F)F <> N THEN 210 190 LET M = -M 200 LET N = N/F 210 LET F = F+1 220 IF F <= N THEN 140 230 RETURN </syntaxhighlight> ==={{header\|MSX Basic}}=== {{works with\|MSX BASIC\|any}} The [[#GW-BASIC\|GW-BASIC]] solution works without any changes. ==={{header\|PureBasic}}=== {{trans\|FreeBASIC}} <syntaxhighlight lang="purebasic">Procedure.i mobius(n) If n = 1: ProcedureReturn 1 EndIf For d = 2 To Int(Sqr(n)) If Mod(n, d) = 0: If Mod(n, d * d) = 0: ProcedureReturn 0 EndIf ProcedureReturn -mobius(n / d) EndIf Next d ProcedureReturn -1 EndProcedure OpenConsole() outstr$ = " . " For i = 1 To 200 If mobius(i) >= 0: outstr$ = outstr$ + " " EndIf outstr$ = outstr$ + Str(mobius(i)) + " " If Mod(i, 10) = 9: PrintN(outstr$) outstr$ = "" EndIf Next i PrintN(#CRLF$ + "Press ENTER to exit"): Input() CloseConsole()</syntaxhighlight> {{out}} <pre>Same as FreeBASIC entry.</pre> ==={{header\|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. <syntaxhighlight lang="tinybasic"> 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)FF = 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</syntaxhighlight> ==={{header\|XBasic}}=== {{works with\|Windows XBasic}} {{trans\|FreeBASIC}} <syntaxhighlight lang="qbasic">PROGRAM "Möbius function" VERSION "0.0000" IMPORT "xma" DECLARE FUNCTION Entry () DECLARE FUNCTION mobius (n) FUNCTION Entry () outstr$ = " . " FOR i = 1 TO 200 IF mobius(i) >= 0 THEN outstr$ = outstr$ outstr$ = outstr$ + STR$(mobius(i)) + " " IF i MOD 10 = 9 THEN PRINT outstr$ outstr$ = "" END IF NEXT i END FUNCTION FUNCTION mobius (n) IF n = 1 THEN RETURN 1 FOR d = 2 TO INT(SQRT(n)) IF n MOD d = 0 THEN IF n MOD (dd) = 0 THEN RETURN 0 RETURN -mobius(n/d) END IF NEXT d RETURN -1 END FUNCTION END PROGRAM</syntaxhighlight> {{out}} <pre>Same as FreeBASIC entry.</pre> ==={{header\|Yabasic}}=== {{trans\|FreeBASIC}} <syntaxhighlight lang="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, (dd)) = 0 then return 0 : fi return -mobius(n/d) end if next d return -1 end sub</syntaxhighlight> =={{header\|C}}== {{trans\|Java}} <~~lang~~syntaxhighlight lang="c">#include <math.h> #include <stdio.h> #include <stdlib.h> Line 222 ⟶ 786: free(mu); return 0; }</~~lang~~syntaxhighlight> {{out}} <pre>First 199 terms of the m÷bius function are as follows: Line 238 ⟶ 802: =={{header\|C++}}== {{trans\|Java}} <~~lang~~syntaxhighlight lang="cpp">#include <iomanip> #include <iostream> #include <vector> Line 292 ⟶ 856: return 0; }</~~lang~~syntaxhighlight> {{out}} <pre>First 199 terms of the m÷bius function are as follows: Line 308 ⟶ 872: =={{header\|D}}== {{trans\|C++}} <~~lang~~syntaxhighlight lang="d">import std.math; import std.stdio; Line 363 ⟶ 927: } } }</~~lang~~syntaxhighlight> {{out}} <pre>First 199 terms of the m├╢bius function are as follows: Line 376 ⟶ 940: 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\|Delphi}}== {{works with\|Delphi\|6.0}} {{libheader\|SysUtils,StdCtrls}} Rather than being clever and trying to perform the task in the smallest number of lines possible, this solution breaks the problem down into its fundamental pieces and solves each one in a separate subroutine. This programming style makes the code easier understand, debug and enhance the code. While the technique is not necessary on simple problems like this, it is essential for larger and more complex programs. <syntaxhighlight lang="Delphi"> function IsPrime(N: int64): boolean; {Fast, optimised prime test} var I,Stop: int64; begin if (N = 2) or (N=3) then Result:=true else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false else begin I:=5; Stop:=Trunc(sqrt(N+0.0)); Result:=False; while I<=Stop do begin if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit; Inc(I,6); end; Result:=True; end; end; function GetNextPrime(var Start: integer): integer; {Get the next prime number after Start} {Start is passed by "reference," so the {original variable is incremented} begin repeat Inc(Start) until IsPrime(Start); Result:=Start; end; type TIntArray = array of integer; procedure StoreNumber(N: integer; var IA: TIntArray); {Expand and store number in array} begin SetLength(IA,Length(IA)+1); IA[High(IA)]:=N; end; procedure GetPrimeFactors(N: integer; var Facts: TIntArray); {Get all the prime factors of a number} var I: integer; begin I:=2; repeat begin if (N mod I) = 0 then begin StoreNumber(I,Facts); N:=N div I; end else GetNextPrime(I); end until N=1; end; function HasDuplicates(IA: TIntArray): boolean; {Look for duplicates factors in array} var I: integer; begin Result:=True; for I:=0 to Length(IA)-1 do if IA[I]=IA[I+1] then exit; Result:=False; end; function Moebius(N: integer): integer; {Get moebius function of number} var I: integer; var Factors: TIntArray; var Even,Square: boolean; begin {Collect all prime factors} SetLength(Factors,0); GetPrimeFactors(N,Factors); {Are there an even number of factors?} Even:=(Length(Factors) and 1)=0; {If there are duplicates, there are perfect squares} Square:=HasDuplicates(Factors); {Return the Moebius function value} if Square then Result:=0 else if Even then Result:=1 else Result:=-1; end; procedure TestMoebiusFactors(Memo: TMemo); {Test Moebius function for 1..200-1} var N,M: integer; var S: string; begin S:=''; for N:=1 to 199 do begin M:=Moebius(N); S:=S+Format('%3d',[M]); if (N mod 20)=19 then S:=S+#$0D#$0A end; Memo.Text:=S; end; </syntaxhighlight> {{out}} <pre> 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\|EasyLang}}== {{trans\|C}} <syntaxhighlight lang=easylang> mu_max = 100000 sqroot = floor sqrt mu_max # for i to mu_max mu[] &= 1 . for i = 2 to sqroot if mu[i] = 1 for j = i step i to mu_max mu[j] = -i . for j = i * i step i * i to mu_max mu[j] = 0 . . . for i = 2 to mu_max if mu[i] = i mu[i] = 1 elif mu[i] = -i mu[i] = -1 elif mu[i] < 0 mu[i] = 1 elif mu[i] > 0 mu[i] = -1 . . numfmt 0 3 for i = 1 to 100 write mu[i] if i mod 10 = 0 print "" . . </syntaxhighlight> =={{header\|F_Sharp\|F#}}== This task uses [[Extensible_prime_generator#The_functions\|Extensible Prime Generator (F#)]] <~~lang~~syntaxhighlight lang="fsharp"> // Möbius function. Nigel Galloway: January 31st., 2021 let fN g=let n=primes32() Line 389 ⟶ 1,122: 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 "") </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 417 ⟶ 1,150: 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~~syntaxhighlight 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~~syntaxhighlight> {{out}} <pre> Line 439 ⟶ 1,172: =={{header\|Fortran}}== {{Trans\|C}} <~~lang~~syntaxhighlight lang="fortran"> program moebius use iso_fortran_env, only: output_unit Line 481 ⟶ 1,214: end do end program moebius </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 497 ⟶ 1,229: 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 </pre> ~~=={{header\|FreeBASIC}}==~~ ~~<lang 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 (dd) = 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</lang>~~ ~~{{out}}~~ ~~<pre>~~ ~~. 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\|Go}}== <~~lang~~syntaxhighlight lang="go">package main import "fmt" Line 598 ⟶ 1,286: fmt.Printf(" % d", mobs[i]) } }</~~lang~~syntaxhighlight> {{out}} Line 615 ⟶ 1,303: </pre> =={{header\|~~GW-BASIC~~Haskell}}== <syntaxhighlight lang="haskell">import Data.List (intercalate) ~~<lang gwbasic>10 FOR T = 0 TO 9~~ import Data.List.Split (chunksOf) ~~20 FOR U = 1 TO 10~~ import Data.Vector.Unboxed (toList) ~~30 N = 10T + U~~ import Math.NumberTheory.ArithmeticFunctions.Moebius (Moebius(..), ~~40 GOSUB 100~~ sieveBlockMoebius) ~~50 PRINT USING "## ";M;~~ import System.Environment (getArgs, getProgName) ~~60 NEXT U~~ import System.IO (hPutStrLn, stderr) ~~70 PRINT~~ import Text.Read (readMaybe) ~~80 NEXT T~~ ~~90 END~~ -- Calculate the Möbius function, μ(n), for a sequence of values starting at 1. ~~100 IF N = 1 THEN M = 1 : RETURN~~ moebiusBlock :: Word -> [Moebius] ~~110 M = 1 : F = 2~~ moebiusBlock = toList . sieveBlockMoebius 1 ~~120 IF N MOD (FF) = 0 THEN M = 0 : RETURN~~ ~~130 IF N MOD F = 0 THEN GOSUB 170~~ showMoebiusBlock :: Word -> [Moebius] -> String ~~140 F = F + 1~~ showMoebiusBlock cols = intercalate "\n" . map (concatMap showMoebius) . ~~150 IF F <= N THEN GOTO 120~~ chunksOf (fromIntegral cols) ~~160 RETURN~~ where showMoebius MoebiusN = " -1" ~~170 M = -M~~ showMoebius MoebiusZ = " 0" ~~180 N = N/F~~ showMoebius MoebiusP = " 1" ~~190 RETURN</lang>~~ 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"</syntaxhighlight> {{out}} <pre> μ(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 </pre> =={{header\|J}}== Implementation: <syntaxhighlight lang="j">mu=: /@:-@~:@q:</syntaxhighlight> Explanation: <code>q: n</code> gives the list of prime factors of n. (This is an empty list for the number 1, is <code>2 2 5 5</code> for the number 100, and is <code>2 2 2 3 5</code> for the number 120.) In this context <code>~:</code> replaces each prime factor either by 1, if it is its first occurrence, or by 0, if it is a repetition (e.g. <code>2 2 5 5</code> → <code>1 0 1 0</code>). Then, <code>-</code> simply negates this list (e.g. <code>1 0 1 0</code> → <code>_1 0 _1 0</code>), and finally <code>/</code> multiplies all list elements to get the desired result. Task example: <syntaxhighlight lang="j"> mu >: 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</syntaxhighlight> =={{header\|Java}}== <~~lang~~syntaxhighlight lang="java"> public class MöbiusFunction { Line 697 ⟶ 1,432: } </syntaxhighlight> ~~</lang>~~ {{out}} Line 714 ⟶ 1,449: </pre> =={{header\|jq}}== {{works with\|jq}} '''Works with gojq, the Go implementation of jq''' ====Using a Sieve==== '''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] # 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];</syntaxhighlight> '''The Task''' <syntaxhighlight lang="jq">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</syntaxhighlight> {{out}} <pre> 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 </pre> ==== 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''' <syntaxhighlight lang="jq"># 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;</syntaxhighlight> '''Mu''' <syntaxhighlight lang="jq">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;</syntaxhighlight> '''The Task''' <syntaxhighlight lang="jq">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</syntaxhighlight> {{out}} As above. =={{header\|Julia}}== <~~lang~~syntaxhighlight lang="julia">using Primes # modified from reinermartin's PR at https://github.com/JuliaMath/Primes.jl/pull/70/files Line 730 ⟶ 1,619: print(lpad(μ(n), 3), n % 20 == 19 ? "\n" : "") end </~~lang~~syntaxhighlight>{{out}} <pre> First 199 terms of the Möbius sequence: Line 747 ⟶ 1,636: =={{header\|Kotlin}}== {{trans\|Java}} <~~lang~~syntaxhighlight lang="scala">import kotlin.math.sqrt fun main() { Line 804 ⟶ 1,693: } return MU!![n] }</~~lang~~syntaxhighlight> {{out}} <pre>First 199 terms of the möbius function are as follows: Line 820 ⟶ 1,709: =={{header\|Lua}}== {{trans\|C}} <~~lang~~syntaxhighlight lang="lua">function buildArray(size, value) local tbl = {} for i=1, size do Line 864 ⟶ 1,753: print() end end</~~lang~~syntaxhighlight> {{out}} <pre>First 199 terms of the mobius function are as follows: Line 879 ⟶ 1,768: =={{header\|Mathematica}}/{{header\|Wolfram Language}}== <~~lang~~syntaxhighlight ~~Mathematica~~lang="mathematica">Grid[Partition[MoebiusMu[Range[99]], UpTo[10]]]</~~lang~~syntaxhighlight> {{out}} <pre>1 -1 -1 0 -1 1 -1 0 0 1 Line 891 ⟶ 1,780: 0 1 -1 0 1 1 1 0 -1 0 1 0 1 1 1 0 -1 0 0 </pre> =={{header\|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.} = 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 </syntaxhighlight> {{out}} <pre>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</pre> =={{header\|PARI/GP}}== {{trans\|Julia}} <syntaxhighlight lang="PARI/GP"> { for(i = 1, 99, print1(moebius(i) " "); if(i % 10 == 0, print("\n");); ); } </syntaxhighlight> {{out}} <pre> 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 </pre> =={{header\|Pascal}}== Line 896 ⟶ 1,890: =={{header\|Perl}}== <~~lang~~syntaxhighlight lang="perl">use utf8; use strict; use warnings; Line 919 ⟶ 1,913: say "Möbius sequence - First $upto terms:\n" . (' 'x4 . sprintf "@{['%4d' x $upto]}", @möebius) =~ s/((.){80})/$1\n/gr;</~~lang~~syntaxhighlight> {{out}} <pre>Möbius sequence - First 199 terms: Line 934 ⟶ 1,928: =={{header\|Phix}}== <!--<syntaxhighlight lang="phix">(phixonline)--> ~~<lang Phix>function Moebius(integer n)~~ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> ~~if n=1 then return 1 end if~~ <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> ~~sequence f = prime_factors(n,true)~~ <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~for i=2 to length(f) do~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> ~~if f[i] = f[i-1] then return 0 end if~~ <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> ~~end for~~ <span style="color: #008080;">if</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> ~~return iff(and_bits(length(f),1)?-1:+1)~~ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> ~~end function~~ <span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">))?-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> ~~sequence s = {" ."}~~ ~~for i=1 to 199 do s = append(s,sprintf("%3d",Moebius(i))) end for~~ <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">" ."</span><span style="color: #0000FF;">}</span> ~~puts(1,join_by(s,1,20," "))</lang>~~ <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> <!--</syntaxhighlight>--> {{out}} <pre> Line 959 ⟶ 1,956: 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 </pre> =={{header\|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. <syntaxhighlight lang="python"> # 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)</syntaxhighlight> {{out}} <pre>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</pre> 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. # BUGS ! mu(1): computes -1, correct 1 # BUGS ! mu(2): computes 1, correct -1 # BUGS ! mu(105): computes 1, correct -1 # BUGS ! ... # Some other programs say: "Translation of Python", probably of this one. <syntaxhighlight lang="python"># 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)</syntaxhighlight> {{out}} <pre>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</pre> =={{header\|Quackery}}== <code>primefactors</code> is defined at [[Prime decomposition#Quackery]]. <syntaxhighlight lang="Quackery"> [ false swap behead swap [ witheach [ tuck != if done dip not conclude ] ] drop ] is square ( [ --> b ) [ 1 & ] is odd ( n --> b ) [ dup 1 = if done primefactors dup square iff [ drop 0 ] done size odd iff -1 else 1 ] is mobius ( n --> n ) say "First 199 terms:" cr say " " 199 times [ i^ 1+ mobius dup -1 > if sp echo i^ 1+ 20 mod 19 = iff cr else [ sp sp ] ]</syntaxhighlight> {{out}} <pre>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> =={{header\|Raku}}== (formerly Perl 6) {{works with\|Rakudo\|~~2019~~2022.1112}} 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. <syntaxhighlight lang="raku" ~~perl6~~line>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";</~~lang~~syntaxhighlight> {{out}} <pre>Möbius sequence - First 199 terms: Line 1,003 ⟶ 2,214: 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). <~~lang~~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/ if LO=='' \| LO=="," then LO= 0 /Not specified? Then use the default./ Line 1,048 ⟶ 2,259: 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</~~lang~~syntaxhighlight> {{out\|output\|text=  when using the default inputs:}} Line 1,068 ⟶ 2,279: =={{header\|Ring}}== {{Trans\|FreeBASIC}} <~~lang~~syntaxhighlight lang="ring"> mobStr = " . " Line 1,099 ⟶ 2,310: next return -1 </syntaxhighlight> ~~</lang>~~ Output: <pre> Line 1,123 ⟶ 2,334: -1 -1 0 -1 1 -1 0 -1 0 -1 </pre> =={{header\|RPL}}== {{trans\|FreeBASIC}} RPL does not allow that a function returns something whilst in the middle of a branch, so we have to play here with index saturation and flag use to mimic the short returns that many other languages accept. {{works with\|Halcyon Calc\|4.2.7}} {\| class="wikitable" ! RPL code ! Comment \|- \| ≪ '''IF''' DUP 1 ≠ '''THEN''' → n ≪ -1 2 n √ '''FOR''' d '''IF''' n d MOD NOT '''THEN''' 1 CF '''IF''' n d SQ MOD NOT '''THEN''' n 'd' STO DROP 0 1 SF '''END''' '''IF''' 1 FC? '''THEN''' DROP n d / n 'd' STO '''MU''' NEG '''END''' '''END''' '''NEXT''' ≫ '''END''' ≫ '<span style="color:blue">MU</span>' STO \| <span style="color:blue">MU</span> ''( n -- µ(n) )'' if n = 1 then return 1 // default return value put in stack for d as uinteger = 2 to int(sqr(n)) if n mod d = 0 then if n mod (dd) = 0 then return 0 // and set flag // if flag not set, return -mobius(n/d) end if next d \|} ≪ 1 100 '''FOR''' li "" li DUP 19 + '''FOR''' j "-0+" j <span style="color:blue">MU</span> 2 + DUP SUB + '''NEXT''' 20 '''STEP''' ≫ EVAL {{out}} <pre> 5: "+--0-+-00+-0-++0-0-0" 4: "++-00+00---0+++0-++0" 3: "---00+-000+0-0+0++-0" 2: "-+00+--0+--0-+00+--0" 1: "0+-0+++0-0+0+++0-000" </pre> {{works with\|HP\|49/50}} Improvement of an implementation found on the [https://www.hpmuseum.org/forum/thread-10330-post-93200.html#pid93200 MoHPC forum] « '''CASE''' DUP 1 ≤ '''THEN END''' FACTOR DUP TYPE 9 ≠ '''THEN''' DROP -1 '''END''' DUP →STR "^" POS '''THEN''' DROP 0 '''END''' SIZE 1 + 2 / 1 SWAP 2 MOD { NEG } IFT '''END''' » '<span style="color:blue">MU</span>' STO « 1 100 '''FOR''' j j 20 MOD 1 == "" IFT "-0+" j <span style="color:blue">MU</span> 2 + DUP SUB + '''NEXT''' » '<span style="color:blue">TASK</span>' STO Same output. =={{header\|Ruby}}== <~~lang~~syntaxhighlight lang="ruby">require 'prime' def μ(n) Line 1,135 ⟶ 2,411: ([" "] + (1..199).map{\|n\|"%2s" % μ(n)}).each_slice(20){\|line\| puts line.join(" ") } </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 1,148 ⟶ 2,424: 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\|Rust}}== <syntaxhighlight lang="rust"> fn moebius(mut x: u64) -> i8 { let mut prime_count = 0; // If x is divisible by the given factor this macro counts the factor and divides it out. // It then returns zero if x is still divisible by the factor. macro_rules! divide_x_by { ($factor:expr) => { if x % $factor == 0 { x /= $factor; prime_count += 1; if x % $factor == 0 { return 0; } } }; } // Handle 2 and 3 separately, divide_x_by!(2); divide_x_by!(3); // then use a wheel sieve to check the remaining factors <= √x. for i in (5..=isqrt(x)).step_by(6) { divide_x_by!(i); divide_x_by!(i + 2); } // There can exist one prime factor larger than √x, // in that case we can check if x is still larger than one, and then count it. if x > 1 { prime_count += 1; } if prime_count % 2 == 0 { 1 } else { -1 } } /// Returns the largest integer smaller than or equal to `√n` const fn isqrt(n: u64) -> u64 { if n <= 1 { n } else { let mut x0 = u64::pow(2, n.ilog2() / 2 + 1); let mut x1 = (x0 + n / x0) / 2; while x1 < x0 { x0 = x1; x1 = (x0 + n / x0) / 2; } x0 } } fn main() { const ROWS: u64 = 10; const COLS: u64 = 20; println!( "Values of the Möbius function, μ(x), for x between 0 and {}:", COLS * ROWS ); for i in 0..ROWS { for j in 0..=COLS { let x = COLS * i + j; let μ = moebius(x); if μ >= 0 { // Print an extra space if there's no minus sign in front of the output // in order to align the numbers in a nice grid. print!(" "); } print!("{μ} "); } println!(); } let x = u64::MAX; println!("\nμ({x}) = {}", moebius(x)); } </syntaxhighlight> {{out}} <pre> Values of the Möbius function, μ(x), for x between 0 and 200: 0 1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1 0 0 1 1 -1 0 0 1 0 0 -1 -1 -1 0 1 1 1 0 -1 1 1 0 0 -1 -1 -1 0 0 1 -1 0 0 0 1 0 -1 0 1 0 1 1 -1 0 0 -1 1 0 0 1 -1 -1 0 1 -1 -1 0 -1 1 0 0 1 -1 -1 0 0 0 1 -1 0 1 1 1 0 -1 0 1 0 1 1 1 0 -1 0 0 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 1 0 0 0 -1 0 1 -1 -1 0 1 1 0 0 -1 -1 -1 0 0 1 1 1 0 1 1 0 0 -1 0 -1 0 0 -1 1 0 -1 1 1 0 0 1 0 -1 0 -1 1 -1 0 0 -1 0 0 -1 -1 0 0 1 1 -1 0 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 0 μ(18446744073709551615) = -1 </pre> Line 1,153 ⟶ 2,527: Built-in: <~~lang~~syntaxhighlight lang="ruby">say moebius(53) #=> -1 say moebius(54) #=> 0 say moebius(55) #=> 1</~~lang~~syntaxhighlight> Simple implementation: <~~lang~~syntaxhighlight lang="ruby">func μ(n) { var f = n.factor_exp.map { .tail } f.any { _ > 1 } ? 0 : ((-1)*f.sum) Line 1,168 ⟶ 2,542: say line.map { '%2s' % _ }.join(' ') }) }</~~lang~~syntaxhighlight> {{out}} <pre> Line 1,183 ⟶ 2,557: 0 -1 -1 1 0 1 -1 1 0 0 -1 -1 0 -1 1 -1 0 -1 0 -1 </pre> ~~=={{header\|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.~~ ~~<lang tinybasic> 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)FF = 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</lang>~~ =={{header\|Wren}}== {{libheader\|Wren-fmt}} {{libheader\|Wren-math}} <~~lang~~syntaxhighlight ~~ecmascript~~lang="wren">import "./fmt" for Fmt import "./math" for Int var isSquareFree = Fn.new { \|n\| Line 1,239 ⟶ 2,589: System.write(" ") } else { ~~System~~Fmt.write("~~%(Fmt.dm(3~~$ 3d ", mu.call(i20 + j)~~)) "~~) } } System.print() }</~~lang~~syntaxhighlight> {{out}} Line 1,258 ⟶ 2,608: 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\|XPL0}}== <syntaxhighlight lang="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); ]; ]</syntaxhighlight> {{out}} <pre> 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\|zkl}}== <~~lang~~syntaxhighlight lang="zkl">fcn mobius(n){ pf:=primeFactors(n); sq:=pf.filter1('wrap(f){ (n % (ff))==0 }); // False if square free Line 1,279 ⟶ 2,668: if(n!=m) acc.append(n/m); // opps, missed last factor else acc; }</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="zkl">[1..199].apply(mobius) .pump(Console.println, T(Void.Read,19,False), fcn{ vm.arglist.pump(String,"%3d".fmt) });</~~lang~~syntaxhighlight> {{out}} <pre>