Mertens function: Difference between revisions
(35 intermediate revisions by 23 users not shown) | |||
Line 32:
:* [[Möbius function]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F mertens(count)
‘Generate Mertens numbers’
V m = [-1, 1]
L(n) 2 .. count
m.append(1)
L(k) 2 .. n
m[n] -= m[n I/ k]
R m
V ms = mertens(1000)
print(‘The first 99 Mertens numbers are:’)
print(‘ ’, end' ‘ ’)
V col = 1
L(n) ms[1.<100]
print(‘#2’.format(n), end' ‘ ’)
col++
I col == 10
print()
col = 0
V zeroes = sum(ms.map(x -> Int(x == 0)))
V crosses = sum(zip(ms, ms[1..]).map((a, b) -> Int(a != 0 & b == 0)))
print(‘M(N) equals zero #. times.’.format(zeroes))
print(‘M(N) crosses zero #. times.’.format(crosses))</syntaxhighlight>
{{out}}
<pre>
The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) equals zero 92 times.
M(N) crosses zero 59 times.
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Mertens function - 01/05/2023
MERTENS CSECT
USING MERTENS,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R0,1 1
STH R0,MM m(1)=1
LA R6,2 i=2
DO WHILE=(CH,R6,LE,=AL2(NN)) do i=2 to n
LR R1,R6 i
SLA R1,1 *2 (H)
LA R0,1 1
STH R0,MM-2(R1) m(i)=1
LA R7,2 j=2
DO WHILE=(CR,R7,LE,R6) do j=2 to i
LR R4,R6 i
SRDA R4,32 ~
LR R1,R7 j
DR R4,R1 i/j
LR R8,R5 d=i/j
LR R4,R6 i
SLA R4,1 *2 (H)
LH R2,MM-2(R4) m(i)
LR R1,R8 d
SLA R1,1 *2 (H)
LH R3,MM-2(R1) m(d)
SR R2,R3 m(i)-m(d)
STH R2,MM-2(R4) m(i)=m(i)-m(d)
LA R7,1(R7) j++
ENDDO , enddo j
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT =C'the first 99 Mertens numbers are:',34 print buffer
LA R9,PG @buffer=pg
MVC PG,=CL80' ' clean buffer
MVC 0(3,R9),=CL3' ' output ' '
LA R9,3(R9) @buffer+=3
LA R7,9 j=9
LA R6,1 i=1
DO WHILE=(CH,R6,LE,=AL2(99)) do i=1 to 99
LR R1,R6 i
SLA R1,1 *2 (H)
LH R2,MM-2(R1) m(i)
XDECO R2,XDEC edit m(i)
MVC 0(3,R9),XDEC+9 output m(i)
LA R9,3(R9) @buffer+=3
BCTR R7,0 j=j-1
IF LTR,R7,Z,R7 THEN if j=0 then do;
LA R7,10 j=10
XPRNT PG,L'PG print buffer
LA R9,PG @buffer=pg
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
SR R10,R10 zero=0
SR R11,R11 cross=0
LA R6,1 i=2
DO WHILE=(CH,R6,LE,=AL2(NN)) do i=2 to n
LR R1,R6 i
SLA R1,1 *2 (H)
LH R2,MM-2(R1) m(i)
IF LTR,R2,Z,R2 THEN if m(i)=0 then
LA R10,1(R10) zero=zero+1
LR R1,R6 i
BCTR R1,0 i-1
SLA R1,1 *2 (H)
LH R2,MM-2(R1) m(i-1)
IF LTR,R2,NZ,R2 THEN if m(i-1)^=0 then
LA R11,1(R11) cross=cross+1
ENDIF , endif
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
MVC PG,=CL80' ' clean buffer
MVC PG(13),=C'm(i) is zero '
XDECO R10,XDEC edit zero
MVC PG+13(2),XDEC+10 output zero
MVC PG+15(7),=C' times.'
XPRNT PG,L'PG print buffer
MVC PGI,=H'0'
MVC PG,=CL80' ' clean buffer
MVC PG(18),=C'm(i) crosses zero '
XDECO R11,XDEC edit cross
MVC PG+18(2),XDEC+10 output cross
MVC PG+20(7),=C' times.'
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
NN EQU 1000 n
PG DS CL80 buffer
PGI DC H'0' buffer index
XDEC DS CL12 temp for xdeci xdeco
MM DS (NN)H m
REGEQU
END MERTENS</syntaxhighlight>
{{out}}
<pre>
the first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
m(i) is zero 92 times.
m(i) crosses zero 59 times.
</pre>
=={{header|8080 Assembly}}==
<
org 100h
;;; Generate Mertens numbers
Line 232 ⟶ 395:
tms: db ' times.$'
;;; Numbers are stored page-aligned after program
MM: equ ($/256)*256+256 </
{{out}}
Line 249 ⟶ 412:
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|8086 Assembly}}==
<
puts: equ 9 ; MS-DOS syscall to print a string
putch: equ 2 ; MS-DOS syscall to print a character
Line 353 ⟶ 515:
section .bss
mm: resb MAX ; Mertens numbers
M: equ mm-1 ; 1-based indexing</
{{out}}
Line 370 ⟶ 532:
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Action!}}==
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.
{{libheader|Action! Tool Kit}}
<syntaxhighlight lang="action!">INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit
PROC MertensNumbers(INT ARRAY m INT count)
INT n,k
m(1)=1
FOR n=2 TO count
DO
m(n)=1
FOR k=2 TO n
DO
m(n)==-m(n/k)
OD
OD
RETURN
PROC PrintMertens(INT ARRAY m INT count)
CHAR ARRAY s(6)
INT i,col
PrintF("First %I Mertens numbers:%E ",count)
col=1
FOR i=1 TO count
DO
StrI(m(i),s)
PrintF("%3S",s)
col==+1
IF col=10 THEN
col=0 PutE()
FI
OD
RETURN
PROC Main()
DEFINE MAX="1001"
INT ARRAY m(MAX)
INT i,zeroCnt=[0],crossCnt=[0],prev=[0]
Put(125) PutE() ;clear the screen
PrintF("Calculation of Mertens numbers,%E please wait...")
MertensNumbers(m,MAX)
Put(125) PutE() ;clear the screen
PrintMertens(m,99)
FOR i=1 TO MAX
DO
IF m(i)=0 THEN
zeroCnt==+1
IF prev THEN
crossCnt==+1
FI
FI
prev=m(i)
OD
PrintF("%EM(n) is zero %I times for 1<=n<=%I.%E",zeroCnt,MAX-1)
PrintF("%EM(n) crosses zero %I times for 1<=n<=%I.%E",crossCnt,MAX-1)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Mertens_function.png Screenshot from Atari 8-bit computer]
<pre>
First 99 Mertens numbers:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(n) is zero 92 times for 1<=n<=1000.
M(n) crosses zero 59 times for 1<=n<=1000.
</pre>
=={{header|ALGOL 68}}==
{{Trans|ALGOL W}}
...which is...
{{Trans|Fortran}}
<syntaxhighlight lang="algol68">BEGIN # compute values of the Mertens function #
# Generate Mertens numbers #
[ 1 : 1000 ]INT m;
m[ 1 ] := 1;
FOR n FROM 2 TO UPB m DO
m[ n ] := 1;
FOR k FROM 2 TO n DO m[ n ] -:= m[ n OVER k ] OD
OD;
# Print table #
print( ( "The first 99 Mertens numbers are:", newline ) );
print( ( " " ) );
INT k := 9;
FOR n TO 99 DO
print( ( whole( m[ n ], -3 ) ) );
IF ( k -:= 1 ) = 0 THEN
k := 10;
print( ( newline ) )
FI
OD;
# Calculate zeroes and crossings #
INT zero := 0;
INT cross := 0;
FOR n FROM 2 TO UPB m DO
IF m[ n ] = 0 THEN
zero +:= 1;
IF m[ n - 1 ] /= 0 THEN cross +:= 1 FI
FI
OD;
print( ( newline ) );
print( ( "M(N) is zero ", whole( zero, -4 ), " times.", newline ) );
print( ( "M(N) crosses zero ", whole( cross, -4 ), " times.", newline ) )
END</syntaxhighlight>
{{out}}
<pre>
The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.
</pre>
=={{header|ALGOL W}}==
{{Trans|Fortran}}
<syntaxhighlight lang="algolw">begin % compute values of the Mertens function %
integer array M ( 1 :: 1000 );
integer k, zero, cross;
% Generate Mertens numbers %
M( 1 ) := 1;
for n := 2 until 1000 do begin
M( n ) := 1;
for k := 2 until n do M( n ) := M( n ) - M( n div k )
end for_n ;
% Print table %
write( "The first 99 Mertens numbers are:" );
write( " " );
k := 9;
for n := 1 until 99 do begin
writeon( i_w := 3, s_w := 0, M( n ) );
k := k - 1;
if k = 0 then begin
k := 10;
write()
end if_k_eq_0
end for_n ;
% Calculate zeroes and crossings %
zero := 0;
cross := 0;
for n :=2 until 1000 do begin
if M( n ) = 0 then begin
zero := zero + 1;
if M( n - 1 ) not = 0 then cross := cross + 1
end if_M_n_eq_0
end for_n ;
write( i_w := 2, s_w := 0, "M(N) is zero ", zero, " times." );
write( i_w := 2, s_w := 0, "M(N) crosses zero ", cross, " times." )
end.</syntaxhighlight>
{{out}}
<pre>
The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<
step ← {⍵,-⍨/⌽1,⍵[⌊n÷1↓⍳n←1+≢⍵]}
m1000 ← step⍣999⊢,1
Line 382 ⟶ 732:
⎕←'M(N) is zero ',(⍕zero),' times.'
⎕←'M(N) crosses zero ',(⍕cross),' times.'
}</
{{out}}
Line 399 ⟶ 749:
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">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
]
mertens: function [z][sum map 1..z => mobius]
print "The first 99 Mertens numbers are:"
loop split.every:20 [""]++map 1..99 => mertens 'a [
print map a 'item -> pad to :string item 2
]
print ""
mertens1000: map 1..1000 => mertens
print ["Times M(x) is zero between 1 and 1000:" size select mertens1000 => zero?]
crossed: new 0
fold mertens1000 [a,b][if and? zero? b not? zero? a -> inc 'crossed, b]
print ["Times M(x) crosses zero between 1 and 1000:" crossed]</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1
Times M(x) is zero between 1 and 1000: 92
Times M(x) crosses zero between 1 and 1000: 59</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">result := "first 100 terms:`n"
loop 100
result .= SubStr(" " Mertens(A_Index), -1) . (Mod(A_Index, 10) ? " " : "`n")
eqZero := crZero := 0, preced:=1
loop 1000
{
if !(x := Mertens(A_Index))
eqZero++, crZero += preced<>0 ? 1 : 0
preced := x
}
result .= "`nfirst 1000 terms:"
MsgBox, 262144, , % result .= "`nequal to zero : " eqZero "`ncrosses zero : " crZero
return
Mertens(n){
loop % n
result += Möbius(A_Index)
return result
}
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>first 100 terms:
1 0 -1 -1 -2 -1 -2 -2 -2 -1
-2 -2 -3 -2 -1 -1 -2 -2 -3 -3
-2 -1 -2 -2 -2 -1 -1 -1 -2 -3
-4 -4 -3 -2 -1 -1 -2 -1 0 0
-1 -2 -3 -3 -3 -2 -3 -3 -3 -3
-2 -2 -3 -3 -2 -2 -1 0 -1 -1
-2 -1 -1 -1 0 -1 -2 -2 -1 -2
-3 -3 -4 -3 -3 -3 -2 -3 -4 -4
-4 -3 -4 -4 -3 -2 -1 -1 -2 -2
-1 -1 0 1 2 2 1 1 1 1
first 1000 terms:
equal to zero : 92
crosses zero : 59</pre>
=={{header|BASIC}}==
Line 408 ⟶ 879:
a little over 1 hour on the 8086 (using GWBASIC).
<
20 M(1)=1
30 FOR N=2 TO 1000
Line 426 ⟶ 897:
170 PRINT "M(N) is zero";Z;"times."
180 PRINT "M(N) crosses zero";C;"times."
190 END</
{{out}}
Line 444 ⟶ 915:
M(N) crosses zero 59 times.</pre>
==={{header|
<syntaxhighlight lang="freebasic">arraybase 1
dim M(1000)
M[1] = 1
for n = 2 to 1000
M[n] = 1
for k = 2 to n
M[n] = M[n] - M[int(n/k)]
next k
next n
print "First 99 Mertens numbers:"
print " ";
for n = 1 to 99
print rjust(string(M[n]),3);
if n mod 10 = 9 then print
next n
numCruza = 0
numEsCero = 0
for n = 1 to 1000
if M[n] = 0 then
numEsCero += 1
if M[n-1] <> 0 then numCruza += 1
end if
next n
print
print "M(n) is zero "; numEsCero; " times."
print "M(n) crosses zero "; numCruza; " times."</syntaxhighlight>
{{out}}
<pre>Same as BASIC entry.</pre>
==={{header|Run BASIC}}===
{{works with|Just BASIC}}
{{works with|Liberty BASIC}}
<syntaxhighlight lang="freebasic">dim M(1000)
M(1) = 1
for n = 2 to 1000
M(n) = 1
for k = 2 to n
M(n) = M(n)-M(int(n/k))
next k
next n
print "First 99 Mertens numbers:"
print " ";
for n = 1 to 99
print using("###", M(n));
if n mod 10 = 9 then print
next n
numCruza = 0
numEsCero = 0
for n = 1 to 1000
if M(n) = 0 then
numEsCero = numEsCero +1
if M(n-1) <> 0 then numCruza = numCruza +1
end if
next n
print
print "M(n) is zero "; numEsCero; " times."
print "M(n) crosses zero "; numCruza; " times."</syntaxhighlight>
{{out}}
<pre>Same as BASIC entry.</pre>
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">DIM m(1000)
LET m(1) = 1
FOR n = 2 TO 1000
LET m(n) = 1
FOR k = 2 TO n
LET m(n) = m(n)-m(INT(n/k))
NEXT k
NEXT n
PRINT "First 99 Mertens numbers:"
PRINT " ";
FOR n = 1 TO 99
PRINT " ";
PRINT USING "##": m(n);
!IF REMAINDER(ROUND(n),10) = 9 THEN PRINT
IF MOD(n,10) = 9 THEN PRINT
NEXT n
LET numcruza = 0
LET numeszero = 0
FOR n = 1 TO 1000
IF m(n) = 0 THEN
LET numeszero = numeszero+1
IF m(n-1) <> 0 THEN LET numcruza = numcruza+1
END IF
NEXT n
PRINT
PRINT "M(n) is zero"; numeszero; "times."
PRINT "M(n) crosses zero"; numcruza; "times."
END</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="xbasic">PROGRAM "Mertens"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
DIM M[1000]
M[1] = 1
FOR n = 2 TO 1000
M[n] = 1
FOR k = 2 TO n
M[n] = M[n] - M[INT(n/k)]
NEXT k
NEXT n
PRINT "First 99 Mertens numbers:"
PRINT " ";
FOR n = 1 TO 99
PRINT FORMAT$("###", M[n]);
IF n MOD 10 = 9 THEN PRINT
NEXT n
numCruza = 0
numEsCero = 0
FOR n = 1 TO 1000
IF M[n] = 0 THEN
INC numEsCero
IF M[n-1] <> 0 THEN INC numCruza
END IF
NEXT n
PRINT
PRINT "M(n) is zero"; numEsCero; " times."
PRINT "M(n) crosses zero"; numCruza; " times."
END FUNCTION
END PROGRAM</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Yabasic}}===
<syntaxhighlight lang="freebasic">dim M(1000)
M(1) = 1
for n = 2 to 1000
M(n) = 1
for k = 2 to n
M(n) = M(n) - M(int(n/k))
next k
next n
print "First 99 Mertens numbers:"
print " ";
for n = 1 to 99
print M(n) using("###");
if mod(n, 10) = 9 print
next n
numCruza = 0
numEsCero = 0
for n = 1 to 1000
if M(n) = 0 then
numEsCero = numEsCero + 1
if M(n-1) <> 0 numCruza = numCruza + 1
end if
next n
print
print "M(n) is zero ", numEsCero, " times."
print "M(n) crosses zero ", numCruza, " times."</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>=={{header|Bash}}==
<syntaxhighlight lang="bash">#!/bin/bash
MAX=1000
Line 478 ⟶ 1,108:
echo "M(N) is zero $zero times."
echo "M(N) crosses zero $cross times."</
{{out}}
Line 493 ⟶ 1,123:
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
manifest $( limit = 1000 $)
let mertens(v, max) be
$( v!1 := 1
for n = 2 to max do
$( v!n := 1
for k = 2 to n do
v!n := v!n - v!(n/k)
$)
$)
let start() be
$( let m = vec limit
let eqz, crossz = 0, 0
writes("The first 99 Mertens numbers are:*N")
mertens(m, limit)
for y=0 to 90 by 10 do
$( for x=0 to 9 do
test x+y=0
then writes(" ")
else writed(m!(x+y),3)
wrch('*N')
$)
for x=2 to limit do
if m!x=0 then
$( eqz := eqz + 1
unless m!(x-1)=0 do crossz := crossz + 1
$)
writef("M(N) is zero %N times.*N", eqz)
writef("M(N) crosses zero %N times.*N", crossz)
$)</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|C}}==
<
#include <stdlib.h>
Line 549 ⟶ 1,231:
printf("M(n) crosses zero %d times for 1 <= n <= %d.\n", cross, max);
return 0;
}</
{{out}}
Line 569 ⟶ 1,251:
=={{header|C++}}==
<
#include <iostream>
#include <vector>
Line 611 ⟶ 1,293:
std::cout << "M(n) crosses zero " << cross << " times for 1 <= n <= 1000.\n";
return 0;
}</
{{out}}
Line 629 ⟶ 1,311:
M(n) crosses zero 59 times for 1 <= n <= 1000.
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Generate Mertens numbers up to a given limit
mertens = proc (limit: int) returns (array[int])
M: array[int] := array[int]$fill(1,limit,0)
M[1] := 1
for n: int in int$from_to(2,limit) do
M[n] := 1
for k: int in int$from_to(2,n) do
M[n] := M[n] - M[n/k]
end
end
return (M)
end mertens
start_up = proc ()
max = 1000
po: stream := stream$primary_output()
M: array[int] := mertens(max)
stream$putl(po, "The first 99 Mertens numbers are:")
for y: int in int$from_to_by(0,90,10) do
for x: int in int$from_to(0,9) do
stream$putright(po, int$unparse(M[x+y]), 3)
except when bounds:
stream$putright(po, "", 3)
end
end
stream$putl(po, "")
end
eqz: int := 0
crossz: int := 0
for i: int in int$from_to(2,max) do
if M[i]=0 then
eqz := eqz + 1
if M[i-1]~=0 then crossz := crossz + 1 end
end
end
stream$putl(po, "M(N) is zero " || int$unparse(eqz) || " times.")
stream$putl(po, "M(N) crosses zero " || int$unparse(crossz) || " times.")
end start_up</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|COBOL}}==
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. MERTENS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 VARIABLES.
03 M PIC S99 OCCURS 1000 TIMES.
03 N PIC 9(4).
03 K PIC 9(4).
03 V PIC 9(4).
03 IS-ZERO PIC 99 VALUE 0.
03 CROSS-ZERO PIC 99 VALUE 0.
01 OUTPUT-FORMAT.
03 OUT-ITEM.
05 OUT-NUM PIC -9.
05 FILLER PIC X VALUE SPACE.
03 OUT-LINE PIC X(30) VALUE SPACES.
03 OUT-PTR PIC 99 VALUE 4.
PROCEDURE DIVISION.
BEGIN.
PERFORM GENERATE-MERTENS.
PERFORM WRITE-TABLE.
PERFORM COUNT-ZEROES.
STOP RUN.
GENERATE-MERTENS.
MOVE 1 TO M(1).
PERFORM MERTENS-OUTER-LOOP VARYING N FROM 2 BY 1
UNTIL N IS GREATER THAN 1000.
MERTENS-OUTER-LOOP.
MOVE 1 TO M(N).
PERFORM MERTENS-INNER-LOOP VARYING K FROM 2 BY 1
UNTIL K IS GREATER THAN N.
MERTENS-INNER-LOOP.
DIVIDE N BY K GIVING V.
SUBTRACT M(V) FROM M(N).
WRITE-TABLE.
DISPLAY "The first 99 Mertens numbers are: "
PERFORM WRITE-ITEM VARYING N FROM 1 BY 1
UNTIL N IS GREATER THAN 99.
WRITE-ITEM.
MOVE M(N) TO OUT-NUM.
STRING OUT-ITEM DELIMITED BY SIZE INTO OUT-LINE
WITH POINTER OUT-PTR.
IF OUT-PTR IS EQUAL TO 31,
DISPLAY OUT-LINE,
MOVE 1 TO OUT-PTR.
COUNT-ZEROES.
PERFORM TEST-N-ZERO VARYING N FROM 2 BY 1
UNTIL N IS GREATER THAN 1000.
DISPLAY "M(N) is zero " IS-ZERO " times.".
DISPLAY "M(N) crosses zero " CROSS-ZERO " times.".
TEST-N-ZERO.
IF M(N) IS EQUAL TO ZERO,
ADD 1 TO IS-ZERO,
SUBTRACT 1 FROM N GIVING K,
IF M(K) IS NOT EQUAL TO ZERO,
ADD 1 TO CROSS-ZERO.</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Cowgol}}==
<
const MAX := 1000;
Line 693 ⟶ 1,515:
print("M(n) is zero "); print_i8(zero); print(" times\n");
print("M(n) crosses zero "); print_i8(cross); print(" times\n");</
{{out}}
Line 710 ⟶ 1,532:
M(n) is zero 92 times
M(n) crosses zero 59 times</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program Mertens_function;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
type
TMertens = record
merts: TArray<Integer>;
zeros, crosses: Integer;
class function Mertens(_to: Integer): TMertens; static;
end;
{ TMertens }
class function TMertens.Mertens(_to: Integer): TMertens;
var
sum, zeros, crosses: Integer;
begin
if _to < 1 then
_to := 1;
sum := 0;
zeros := 0;
crosses := 0;
SetLength(Result.merts, _to + 1);
var primes := [2];
for var i := 1 to _to do
begin
var j := i;
var cp := 0;
var spf := false;
for var p in primes do
begin
if p > j then
Break;
if j mod p = 0 then
begin
j := j div p;
inc(cp);
end;
if j mod p = 0 then
begin
spf := true;
Break;
end;
end;
if (cp = 0) and (i > 2) then
begin
cp := 1;
SetLength(primes, Length(primes) + 1);
primes[High(primes)] := i;
end;
if not spf then
begin
if cp mod 2 = 0 then
inc(sum)
else
dec(sum);
end;
Result.merts[i] := sum;
if sum = 0 then
begin
inc(zeros);
if (i > 1) and (Result.merts[i - 1] <> 0) then
inc(crosses);
end;
end;
Result.zeros := zeros;
Result.crosses := crosses;
end;
begin
var m := TMertens.mertens(1000);
writeln('Mertens sequence - First 199 terms:');
for var i := 0 to 199 do
begin
if i = 0 then
begin
write(' ');
Continue;
end;
if i mod 20 = 0 then
writeln;
write(format(' %3d', [m.merts[i]]));
end;
writeln(#10#10'Equals zero ', m.zeros, ' times between 1 and 1000');
writeln(#10'Crosses zero ', m.crosses, ' times between 1 and 1000');
{$IFNDEF UNIX} readln; {$ENDIF}
end.</syntaxhighlight>
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc nonrec mertens([*] short m) void:
word n,k;
m[1] := 1;
for n from 2 upto dim(m,1)-1 do
m[n] := 1;
for k from 2 upto n do
m[n] := m[n] - m[n/k]
od
od
corp
proc nonrec main() void:
[1001] short m;
word x, y, eqz, crossz;
mertens(m);
writeln("The first 99 Mertens numbers are:");
for y from 0 by 10 upto 90 do
for x from 0 upto 9 do
if x+y=0
then write(" ")
else write(m[x+y]:3)
fi
od;
writeln()
od;
eqz := 0;
crossz := 0;
for x from 2 upto dim(m,1)-1 do
if m[x]=0 then
eqz := eqz + 1;
if m[x-1]~=0 then crossz := crossz + 1 fi
fi
od;
writeln("M(N) is zero ",eqz," times.");
writeln("M(N) crosses zero ",crossz," times.")
corp</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Dyalect}}==
{{trans|Swift}}
<syntaxhighlight lang="dyalect">func mertensNumbers(max) {
let mertens = Array.Empty(max + 1, 1)
for n in 2..max {
for k in 2..n {
mertens[n] -= mertens[n / k]
}
}
mertens
}
let max = 1000
let mertens = mertensNumbers(max)
let count = 200
let columns = 20
print("First \(count - 1) Mertens numbers:")
for i in 0..<count {
if i % columns > 0 {
print(" ", terminator: "")
}
print(i == 0 ? " " : mertens[i].ToString().PadLeft(2, ' ') + " ", terminator: "")
if (i + 1) % columns == 0 {
print()
}
}
var (zero, cross, previous) = (0, 0, 0)
for i in 1..max {
let m = mertens[i]
if m == 0 {
zero += 1
if previous != 0 {
cross += 1
}
}
previous = m
}
print("M(n) is zero \(zero) times for 1 <= n <= \(max).")
print("M(n) crosses zero \(cross) times for 1 <= n <= \(max).")</syntaxhighlight>
{{out}}
<pre>First 199 Mertens numbers:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1
1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3
-3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4
-4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0
0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3
-3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8
M(n) is zero 92 times for 1 <= n <= 1000.
M(n) crosses zero 59 times for 1 <= n <= 1000.</pre>
=={{header|EasyLang}}==
{{trans|FutureBasic}}
<syntaxhighlight>
len mertens[] 1000
mertens[1] = 1
for n = 2 to 1000
mertens[n] = 1
for k = 2 to n
mertens[n] -= mertens[n div k]
.
.
print "First 99 Mertens numbers:"
write " "
numfmt 0 2
for n = 1 to 99
write mertens[n] & " "
if n mod 10 = 9
print ""
.
.
for n = 1 to 1000
if mertens[n] = 0
zeros += 1
if mertens[n - 1] <> 0
crosses += 1
.
.
.
print ""
print "In the first 1000 terms of the Mertens sequence there are:"
print zeros & " zeros"
print crosses & " zero crosses"
</syntaxhighlight>
{{out}}
<pre>
First 99 Mertens numbers:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
In the first 1000 terms of the Mertens sequence there are:
92 zeros
59 zero crosses
</pre>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Möbius_function#F.23 Möbius_function (F#)]
<
// Mertens function. Nigel Galloway: January 31st., 2021
let mertens=mobius|>Seq.scan((+)) 0|>Seq.tail
Line 721 ⟶ 1,811:
printfn "%d Zeroes\n####" (Seq.length (snd n.[0]))
printfn "Crosses zero %d times" (mertens|>Seq.take 1000|>Seq.pairwise|>Seq.sumBy(fun(n,g)->if n<>0 && g=0 then 1 else 0)))
</syntaxhighlight>
{{out}}
<pre>
Line 773 ⟶ 1,863:
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<
math.ranges math.statistics prettyprint sequences ;
Line 790 ⟶ 1,880:
2 <clumps> [ first2 [ 0 = not ] [ zero? ] bi* and ] count bl
pprint bl "zero crossings." print
] bi</
{{out}}
<pre>
Line 811 ⟶ 1,901:
=={{header|Forth}}==
<
variable mertens AMOUNT cells allot
Line 861 ⟶ 1,951:
." M(N) is zero " . ." times." cr
." M(N) crosses zero " . ." times." cr
bye </
{{out}}
Line 880 ⟶ 1,970:
=={{header|Fortran}}==
<
implicit none
integer M(1000), n, k, zero, cross
Line 919 ⟶ 2,009:
50 format("M(N) crosses zero ",I2," times.")
write (*,50) cross
end program</
{{out}}
Line 938 ⟶ 2,028:
=={{header|FreeBASIC}}==
<
return wspace(i-len(str(j)))+str(j)
end function
Line 971 ⟶ 2,061:
outstr = ""
end if
next n</
{{out}}
<pre>
Line 987 ⟶ 2,077:
-4 -3 -4 -4 -3 -2 -1 -1 -2 -2
-1 -1 0 1 2 2 1 1 1 1
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
void local fn MertensFunction
long mertens(1000), n, k, crossesTotal = 0, zerosTotal = 0
mertens(1) = 1
for n = 2 to 1000
mertens(n) = 1
for k = 2 to n
mertens(n) = mertens(n) - mertens(n/k)
next
next
printf @"First 99 Mertens numbers:\n \b"
for n = 1 to 99
printf @"%3ld \b", mertens(n)
if ( n mod 10 == 9 ) then print
next
for n = 1 to 1000
if ( mertens(n) == 0 )
zerosTotal++
if mertens(n-1) != 0 then crossesTotal++
end if
next
print
printf @"mertens(n) array is zero %ld times.", zerosTotal
printf @"mertens(n) array crosses zero %ld times.", crossesTotal
end fn
fn MertensFunction
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
First 99 Mertens numbers:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
mertens(n) array is zero 92 times.
mertens(n) array crosses zero 59 times.
</pre>
=={{header|Go}}==
<
import "fmt"
Line 1,055 ⟶ 2,200:
fmt.Println("\n\nEquals zero", zeros, "times between 1 and 1000")
fmt.Println("\nCrosses zero", crosses, "times between 1 and 1000")
}</
{{out}}
Line 1,075 ⟶ 2,220:
Crosses zero 59 times between 1 and 1000
</pre>
=={{header|Haskell}}==
<
import qualified Data.MemoCombinators as Memo
import Math.NumberTheory.Primes (unPrime, factorise)
Line 1,109 ⟶ 2,255:
mapM_ (\row -> mapM_ (printf "%3d" . mertens) row >> printf "\n") $ chunksOf 10 [10..99]
printf "\nM(n) is zero %d times for 1 <= n <= 1000.\n" $ countZeros [1..1000]
printf "M(n) crosses zero %d times for 1 <= n <= 1000.\n" $ crossesZero [1..1000]</
{{out}}
<pre>The first 99 terms for M(1..99):
Line 1,128 ⟶ 2,274:
=={{header|J}}==
<
M =: +/@([: mu 1:+i.)
Line 1,139 ⟶ 2,285:
echo 'M(N) is zero ',(":zero),' times.'
echo 'M(N) crosses zero ',(":cross),' times.'
exit''</
{{out}}
Line 1,158 ⟶ 2,304:
=={{header|Java}}==
<
public class MertensFunction {
Line 1,268 ⟶ 2,414:
}
</syntaxhighlight>
{{out}}
Line 1,331 ⟶ 2,477:
M(x) has 41,908 zeroes in the interval.
M(x) has 25,525 crossings in the interval.
</pre>
=={{header|jq}}==
'''Adapted from [[#C|C]]'''
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
This entry will use the strategy exemplified in the entry for C and some
others, that is, it will begin by defining a function that
constructs an array of a specified number of Merten numbers, and use
that function to solve the other tasks, which, however, will be solved
independently for the sake of modularity and to illustrate efficient
approaches to the problems considered separately. It would be
trivial but uninteresting to merge the answers for efficiency.
'''Preliminaries'''
<syntaxhighlight lang="jq">
def sum(s): reduce s as $x (null; . + $x);
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# input: an array
# output: number of crossings at $value
def count_crossings($value):
. as $a
| reduce range(0; length) as $i ({};
if $a[$i] == $value
then if $i == 0 or .prev != $value then .count += 1 else . end
else .
end
| .prev = $a[$i] )
| .count;</syntaxhighlight>
'''Mertens Numbers'''
<syntaxhighlight lang="jq">
# Input: $max >= 1
# Output: an array of size $max with $max mertenNumbers beginning with 1
def mertensNumbers:
. as $max
| reduce range(2; $max + 1) as $n ( [1];
.[$n-1]=1
| reduce range(2; $n+1) as $k (.;
.[$n-1] -= .[($n / $k) | floor - 1] ));</syntaxhighlight>
'''The Tasks'''
<syntaxhighlight lang="jq"># Task 0:
def mertens_number:
mertensNumbers[.-1];
def task1:
"The first \(.) Mertens numbers are:",
(mertensNumbers | nwise(10) | map(lpad(2)) | join(" ") );
def task2:
. as $n
| sum(mertensNumbers[] | select(.==0) | 1)
| "M(n) is zero \(.) times for 1 <= n <= \($n)\n";
def task3:
. as $n
| mertensNumbers
| count_crossings(0)
| "M(n) crosses zero \(.) times for 1 <= n <= \($n).\n" ;
(99|task1),
"",
(1000 | (task2, task3))
</syntaxhighlight>
{{out}}
<pre>
The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2 -1
-2 -2 -3 -2 -1 -1 -2 -2 -3 -3
-2 -1 -2 -2 -2 -1 -1 -1 -2 -3
-4 -4 -3 -2 -1 -1 -2 -1 0 0
-1 -2 -3 -3 -3 -2 -3 -3 -3 -3
-2 -2 -3 -3 -2 -2 -1 0 -1 -1
-2 -1 -1 -1 0 -1 -2 -2 -1 -2
-3 -3 -4 -3 -3 -3 -2 -3 -4 -4
-4 -3 -4 -4 -3 -2 -1 -1 -2 -2
-1 -1 0 1 2 2 1 1 1
M(n) is zero 92 times for 1 <= n <= 1000
M(n) crosses zero 59 times for 1 <= n <= 1000.
</pre>
=={{header|Julia}}==
The OEIS A002321 reference suggests the Mertens function has a negative bias, which it does below 1 million, but this bias seems to switch to a positive bias by 1 billion. There may simply be large swings in the bias overall, which get larger and longer as the sequence continues.
<
function moebius(n::Integer)
Line 1,392 ⟶ 2,626:
foreach(maximinM, (1000, 1_000_000, 1_000_000_000))
</
<pre>
First 99 terms of the Mertens function for positive integers:
Line 1,435 ⟶ 2,669:
=={{header|MAD}}==
<
DIMENSION M(1000)
Line 1,467 ⟶ 2,701:
PRINT FORMAT FC, CROSS
END OF PROGRAM </
{{out}}
Line 1,484 ⟶ 2,718:
M(N) IS ZERO 92 TIMES
M(N) CROSSES ZERO 59 TIMES</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[Mertens]
Mertens[n_] := Total[MoebiusMu[Range[n]]]
Grid[Partition[Mertens /@ Range[99], UpTo[10]]]
Count[Mertens /@ Range[1000], 0]
SequenceCount[Mertens /@ Range[1000], {Except[0], 0}]</syntaxhighlight>
{{out}}
<pre>1 0 -1 -1 -2 -1 -2 -2 -2 -1
-2 -2 -3 -2 -1 -1 -2 -2 -3 -3
-2 -1 -2 -2 -2 -1 -1 -1 -2 -3
-4 -4 -3 -2 -1 -1 -2 -1 0 0
-1 -2 -3 -3 -3 -2 -3 -3 -3 -3
-2 -2 -3 -3 -2 -2 -1 0 -1 -1
-2 -1 -1 -1 0 -1 -2 -2 -1 -2
-3 -3 -4 -3 -3 -3 -2 -3 -4 -4
-4 -3 -4 -4 -3 -2 -1 -1 -2 -2
-1 -1 0 1 2 2 1 1 1
92
59</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE Mertens;
FROM InOut IMPORT WriteString, WriteInt, WriteCard, WriteLn;
CONST Max = 1000;
VAR n, k, x, y, zero, cross: CARDINAL;
M: ARRAY [1..Max] OF INTEGER;
BEGIN
M[1] := 1;
FOR n := 2 TO Max DO
M[n] := 1;
FOR k := 2 TO n DO
M[n] := M[n] - M[n DIV k];
END;
END;
WriteString("The first 99 Mertens numbers are:");
WriteLn();
FOR y := 0 TO 90 BY 10 DO
FOR x := 0 TO 9 DO
IF x+y=0 THEN WriteString(" ");
ELSE WriteInt(M[x+y], 3);
END;
END;
WriteLn();
END;
zero := 0;
cross := 0;
FOR n := 2 TO Max DO
IF M[n] = 0 THEN
zero := zero + 1;
IF M[n-1] # 0 THEN
cross := cross + 1;
END;
END;
END;
WriteString("M(n) is zero ");
WriteCard(zero,0);
WriteString(" times.");
WriteLn();
WriteString("M(n) crosses zero ");
WriteCard(cross,0);
WriteString(" times.");
WriteLn();
END Mertens.</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(n) is zero 92 times.
M(n) crosses zero 59 times.</pre>
=={{header|Nim}}==
{{trans|C}}
<
func mertensNumbers(max: int): seq[int] =
Line 1,520 ⟶ 2,837:
echo ""
echo &"M(n) is zero {zero} times for 1 ⩽ n ⩽ {Max}."
echo &"M(n) crosses zero {cross} times for 1 ⩽ n ⩽ {Max}."</
{{out}}
Line 1,541 ⟶ 2,858:
Nearly the same as [[Square-free_integers#Pascal]]
Instead here marking all multiples, starting at factor 2, of a prime by incrementing the factor count.<BR> runtime ~log(n)*n
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 1,765 ⟶ 3,082:
setlength(primes,0);
setlength(sieve,0);
end.</
{{out}}
<pre>[1 to limit]
Line 1,827 ⟶ 3,144:
=={{header|Perl}}==
<
use strict;
use warnings;
Line 1,859 ⟶ 3,176:
(' 'x4 . sprintf "@{['%4d' x $show]}", @mertens[0..$show-1]) =~ s/((.){80})/$1\n/gr .
sprintf("\nEquals zero %3d times between 1 and $upto", scalar grep { ! $_ } @mertens) .
sprintf "\nCrosses zero%3d times between 1 and $upto", scalar grep { ! $mertens[$_-1] and $mertens[$_] } 1 .. @mertens;</
{{out}}
<pre>Mertens sequence - First 199 terms:
Line 1,877 ⟶ 3,194:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (skip arg added to join_by)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mcache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Mertens</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;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mcache</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">mm</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">mcache</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">/</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">mcache</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">mm</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">mcache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">99</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">perline</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10</span>
<span style="color: #000080;font-style:italic;">--constant first = 199, perline = 20 -- matches C/Go/etc
--constant first = 143, perline = 12 -- matches wp</span>
<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><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">first</span><span style="color: #0000FF;">),</span><span style="color: #000000;">Mertens</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First %d Mertens numbers:\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">first</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;">perline</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">skip</span><span style="color: #0000FF;">:=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">zeroes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">crosses</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1000</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Mertens</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">zeroes</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">crosses</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">prev</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nMertens[1..1000] equals zero %d times and crosses zero %d times\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">zeroes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">crosses</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
First 99 Mertens numbers:
-
-
-3 -
-3 -
-
-
-
Mertens[1..1000] equals zero 92 times and crosses zero 59 times
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pli">mertens: procedure options(main);
%replace MAX by 1000;
declare M(1:MAX) fixed binary(5);
declare (n, k) fixed binary(10);
declare (isZero, crossZero) fixed binary(8);
M(1) = 1;
do n = 2 to MAX;
M(n) = 1;
do k = 2 to n;
M(n) = M(n) - M(divide(n,k,10));
end;
end;
put skip list('The first 99 Mertens numbers are:');
put skip list(' ');
do n = 1 to 99;
put edit(M(n)) (F(3));
if mod(n,10) = 9 then put skip;
end;
isZero = 0;
crossZero = 0;
do n = 2 to MAX;
if M(n) = 0 then do;
isZero = isZero + 1;
if M(n-1) ^= 0 then
crossZero = crossZero + 1;
end;
end;
put skip list('Zeroes: ',isZero);
put skip list('Crossings:',crossZero);
end mertens;</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
Zeroes: 92
Crossings: 59</pre>
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<
mertens_number(1, 1):- !.
Line 1,977 ⟶ 3,355:
count_zeros(1, 1000, Z, C),
writef('M(n) is zero %t times for 1 <= n <= 1000.\n', [Z]),
writef('M(n) crosses zero %t times for 1 <= n <= 1000.\n', [C]).</
{{out}}
Line 1,995 ⟶ 3,373:
M(n) crosses zero 59 times for 1 <= n <= 1000.
</pre>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">Dim M.i(1000)
M(1)=1
For n=2 To 1000
psum=0
For k=2 To n : psum+M(Int(n/k)) : Next : M(n)=1-psum
If M(n)=0 : z+1 : If M(n-1)<>0 : c+1 : EndIf : EndIf
Next
OpenConsole("")
PrintN("First 99 Mertens numbers:") : Print(Space(4))
For n=1 To 99 : Print(RSet(Str(M(n)),4)) : If n%10=9 : PrintN("") : EndIf : Next
PrintN("M(N) is zero "+Str(z)+" times.") : PrintN("M(N) crosses zero "+Str(c)+" times.")
Input()</syntaxhighlight>
{{out}}
<pre>First 99 Mertens numbers:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Python}}==
<
"""Generate Mertens numbers"""
m = [None, 1]
Line 2,022 ⟶ 3,430:
crosses = sum(a!=0 and b==0 for a,b in zip(ms, ms[1:]))
print("M(N) equals zero {} times.".format(zeroes))
print("M(N) crosses zero {} times.".format(crosses))</
{{out}}
Line 2,039 ⟶ 3,447:
M(N) equals zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Quackery}}==
<code>mobius</code> is defined at [[Möbius function#Quackery]].
<syntaxhighlight lang="Quackery"> [ ' [ 0 ]
swap 1+ times
[ dup -1 peek
i^ 1+ mobius
+ join ]
behead drop ] is mertens ( n --> [ )
[ say " "
99 times
[ dup i^ peek
dup dup
-1 > if sp
abs 10 < if sp
echo
i^ 1+ 10 mod
9 = if cr ]
drop ] is grid ( [ --> )
[ 0 swap
witheach
[ 0 = + ] ] is zeroes ( [ --> n )
[ 0 0
rot witheach
[ dup 0 =
rot 0 !=
and
rot + swap ]
drop ] is crossings ( [ --> n )
1000 mertens
say "First 99 terms:"
cr
dup grid
cr
dup zeroes echo say " zeroes and "
crossings echo say " crossings"</syntaxhighlight>
{{out}}
<pre>First 99 terms:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
92 zeroes and 59 crossings</pre>
=={{header|Raku}}==
Line 2,045 ⟶ 3,511:
Mertens number is not defined for n == 0. Raku arrays are indexed from 0 so store a blank value at position zero to keep x and M(x) aligned.
<syntaxhighlight lang="raku"
sub μ (Int \n) {
Line 2,065 ⟶ 3,531:
printf "%4d: M(%d)\n", -$threshold, @mertens.first: * == -$threshold, :k;
printf "%4d: M(%d)\n", $threshold, @mertens.first: * == $threshold, :k;
}</
{{out}}
<pre>Mertens sequence - First 199 terms:
Line 2,117 ⟶ 3,583:
The above "feature" was added to make the grid to be aligned with other solutions.
<
parse arg LO HI grp eqZ xZ . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 0 /*Not specified? Then use the default.*/
Line 2,126 ⟶ 3,592:
call genP /*generate primes up to max √ HIHI */
call Franz LO, HI
if eqZ>0 then call Franz 1, -eqZ
if xZ>0 then call Franz -1, xZ
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Franz: parse arg a 1 oa,b 1 ob; @Mertens= ' The Mertens sequence from '
a= abs(a); b= abs(b); grid= oa>=0 & ob>=0 /*semaphore used to show a grid title. */
if grid then say center(@Mertens LO " ──► " HI" ", max(50, grp*3), '═') /*show title*/
Line 2,136 ⟶ 3,602:
zeros= 0 /*# of 0's found for Mertens function.*/
Xzero= 0 /*number of times that zero was crossed*/
$=; prev= /*$ holds output grid of GRP numbers. */
do j=a to b; _= Mertens(j) /*process some numbers from LO ──► HI.*/
if _==0 then zeros= zeros + 1 /*Is Zero? Then bump the zeros counter*/
Line 2,143 ⟶ 3,608:
prev= _
if grid then $= $ right(_, 2) /*build grid if A & B are non─negative.*/
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.*/
Line 2,152 ⟶ 3,617:
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Mertens: procedure expose @. !!. M.; parse arg n;
if
do k=1 for n; m= m + mobius(k) /*sum the MU's up to N. */
end /*k*/ /* [↑] mobius function uses memoization*/
M.n= m; return m /*return the sum of all the MU's. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
mobius: procedure expose @. !!.; parse arg x 1 ox /*
if !!.x\==. then return !!.x
if x<1
if
x= x % p /* Divide by prime. */
if x//p==0 then return 0 /*X÷by P? Then return zero*/
end
end /*k*/ /*
!!.ox= -1 **
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP:
do
if _==5 then iterate; if j//3==0 then iterate; if j//7==0 then iterate /*÷ 5 3 7*/
do k=
if j
end /*k*/ /* [↓] a prime (J) has been found. */
end /*j*/; return /*calculate the squares of some primes.*/</
{{out|output|text= when using the default inputs:}}
Line 2,206 ⟶ 3,666:
=={{header|Ruby}}==
<
def μ(n)
Line 2,224 ⟶ 3,684:
puts "\nThe Mertens function is zero #{ar.count(0)} times in the range (1..1000);"
puts "it crosses zero #{ar.each_cons(2).count{|m1, m2| m1 != 0 && m2 == 0}} times."
</syntaxhighlight>
{{out}}
<pre> 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3
Line 2,240 ⟶ 3,700:
it crosses zero 59 times.
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program mertens;
m := [1] * 1000;
loop for n in [1..#m] do
m(n) -:= 0 +/[m(n div k) : k in [2..n]];
end loop;
print("The first 99 Mertens numbers:");
putchar(" ");
loop for n in [1..99] do
putchar(lpad(str m(n), 3));
if n mod 10=9 then print; end if;
end loop;
zero := #[n : n in [1..#m] | m(n) = 0];
cross := #[n : n in [1..#m] | m(n) = 0 and m(n-1) /= 0];
print("M(N) is zero " + str zero + " times.");
print("M(N) crosses zero " + str cross + " times.");
end program;</syntaxhighlight>
{{out}}
<pre>The first 99 Mertens numbers:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.</pre>
=={{header|Sidef}}==
Built-in:
<
say mertens(1234567890) #=> 9163</
Algorithm for computing M(n) in sublinear time:
<
var lookup_size = (2 * n.iroot(3)**2)
Line 2,282 ⟶ 3,777:
cache{n} = M
}(n)
}</
Task:
<
say "Mertens function in the range 1..#{n}:"
(1..n).map { mertens(_) }.slices(20).each {|line|
Line 2,296 ⟶ 3,791:
say (1..n->count_by { mertens(_)==0 }, " zeros")
say (1..n->count_by { mertens(_)==0 && mertens(_-1)!=0 }, " zero crossings")
}</
{{out}}
<pre>
Line 2,318 ⟶ 3,813:
=={{header|Swift}}==
{{trans|C}}
<
func mertensNumbers(max: Int) -> [Int] {
Line 2,358 ⟶ 3,853:
}
print("M(n) is zero \(zero) times for 1 <= n <= \(max).")
print("M(n) crosses zero \(cross) times for 1 <= n <= \(max).")</
{{out}}
Line 2,375 ⟶ 3,870:
M(n) is zero 92 times for 1 <= n <= 1000.
M(n) crosses zero 59 times for 1 <= n <= 1000.
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">fn mertens(t int) ([]int, int, int) {
mut to:=t
if to < 1 {
to = 1
}
mut merts := []int{len:to+1}
mut primes := [2]
mut sum := 0
mut zeros := 0
mut crosses := 0
for i := 1; i <= to; i++ {
mut j := i
mut cp := 0 // counts prime factors
mut spf := false // true if there is a square prime factor
for p in 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 << i
}
if !spf {
if cp%2 == 0 {
sum++
} else {
sum--
}
}
merts[i] = sum
if sum == 0 {
zeros++
if i > 1 && merts[i-1] != 0 {
crosses++
}
}
}
return merts, zeros, crosses
}
fn main() {
merts, zeros, crosses := mertens(1000)
println("Mertens sequence - First 199 terms:")
for i := 0; i < 200; i++ {
if i == 0 {
print(" ")
continue
}
if i%20 == 0 {
println('')
}
print(" ${merts[i]:2}")
}
println("\n\nEquals zero $zeros times between 1 and 1000")
println("\nCrosses zero $crosses times between 1 and 1000")
}</syntaxhighlight>
{{out}}
<pre>
Mertens sequence - First 199 terms:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1
1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3
-3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4
-4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0
0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3
-3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8
Equals zero 92 times between 1 and 1000
Crosses zero 59 times between 1 and 1000
</pre>
Line 2,380 ⟶ 3,962:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<
import "./math" for Int
var isSquareFree = Fn.new { |n|
Line 2,432 ⟶ 4,014:
prev = next
}
System.print("\nThe Mertens function crosses zero %(count) times in the range [1, 1000].")</
{{out}}
Line 2,451 ⟶ 4,033:
The Mertens function crosses zero 59 times in the range [1, 1000].
</pre>
=={{header|XPL0}}==
{{trans|ALGOL W}}
<syntaxhighlight lang "XPL0">integer M ( 1+1000 );
integer K, Zero, Cross, N;
begin \compute values of the Mertens function
\Generate Mertens numbers
M( 1 ) := 1;
for N := 2 to 1000 do begin
M( N ) := 1;
for K := 2 to N do M( N ) := M( N ) - M( N / K )
end;
\Print table
Text(0, "The first 99 Mertens numbers are:^m^j");
Text(0, " " );
K := 9;
for N := 1 to 99 do begin
Format(3, 0);
RlOut(0, float(M(N)));
K := K - 1;
if K = 0 then begin
K := 10;
CrLf(0);
end
end;
\Calculate zeroes and crossings
Zero := 0;
Cross := 0;
for N :=2 to 1000 do begin
if M( N ) = 0 then begin
Zero := Zero + 1;
if M( N - 1 ) # 0 then Cross := Cross + 1
end
end;
Text(0, "M(N) is zero "); IntOut(0, Zero); Text(0, " times.^m^j" );
Text(0, "M(N) crosses zero "); IntOut(0, Cross); Text(0, " times.^m^j" );
end</syntaxhighlight>
{{out}}
<pre>
The first 99 Mertens numbers are:
1 0 -1 -1 -2 -1 -2 -2 -2
-1 -2 -2 -3 -2 -1 -1 -2 -2 -3
-3 -2 -1 -2 -2 -2 -1 -1 -1 -2
-3 -4 -4 -3 -2 -1 -1 -2 -1 0
0 -1 -2 -3 -3 -3 -2 -3 -3 -3
-3 -2 -2 -3 -3 -2 -2 -1 0 -1
-1 -2 -1 -1 -1 0 -1 -2 -2 -1
-2 -3 -3 -4 -3 -3 -3 -2 -3 -4
-4 -4 -3 -4 -4 -3 -2 -1 -1 -2
-2 -1 -1 0 1 2 2 1 1 1
M(N) is zero 92 times.
M(N) crosses zero 59 times.
</pre>
=={{header|zkl}}==
<
[1..].tweak(fcn(n,pm){
pm.incN(mobius(n));
Line 2,478 ⟶ 4,113:
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}</
<
.pump(Console.println, T(Void.Read,19,False),
fcn{ vm.arglist.pump(String,"%3d".fmt) });
Line 2,487 ⟶ 4,122:
otm.reduce(fcn(s,m){ s + (m==0) },0) : println(_," zeros");
otm.reduce(fcn(p,m,rs){ rs.incN(m==0 and p!=0); m }.fp2( s:=Ref(0) ));
println(s.value," zero crossings");</
{{out}}
<pre>
|
Latest revision as of 21:24, 19 February 2024
You are encouraged to solve this task according to the task description, using any language you may know.
The Mertens function M(x) is the count of square-free integers up to x that have an even number of prime factors, minus the count of those that have an odd number.
It is an extension of the Möbius function. Given the Möbius function μ(n), the Mertens function M(x) is the sum of the Möbius numbers from n == 1 through n == x.
- Task
- Write a routine (function, procedure, whatever) to find the Mertens number for any positive integer x.
- 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.)
- Use that routine to find and display here, on this page, the number of times the Mertens function sequence is equal to zero in the range M(1) through M(1000).
- Use that routine to find and display here, on this page, the number of times the Mertens function sequence crosses zero in the range M(1) through M(1000). (Crossing defined as this term equal to zero but preceding term not.)
- See also
This is not code golf. The stackexchange link is provided as an algorithm reference, not as a guide.
- Related tasks
11l
F mertens(count)
‘Generate Mertens numbers’
V m = [-1, 1]
L(n) 2 .. count
m.append(1)
L(k) 2 .. n
m[n] -= m[n I/ k]
R m
V ms = mertens(1000)
print(‘The first 99 Mertens numbers are:’)
print(‘ ’, end' ‘ ’)
V col = 1
L(n) ms[1.<100]
print(‘#2’.format(n), end' ‘ ’)
col++
I col == 10
print()
col = 0
V zeroes = sum(ms.map(x -> Int(x == 0)))
V crosses = sum(zip(ms, ms[1..]).map((a, b) -> Int(a != 0 & b == 0)))
print(‘M(N) equals zero #. times.’.format(zeroes))
print(‘M(N) crosses zero #. times.’.format(crosses))
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) equals zero 92 times. M(N) crosses zero 59 times.
360 Assembly
* Mertens function - 01/05/2023
MERTENS CSECT
USING MERTENS,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R0,1 1
STH R0,MM m(1)=1
LA R6,2 i=2
DO WHILE=(CH,R6,LE,=AL2(NN)) do i=2 to n
LR R1,R6 i
SLA R1,1 *2 (H)
LA R0,1 1
STH R0,MM-2(R1) m(i)=1
LA R7,2 j=2
DO WHILE=(CR,R7,LE,R6) do j=2 to i
LR R4,R6 i
SRDA R4,32 ~
LR R1,R7 j
DR R4,R1 i/j
LR R8,R5 d=i/j
LR R4,R6 i
SLA R4,1 *2 (H)
LH R2,MM-2(R4) m(i)
LR R1,R8 d
SLA R1,1 *2 (H)
LH R3,MM-2(R1) m(d)
SR R2,R3 m(i)-m(d)
STH R2,MM-2(R4) m(i)=m(i)-m(d)
LA R7,1(R7) j++
ENDDO , enddo j
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT =C'the first 99 Mertens numbers are:',34 print buffer
LA R9,PG @buffer=pg
MVC PG,=CL80' ' clean buffer
MVC 0(3,R9),=CL3' ' output ' '
LA R9,3(R9) @buffer+=3
LA R7,9 j=9
LA R6,1 i=1
DO WHILE=(CH,R6,LE,=AL2(99)) do i=1 to 99
LR R1,R6 i
SLA R1,1 *2 (H)
LH R2,MM-2(R1) m(i)
XDECO R2,XDEC edit m(i)
MVC 0(3,R9),XDEC+9 output m(i)
LA R9,3(R9) @buffer+=3
BCTR R7,0 j=j-1
IF LTR,R7,Z,R7 THEN if j=0 then do;
LA R7,10 j=10
XPRNT PG,L'PG print buffer
LA R9,PG @buffer=pg
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
SR R10,R10 zero=0
SR R11,R11 cross=0
LA R6,1 i=2
DO WHILE=(CH,R6,LE,=AL2(NN)) do i=2 to n
LR R1,R6 i
SLA R1,1 *2 (H)
LH R2,MM-2(R1) m(i)
IF LTR,R2,Z,R2 THEN if m(i)=0 then
LA R10,1(R10) zero=zero+1
LR R1,R6 i
BCTR R1,0 i-1
SLA R1,1 *2 (H)
LH R2,MM-2(R1) m(i-1)
IF LTR,R2,NZ,R2 THEN if m(i-1)^=0 then
LA R11,1(R11) cross=cross+1
ENDIF , endif
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
MVC PG,=CL80' ' clean buffer
MVC PG(13),=C'm(i) is zero '
XDECO R10,XDEC edit zero
MVC PG+13(2),XDEC+10 output zero
MVC PG+15(7),=C' times.'
XPRNT PG,L'PG print buffer
MVC PGI,=H'0'
MVC PG,=CL80' ' clean buffer
MVC PG(18),=C'm(i) crosses zero '
XDECO R11,XDEC edit cross
MVC PG+18(2),XDEC+10 output cross
MVC PG+20(7),=C' times.'
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
NN EQU 1000 n
PG DS CL80 buffer
PGI DC H'0' buffer index
XDEC DS CL12 temp for xdeci xdeco
MM DS (NN)H m
REGEQU
END MERTENS
- Output:
the first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 m(i) is zero 92 times. m(i) crosses zero 59 times.
8080 Assembly
MAX: equ 1000 ; Amount of numbers to generate
org 100h
;;; Generate Mertens numbers
lxi b,1 ; Start at place 1; BC = current Mertens number
lxi h,MM ; First one is 1
dad b
mvi m,1
outer: inx b ; Next Mertens number
lxi h,MM
dad b
mvi m,1 ; Initialize at 1
lxi d,2 ; DE = inner loop counter ('k'), starts at 2
;;; Now we need to find BC/DE, but there is no hardware divide
;;; We also need to be somewhat clever so it doesn't take forever
inner: push d ; Keep both loop counters safe on the stack
push b
xchg ; Divisor in HL
mov d,b ; Dividend in DE
mov e,c
lxi b,100h ; B = counter, C = zero
double: dad h ; Double divisor
inr b ; Increment counter
call cdehl ; Dividend <= divisor?
jnc double ; If so, keep doubling
mov a,b ; Keep counter
mov b,c ; BC = 0
push b ; Push result variable on stakc (initial 0)
mov b,a ; Restore counter
xchg ; HL = dividend, DE = doubled divisor
subtr: mov a,l ; Try HL -= DE
sub e
mov l,a
mov a,h
sbb d
mov h,a
xthl ; Get result accumulator from stack
cmc ; Flip borrow
mov a,l ; Rotate into result
ral
mov l,a
mov a,h
ral
mov h,a
mov a,l ; Retrieve flag
rar
xthl ; Retrieve rest of divisor
jc $+4 ; If borrow,
dad d ; Add dividend back into divisor
xra a ; DE >> 1
ora d
rar
mov d,a
mov a,e
rar
mov e,a
dcr b ; Are we there yet?
jnz subtr ; If not, try another subtraction
pop h ; HL = quotient
;;; Division is done, do lookup and subraction
lxi d,MM ; Look up M[outer/inner]
dad d
mov e,m ; E = M[BC/DE]
pop b ; Restore BC (n)
lxi h,MM
dad b
mov a,m ; A = M[BC]
sub e ; A = M[BC] - M[BC/DE]
mov m,a ; M[BC] = A
pop d ; Restore DE (k)
;;; Update loops
inx d ; k++
call cbcde ; DE <= BC?
jnc inner
lxi h,MAX
call chlbc ; BC <= MAX?
jnc outer
;;; Print table
lxi d,frst99
call puts
lxi h,MM+1 ; Start of Merten numbers
mvi c,9 ; Column counter
table: mov a,m ; Get Merten number
ana a ; Set flags
mvi b,' ' ; Space
jp prtab ; If positive, print space-number-space
mvi b,'-' ; Otherwise, print minus sign
cma ; And negate the number (make positive)
inr a
prtab: adi '0' ; Make ASCII digit
mov d,a ; Keep number
mov a,b ; Print space or minus sign
call putc
mov a,d ; Restore number
call putc ; Print number
mvi a,' ' ; Print space
call putc
dcr c ; Decrement column counter
jnz tnext
lxi d,nl ; End of columns - print newline
call puts
mvi c,10 ; Column counter
tnext: inx h ; Table done?
mov a,l
cpi 100
jnz table ; If not, keep going
;;; Find zeroes and crossings
lxi b,0 ; B=zeroes, C=crossings
lxi d,MAX ; Counter
lxi h,MM+1
count: mov a,m ; Get number
ana a ; Zero?
jnz cnext
inr b ; If so, add zero
dcx h ; Previous number also zero?
mov a,m
inx h
ana a
jz cnext
inr c ; If not, add crossiong
cnext: inx h
dcx d
mov a,d
ora e
jnz count
lxi d,zero ; Print zeroes
call puts
mov a,b
call puta
lxi d,cross ; Print crossings
call puts
mov a,c
call puta
lxi d,tms
jmp puts
;;; Print character in A using CP/M, keeping registers
putc: push b
push d
push h
mov e,a
mvi c,2
call 5
jmp resrgs
;;; Print number in A, keeping registers
puta: push b
push d
push h
lxi h,num
putad: mvi c,-1
putal: inr c
sui 10
jnc putal
adi 10+'0'
dcx h
mov m,a
mov a,c
ana a
jnz putad
xchg
mvi c,9
call 5
jmp resrgs
;;; Print string in DE using CP/M, keeping registers
puts: push b
push d
push h
mvi c,9
call 5
resrgs: pop h
pop d
pop b
ret
cdehl: mov a,d
cmp h
rnz
mov a,e
cmp l
ret
cbcde: mov a,b
cmp d
rnz
mov a,c
cmp e
ret
chlbc: mov a,h
cmp b
rnz
mov a,l
cmp c
ret
;;; Strings
db '***'
num: db '$'
frst99: db 'First 99 Mertens numbers:',13,10,' $'
nl: db 13,10,'$'
zero: db 'M(N) is zero $'
cross: db ' times.',13,10,'M(N) crosses zero $'
tms: db ' times.$'
;;; Numbers are stored page-aligned after program
MM: equ ($/256)*256+256
- Output:
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
8086 Assembly
MAX: equ 1000 ; Amount of Mertens numbers to generate
puts: equ 9 ; MS-DOS syscall to print a string
putch: equ 2 ; MS-DOS syscall to print a character
cpu 8086
org 100h
section .text
;;; Generate Mertens numbers
mov bx,M ; BX = pointer to start of Mertens numbers
mov si,1 ; Current Mertens number
mov [si+bx],byte 1 ; First Mertens number is 1
outer: inc si ; Next Mertens number
mov [si+bx],byte 1 ; Starts out at 1...
mov cx,2 ; CX = from 2 to current number,
inner: mov ax,si ; Divide current number,
xor dx,dx
div cx ; By CX
mov di,ax
mov al,[di+bx] ; Get value at that location
sub [si+bx],al ; Subtract from current number
inc cx
cmp cx,si
jbe inner
cmp si,MAX
jbe outer
;;; Print the table
mov dx,frst99 ; First string
call outstr
mov si,1 ; Start at index 1
mov dh,9 ; Column count
table: mov cl,[si+bx] ; Get item
test cl,cl
mov dl,' '
jns .print ; Positive?
mov dl,'-' ; Otherwise, it is negative,
neg cl ; print ' ' and negate
.print: call putc ; Print space or minus
add cl,'0' ; Add ASCII 0
mov dl,cl
call putc ; Print number
mov dl,' '
call putc ; Print space
dec dh ; One less column left
jnz .next
mov dx,nl ; Print newline
call outstr
mov dh,10
.next: inc si ; Done yet?
cmp si,100
jb table ; If not, print next item from table
;;; Calculate zeroes and crossings
xor cx,cx ; CL = zeroes, CH = crossings
mov si,1
mov al,[si+bx] ; AL = current item
zc: inc si
mov ah,al ; AH = previous item
mov al,[si+bx]
test al,al ; Zero?
jnz .next
inc cx ; Then increment zero counter
test ah,ah ; Previous one also zero?
jz .next
inc ch ; Then increment crossing counter
.next: cmp si,MAX ; Done yet?
jbe zc
;;; Print zeroes and crossings
mov dx,zero
call outstr
mov al,cl
call putal
mov dx,cross
call outstr
mov al,ch
call putal
mov dx,tms
jmp outstr
putc: mov ah,putch ; Print character
int 21h
ret
;;; Print AL in decimal format
putal: mov di,num
.loop: aam ; Extract digit
add al,'0' ; Store digit
dec di
mov [di],al
mov al,ah ; Rest of number
test al,al ; Done?
jnz .loop ; If not, get more digits
mov dx,di ; Otherwise, print string
outstr: mov ah,puts
int 21h
ret
section .data
db '***' ; Number output placeholder
num: db '$'
frst99: db 'First 99 Mertens numbers:',13,10,' $'
nl: db 13,10,'$'
zero: db 'M(N) is zero $'
cross: db ' times.',13,10,'M(N) crosses zero $'
tms: db ' times.$'
section .bss
mm: resb MAX ; Mertens numbers
M: equ mm-1 ; 1-based indexing
- Output:
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
Action!
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.
INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit
PROC MertensNumbers(INT ARRAY m INT count)
INT n,k
m(1)=1
FOR n=2 TO count
DO
m(n)=1
FOR k=2 TO n
DO
m(n)==-m(n/k)
OD
OD
RETURN
PROC PrintMertens(INT ARRAY m INT count)
CHAR ARRAY s(6)
INT i,col
PrintF("First %I Mertens numbers:%E ",count)
col=1
FOR i=1 TO count
DO
StrI(m(i),s)
PrintF("%3S",s)
col==+1
IF col=10 THEN
col=0 PutE()
FI
OD
RETURN
PROC Main()
DEFINE MAX="1001"
INT ARRAY m(MAX)
INT i,zeroCnt=[0],crossCnt=[0],prev=[0]
Put(125) PutE() ;clear the screen
PrintF("Calculation of Mertens numbers,%E please wait...")
MertensNumbers(m,MAX)
Put(125) PutE() ;clear the screen
PrintMertens(m,99)
FOR i=1 TO MAX
DO
IF m(i)=0 THEN
zeroCnt==+1
IF prev THEN
crossCnt==+1
FI
FI
prev=m(i)
OD
PrintF("%EM(n) is zero %I times for 1<=n<=%I.%E",zeroCnt,MAX-1)
PrintF("%EM(n) crosses zero %I times for 1<=n<=%I.%E",crossCnt,MAX-1)
RETURN
- Output:
Screenshot from Atari 8-bit computer
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(n) is zero 92 times for 1<=n<=1000. M(n) crosses zero 59 times for 1<=n<=1000.
ALGOL 68
...which is...
BEGIN # compute values of the Mertens function #
# Generate Mertens numbers #
[ 1 : 1000 ]INT m;
m[ 1 ] := 1;
FOR n FROM 2 TO UPB m DO
m[ n ] := 1;
FOR k FROM 2 TO n DO m[ n ] -:= m[ n OVER k ] OD
OD;
# Print table #
print( ( "The first 99 Mertens numbers are:", newline ) );
print( ( " " ) );
INT k := 9;
FOR n TO 99 DO
print( ( whole( m[ n ], -3 ) ) );
IF ( k -:= 1 ) = 0 THEN
k := 10;
print( ( newline ) )
FI
OD;
# Calculate zeroes and crossings #
INT zero := 0;
INT cross := 0;
FOR n FROM 2 TO UPB m DO
IF m[ n ] = 0 THEN
zero +:= 1;
IF m[ n - 1 ] /= 0 THEN cross +:= 1 FI
FI
OD;
print( ( newline ) );
print( ( "M(N) is zero ", whole( zero, -4 ), " times.", newline ) );
print( ( "M(N) crosses zero ", whole( cross, -4 ), " times.", newline ) )
END
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
ALGOL W
begin % compute values of the Mertens function %
integer array M ( 1 :: 1000 );
integer k, zero, cross;
% Generate Mertens numbers %
M( 1 ) := 1;
for n := 2 until 1000 do begin
M( n ) := 1;
for k := 2 until n do M( n ) := M( n ) - M( n div k )
end for_n ;
% Print table %
write( "The first 99 Mertens numbers are:" );
write( " " );
k := 9;
for n := 1 until 99 do begin
writeon( i_w := 3, s_w := 0, M( n ) );
k := k - 1;
if k = 0 then begin
k := 10;
write()
end if_k_eq_0
end for_n ;
% Calculate zeroes and crossings %
zero := 0;
cross := 0;
for n :=2 until 1000 do begin
if M( n ) = 0 then begin
zero := zero + 1;
if M( n - 1 ) not = 0 then cross := cross + 1
end if_M_n_eq_0
end for_n ;
write( i_w := 2, s_w := 0, "M(N) is zero ", zero, " times." );
write( i_w := 2, s_w := 0, "M(N) crosses zero ", cross, " times." )
end.
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
APL
mertens←{
step ← {⍵,-⍨/⌽1,⍵[⌊n÷1↓⍳n←1+≢⍵]}
m1000 ← step⍣999⊢,1
zero ← m1000+.=0
cross ← +/(~∧1⌽⊢)m1000≠0
⎕←'First 99 Mertens numbers:'
⎕←10 10⍴'∘',m1000
⎕←'M(N) is zero ',(⍕zero),' times.'
⎕←'M(N) crosses zero ',(⍕cross),' times.'
}
- Output:
First 99 Mertens numbers: ∘ 1 0 ¯1 ¯1 ¯2 ¯1 ¯2 ¯2 ¯2 ¯1 ¯2 ¯2 ¯3 ¯2 ¯1 ¯1 ¯2 ¯2 ¯3 ¯3 ¯2 ¯1 ¯2 ¯2 ¯2 ¯1 ¯1 ¯1 ¯2 ¯3 ¯4 ¯4 ¯3 ¯2 ¯1 ¯1 ¯2 ¯1 0 0 ¯1 ¯2 ¯3 ¯3 ¯3 ¯2 ¯3 ¯3 ¯3 ¯3 ¯2 ¯2 ¯3 ¯3 ¯2 ¯2 ¯1 0 ¯1 ¯1 ¯2 ¯1 ¯1 ¯1 0 ¯1 ¯2 ¯2 ¯1 ¯2 ¯3 ¯3 ¯4 ¯3 ¯3 ¯3 ¯2 ¯3 ¯4 ¯4 ¯4 ¯3 ¯4 ¯4 ¯3 ¯2 ¯1 ¯1 ¯2 ¯2 ¯1 ¯1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
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
]
mertens: function [z][sum map 1..z => mobius]
print "The first 99 Mertens numbers are:"
loop split.every:20 [""]++map 1..99 => mertens 'a [
print map a 'item -> pad to :string item 2
]
print ""
mertens1000: map 1..1000 => mertens
print ["Times M(x) is zero between 1 and 1000:" size select mertens1000 => zero?]
crossed: new 0
fold mertens1000 [a,b][if and? zero? b not? zero? a -> inc 'crossed, b]
print ["Times M(x) crosses zero between 1 and 1000:" crossed]
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 Times M(x) is zero between 1 and 1000: 92 Times M(x) crosses zero between 1 and 1000: 59
AutoHotkey
result := "first 100 terms:`n"
loop 100
result .= SubStr(" " Mertens(A_Index), -1) . (Mod(A_Index, 10) ? " " : "`n")
eqZero := crZero := 0, preced:=1
loop 1000
{
if !(x := Mertens(A_Index))
eqZero++, crZero += preced<>0 ? 1 : 0
preced := x
}
result .= "`nfirst 1000 terms:"
MsgBox, 262144, , % result .= "`nequal to zero : " eqZero "`ncrosses zero : " crZero
return
Mertens(n){
loop % n
result += Möbius(A_Index)
return result
}
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:
first 100 terms: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 first 1000 terms: equal to zero : 92 crosses zero : 59
BASIC
Note that if you actually try this on a real 8-bit micro, this will take literal hours to run. Interpreted BASIC is not fast.
For comparison, the 8080 and 8086 assembly versions above run in around 4 minutes and 15 seconds respectively, on real hardware. This took nearly 4 hours on the 8080 (using MBASIC) and a little over 1 hour on the 8086 (using GWBASIC).
10 DEFINT C,Z,N,K,M: DIM M(1000)
20 M(1)=1
30 FOR N=2 TO 1000
40 M(N)=1
50 FOR K=2 TO N: M(N) = M(N)-M(INT(N/K)): NEXT
60 NEXT
70 PRINT "First 99 Mertens numbers:"
80 PRINT " ";
90 FOR N=1 TO 99
100 PRINT USING "###";M(N);
110 IF N MOD 10 = 9 THEN PRINT
120 NEXT
130 C=0: Z=0
140 FOR N=1 TO 1000
150 IF M(N)=0 THEN Z=Z+1: IF M(N-1)<>0 THEN C=C+1
160 NEXT
170 PRINT "M(N) is zero";Z;"times."
180 PRINT "M(N) crosses zero";C;"times."
190 END
- Output:
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
BASIC256
arraybase 1
dim M(1000)
M[1] = 1
for n = 2 to 1000
M[n] = 1
for k = 2 to n
M[n] = M[n] - M[int(n/k)]
next k
next n
print "First 99 Mertens numbers:"
print " ";
for n = 1 to 99
print rjust(string(M[n]),3);
if n mod 10 = 9 then print
next n
numCruza = 0
numEsCero = 0
for n = 1 to 1000
if M[n] = 0 then
numEsCero += 1
if M[n-1] <> 0 then numCruza += 1
end if
next n
print
print "M(n) is zero "; numEsCero; " times."
print "M(n) crosses zero "; numCruza; " times."
- Output:
Same as BASIC entry.
Run BASIC
dim M(1000)
M(1) = 1
for n = 2 to 1000
M(n) = 1
for k = 2 to n
M(n) = M(n)-M(int(n/k))
next k
next n
print "First 99 Mertens numbers:"
print " ";
for n = 1 to 99
print using("###", M(n));
if n mod 10 = 9 then print
next n
numCruza = 0
numEsCero = 0
for n = 1 to 1000
if M(n) = 0 then
numEsCero = numEsCero +1
if M(n-1) <> 0 then numCruza = numCruza +1
end if
next n
print
print "M(n) is zero "; numEsCero; " times."
print "M(n) crosses zero "; numCruza; " times."
- Output:
Same as BASIC entry.
True BASIC
DIM m(1000)
LET m(1) = 1
FOR n = 2 TO 1000
LET m(n) = 1
FOR k = 2 TO n
LET m(n) = m(n)-m(INT(n/k))
NEXT k
NEXT n
PRINT "First 99 Mertens numbers:"
PRINT " ";
FOR n = 1 TO 99
PRINT " ";
PRINT USING "##": m(n);
!IF REMAINDER(ROUND(n),10) = 9 THEN PRINT
IF MOD(n,10) = 9 THEN PRINT
NEXT n
LET numcruza = 0
LET numeszero = 0
FOR n = 1 TO 1000
IF m(n) = 0 THEN
LET numeszero = numeszero+1
IF m(n-1) <> 0 THEN LET numcruza = numcruza+1
END IF
NEXT n
PRINT
PRINT "M(n) is zero"; numeszero; "times."
PRINT "M(n) crosses zero"; numcruza; "times."
END
- Output:
Same as FreeBASIC entry.
XBasic
PROGRAM "Mertens"
VERSION "0.0000"
DECLARE FUNCTION Entry ()
FUNCTION Entry ()
DIM M[1000]
M[1] = 1
FOR n = 2 TO 1000
M[n] = 1
FOR k = 2 TO n
M[n] = M[n] - M[INT(n/k)]
NEXT k
NEXT n
PRINT "First 99 Mertens numbers:"
PRINT " ";
FOR n = 1 TO 99
PRINT FORMAT$("###", M[n]);
IF n MOD 10 = 9 THEN PRINT
NEXT n
numCruza = 0
numEsCero = 0
FOR n = 1 TO 1000
IF M[n] = 0 THEN
INC numEsCero
IF M[n-1] <> 0 THEN INC numCruza
END IF
NEXT n
PRINT
PRINT "M(n) is zero"; numEsCero; " times."
PRINT "M(n) crosses zero"; numCruza; " times."
END FUNCTION
END PROGRAM
- Output:
Same as FreeBASIC entry.
Yabasic
dim M(1000)
M(1) = 1
for n = 2 to 1000
M(n) = 1
for k = 2 to n
M(n) = M(n) - M(int(n/k))
next k
next n
print "First 99 Mertens numbers:"
print " ";
for n = 1 to 99
print M(n) using("###");
if mod(n, 10) = 9 print
next n
numCruza = 0
numEsCero = 0
for n = 1 to 1000
if M(n) = 0 then
numEsCero = numEsCero + 1
if M(n-1) <> 0 numCruza = numCruza + 1
end if
next n
print
print "M(n) is zero ", numEsCero, " times."
print "M(n) crosses zero ", numCruza, " times."
- Output:
Same as FreeBASIC entry.
==Bash==
#!/bin/bash
MAX=1000
m[1]=1
for n in `seq 2 $MAX`
do
m[n]=1
for k in `seq 2 $n`
do
m[n]=$((m[n]-m[n/k]))
done
done
echo 'The first 99 Mertens numbers are:'
echo -n ' '
for n in `seq 1 99`
do
printf '%2d ' ${m[n]}
test $((n%10)) -eq 9 && echo
done
zero=0
cross=0
for n in `seq 1 $MAX`
do
if [ ${m[n]} -eq 0 ]
then
((zero++))
test ${m[n-1]} -ne 0 && ((cross++))
fi
done
echo "M(N) is zero $zero times."
echo "M(N) crosses zero $cross times."
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
BCPL
get "libhdr"
manifest $( limit = 1000 $)
let mertens(v, max) be
$( v!1 := 1
for n = 2 to max do
$( v!n := 1
for k = 2 to n do
v!n := v!n - v!(n/k)
$)
$)
let start() be
$( let m = vec limit
let eqz, crossz = 0, 0
writes("The first 99 Mertens numbers are:*N")
mertens(m, limit)
for y=0 to 90 by 10 do
$( for x=0 to 9 do
test x+y=0
then writes(" ")
else writed(m!(x+y),3)
wrch('*N')
$)
for x=2 to limit do
if m!x=0 then
$( eqz := eqz + 1
unless m!(x-1)=0 do crossz := crossz + 1
$)
writef("M(N) is zero %N times.*N", eqz)
writef("M(N) crosses zero %N times.*N", crossz)
$)
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
C
#include <stdio.h>
#include <stdlib.h>
int* mertens_numbers(int max) {
int* m = malloc((max + 1) * sizeof(int));
if (m == NULL)
return m;
m[1] = 1;
for (int n = 2; n <= max; ++n) {
m[n] = 1;
for (int k = 2; k <= n; ++k)
m[n] -= m[n/k];
}
return m;
}
int main() {
const int max = 1000;
int* mertens = mertens_numbers(max);
if (mertens == NULL) {
fprintf(stderr, "Out of memory\n");
return 1;
}
printf("First 199 Mertens numbers:\n");
const int count = 200;
for (int i = 0, column = 0; i < count; ++i) {
if (column > 0)
printf(" ");
if (i == 0)
printf(" ");
else
printf("%2d", mertens[i]);
++column;
if (column == 20) {
printf("\n");
column = 0;
}
}
int zero = 0, cross = 0, previous = 0;
for (int i = 1; i <= max; ++i) {
int m = mertens[i];
if (m == 0) {
++zero;
if (previous != 0)
++cross;
}
previous = m;
}
free(mertens);
printf("M(n) is zero %d times for 1 <= n <= %d.\n", zero, max);
printf("M(n) crosses zero %d times for 1 <= n <= %d.\n", cross, max);
return 0;
}
- Output:
First 199 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 M(n) is zero 92 times for 1 <= n <= 1000. M(n) crosses zero 59 times for 1 <= n <= 1000.
C++
#include <iomanip>
#include <iostream>
#include <vector>
std::vector<int> mertens_numbers(int max) {
std::vector<int> m(max + 1, 1);
for (int n = 2; n <= max; ++n) {
for (int k = 2; k <= n; ++k)
m[n] -= m[n / k];
}
return m;
}
int main() {
const int max = 1000;
auto m(mertens_numbers(max));
std::cout << "First 199 Mertens numbers:\n";
for (int i = 0, column = 0; i < 200; ++i) {
if (column > 0)
std::cout << ' ';
if (i == 0)
std::cout << " ";
else
std::cout << std::setw(2) << m[i];
++column;
if (column == 20) {
std::cout << '\n';
column = 0;
}
}
int zero = 0, cross = 0, previous = 0;
for (int i = 1; i <= max; ++i) {
if (m[i] == 0) {
++zero;
if (previous != 0)
++cross;
}
previous = m[i];
}
std::cout << "M(n) is zero " << zero << " times for 1 <= n <= 1000.\n";
std::cout << "M(n) crosses zero " << cross << " times for 1 <= n <= 1000.\n";
return 0;
}
- Output:
First 199 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 M(n) is zero 92 times for 1 <= n <= 1000. M(n) crosses zero 59 times for 1 <= n <= 1000.
CLU
% Generate Mertens numbers up to a given limit
mertens = proc (limit: int) returns (array[int])
M: array[int] := array[int]$fill(1,limit,0)
M[1] := 1
for n: int in int$from_to(2,limit) do
M[n] := 1
for k: int in int$from_to(2,n) do
M[n] := M[n] - M[n/k]
end
end
return (M)
end mertens
start_up = proc ()
max = 1000
po: stream := stream$primary_output()
M: array[int] := mertens(max)
stream$putl(po, "The first 99 Mertens numbers are:")
for y: int in int$from_to_by(0,90,10) do
for x: int in int$from_to(0,9) do
stream$putright(po, int$unparse(M[x+y]), 3)
except when bounds:
stream$putright(po, "", 3)
end
end
stream$putl(po, "")
end
eqz: int := 0
crossz: int := 0
for i: int in int$from_to(2,max) do
if M[i]=0 then
eqz := eqz + 1
if M[i-1]~=0 then crossz := crossz + 1 end
end
end
stream$putl(po, "M(N) is zero " || int$unparse(eqz) || " times.")
stream$putl(po, "M(N) crosses zero " || int$unparse(crossz) || " times.")
end start_up
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
COBOL
IDENTIFICATION DIVISION.
PROGRAM-ID. MERTENS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 VARIABLES.
03 M PIC S99 OCCURS 1000 TIMES.
03 N PIC 9(4).
03 K PIC 9(4).
03 V PIC 9(4).
03 IS-ZERO PIC 99 VALUE 0.
03 CROSS-ZERO PIC 99 VALUE 0.
01 OUTPUT-FORMAT.
03 OUT-ITEM.
05 OUT-NUM PIC -9.
05 FILLER PIC X VALUE SPACE.
03 OUT-LINE PIC X(30) VALUE SPACES.
03 OUT-PTR PIC 99 VALUE 4.
PROCEDURE DIVISION.
BEGIN.
PERFORM GENERATE-MERTENS.
PERFORM WRITE-TABLE.
PERFORM COUNT-ZEROES.
STOP RUN.
GENERATE-MERTENS.
MOVE 1 TO M(1).
PERFORM MERTENS-OUTER-LOOP VARYING N FROM 2 BY 1
UNTIL N IS GREATER THAN 1000.
MERTENS-OUTER-LOOP.
MOVE 1 TO M(N).
PERFORM MERTENS-INNER-LOOP VARYING K FROM 2 BY 1
UNTIL K IS GREATER THAN N.
MERTENS-INNER-LOOP.
DIVIDE N BY K GIVING V.
SUBTRACT M(V) FROM M(N).
WRITE-TABLE.
DISPLAY "The first 99 Mertens numbers are: "
PERFORM WRITE-ITEM VARYING N FROM 1 BY 1
UNTIL N IS GREATER THAN 99.
WRITE-ITEM.
MOVE M(N) TO OUT-NUM.
STRING OUT-ITEM DELIMITED BY SIZE INTO OUT-LINE
WITH POINTER OUT-PTR.
IF OUT-PTR IS EQUAL TO 31,
DISPLAY OUT-LINE,
MOVE 1 TO OUT-PTR.
COUNT-ZEROES.
PERFORM TEST-N-ZERO VARYING N FROM 2 BY 1
UNTIL N IS GREATER THAN 1000.
DISPLAY "M(N) is zero " IS-ZERO " times.".
DISPLAY "M(N) crosses zero " CROSS-ZERO " times.".
TEST-N-ZERO.
IF M(N) IS EQUAL TO ZERO,
ADD 1 TO IS-ZERO,
SUBTRACT 1 FROM N GIVING K,
IF M(K) IS NOT EQUAL TO ZERO,
ADD 1 TO CROSS-ZERO.
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
Cowgol
include "cowgol.coh";
const MAX := 1000;
# Table output
sub printtab(n: int8) is
if n<0 then
print_char('-');
n := -n;
else
print_char(' ');
end if;
print_char(n as uint8 + '0');
print_char(' ');
end sub;
# Generate Merten numbers
var M: int8[MAX+1];
M[0] := 0;
M[1] := 1;
var n: @indexof M := 2;
while n < @sizeof M loop
M[n] := 1;
var k: @indexof M := 2;
while k <= n loop
M[n] := M[n] - M[n/k];
k := k + 1;
end loop;
n := n + 1;
end loop;
# Find zeroes and crossings
var zero: uint8 := 0;
var cross: uint8 := 0;
n := 1;
while n < @sizeof M loop
if M[n] == 0 then
zero := zero + 1;
if M[n-1] != 0 then
cross := cross + 1;
end if;
end if;
n := n + 1;
end loop;
# Print table
print("The first 99 Mertens numbers are:\n");
print(" ");
n := 1;
var col: uint8 := 9;
while n < 100 loop
printtab(M[n]);
col := col - 1;
if col == 0 then
print_nl();
col := 10;
end if;
n := n + 1;
end loop;
print("M(n) is zero "); print_i8(zero); print(" times\n");
print("M(n) crosses zero "); print_i8(cross); print(" times\n");
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(n) is zero 92 times M(n) crosses zero 59 times
Delphi
program Mertens_function;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
type
TMertens = record
merts: TArray<Integer>;
zeros, crosses: Integer;
class function Mertens(_to: Integer): TMertens; static;
end;
{ TMertens }
class function TMertens.Mertens(_to: Integer): TMertens;
var
sum, zeros, crosses: Integer;
begin
if _to < 1 then
_to := 1;
sum := 0;
zeros := 0;
crosses := 0;
SetLength(Result.merts, _to + 1);
var primes := [2];
for var i := 1 to _to do
begin
var j := i;
var cp := 0;
var spf := false;
for var p in primes do
begin
if p > j then
Break;
if j mod p = 0 then
begin
j := j div p;
inc(cp);
end;
if j mod p = 0 then
begin
spf := true;
Break;
end;
end;
if (cp = 0) and (i > 2) then
begin
cp := 1;
SetLength(primes, Length(primes) + 1);
primes[High(primes)] := i;
end;
if not spf then
begin
if cp mod 2 = 0 then
inc(sum)
else
dec(sum);
end;
Result.merts[i] := sum;
if sum = 0 then
begin
inc(zeros);
if (i > 1) and (Result.merts[i - 1] <> 0) then
inc(crosses);
end;
end;
Result.zeros := zeros;
Result.crosses := crosses;
end;
begin
var m := TMertens.mertens(1000);
writeln('Mertens sequence - First 199 terms:');
for var i := 0 to 199 do
begin
if i = 0 then
begin
write(' ');
Continue;
end;
if i mod 20 = 0 then
writeln;
write(format(' %3d', [m.merts[i]]));
end;
writeln(#10#10'Equals zero ', m.zeros, ' times between 1 and 1000');
writeln(#10'Crosses zero ', m.crosses, ' times between 1 and 1000');
{$IFNDEF UNIX} readln; {$ENDIF}
end.
Draco
proc nonrec mertens([*] short m) void:
word n,k;
m[1] := 1;
for n from 2 upto dim(m,1)-1 do
m[n] := 1;
for k from 2 upto n do
m[n] := m[n] - m[n/k]
od
od
corp
proc nonrec main() void:
[1001] short m;
word x, y, eqz, crossz;
mertens(m);
writeln("The first 99 Mertens numbers are:");
for y from 0 by 10 upto 90 do
for x from 0 upto 9 do
if x+y=0
then write(" ")
else write(m[x+y]:3)
fi
od;
writeln()
od;
eqz := 0;
crossz := 0;
for x from 2 upto dim(m,1)-1 do
if m[x]=0 then
eqz := eqz + 1;
if m[x-1]~=0 then crossz := crossz + 1 fi
fi
od;
writeln("M(N) is zero ",eqz," times.");
writeln("M(N) crosses zero ",crossz," times.")
corp
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
Dyalect
func mertensNumbers(max) {
let mertens = Array.Empty(max + 1, 1)
for n in 2..max {
for k in 2..n {
mertens[n] -= mertens[n / k]
}
}
mertens
}
let max = 1000
let mertens = mertensNumbers(max)
let count = 200
let columns = 20
print("First \(count - 1) Mertens numbers:")
for i in 0..<count {
if i % columns > 0 {
print(" ", terminator: "")
}
print(i == 0 ? " " : mertens[i].ToString().PadLeft(2, ' ') + " ", terminator: "")
if (i + 1) % columns == 0 {
print()
}
}
var (zero, cross, previous) = (0, 0, 0)
for i in 1..max {
let m = mertens[i]
if m == 0 {
zero += 1
if previous != 0 {
cross += 1
}
}
previous = m
}
print("M(n) is zero \(zero) times for 1 <= n <= \(max).")
print("M(n) crosses zero \(cross) times for 1 <= n <= \(max).")
- Output:
First 199 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 M(n) is zero 92 times for 1 <= n <= 1000. M(n) crosses zero 59 times for 1 <= n <= 1000.
EasyLang
len mertens[] 1000
mertens[1] = 1
for n = 2 to 1000
mertens[n] = 1
for k = 2 to n
mertens[n] -= mertens[n div k]
.
.
print "First 99 Mertens numbers:"
write " "
numfmt 0 2
for n = 1 to 99
write mertens[n] & " "
if n mod 10 = 9
print ""
.
.
for n = 1 to 1000
if mertens[n] = 0
zeros += 1
if mertens[n - 1] <> 0
crosses += 1
.
.
.
print ""
print "In the first 1000 terms of the Mertens sequence there are:"
print zeros & " zeros"
print crosses & " zero crosses"
- Output:
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 In the first 1000 terms of the Mertens sequence there are: 92 zeros 59 zero crosses
F#
This task uses Möbius_function (F#)
// Mertens function. Nigel Galloway: January 31st., 2021
let mertens=mobius|>Seq.scan((+)) 0|>Seq.tail
mertens|>Seq.take 500|>Seq.chunkBySize 25|>Seq.iter(fun n->Array.iter(printf "%3d") n;printfn "\n####")
let n=mertens|>Seq.take 1000|>Seq.mapi(fun n g->(n+1,g))|>Seq.groupBy snd|>Map.ofSeq
n|>Map.iter(fun n g->printf "%3d->" n; g|>Seq.iter(fun(n,_)->printf "%3d " n); printfn "\n####")
printfn "%d Zeroes\n####" (Seq.length (snd n.[0]))
printfn "Crosses zero %d times" (mertens|>Seq.take 1000|>Seq.pairwise|>Seq.sumBy(fun(n,g)->if n<>0 && g=0 then 1 else 0)))
- Output:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 -8 -7 -6 -5 -5 -4 -3 -3 -3 -2 -1 -2 -2 -1 0 1 1 2 3 4 4 5 4 3 3 3 4 3 3 2 1 0 0 -1 -1 0 0 1 0 -1 -1 -2 -2 -2 -2 -2 -3 -2 -2 -1 -1 -2 -2 -1 0 -1 -1 -2 -3 -2 -2 -2 -1 -2 -2 -1 -2 -1 -1 -2 -2 -3 -3 -4 -3 -3 -3 -4 -3 -3 -3 -4 -5 -6 -6 -7 -8 -7 -7 -7 -8 -7 -7 -8 -8 -7 -7 -7 -6 -5 -5 -4 -3 -2 -2 -1 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -2 -1 -1 0 1 0 0 0 1 2 2 1 1 2 2 3 3 3 3 2 3 2 2 1 1 1 1 0 -1 0 0 -1 0 -1 -1 -1 0 0 0 1 0 -1 -1 -1 -2 -1 -1 -2 -3 -3 -3 -2 -2 -3 -3 -2 -1 -2 -2 -3 -2 -2 -2 -3 -2 -1 -1 0 1 2 2 1 2 1 1 0 -1 0 0 0 -1 0 0 -1 -2 -1 -1 0 0 1 1 2 1 0 0 -1 0 0 0 0 -1 0 0 -1 -2 -3 -3 -4 -5 -6 -6 -5 -6 -7 -7 -7 -8 -9 -9 -8 -7 -6 -6 -7 -7 -6 -6 -5 -4 -5 -5 -6 -5 -5 -5 -6 -5 -6 -6 -7 -6 -7 -7 -6 -7 -6 -6 -5 -6 -6 -6 -6 -5 -6 -6 -5 -4 -5 -5 -4 -4 -5 -5 -4 -4 -5 -5 -4 -5 -5 -5 -4 -5 -6 -6 #### -12->665 666 678 683 684 -11->661 663 664 667 668 670 673 677 679 680 682 685 686 -10->659 660 662 669 671 672 674 675 676 681 687 688 -9->443 444 654 658 689 691 692 693 -8->199 200 286 290 293 294 442 445 653 655 656 657 690 694 -7->197 198 201 285 287 288 289 291 292 295 296 297 439 440 441 446 449 450 465 467 468 470 647 648 651 652 695 696 -6->114 193 195 196 202 283 284 298 435 436 438 447 448 451 452 457 461 463 464 466 469 471 472 474 475 476 477 479 480 499 500 509 646 649 650 697 -5->110 113 115 116 117 182 191 192 194 203 204 282 299 300 318 434 437 453 455 456 458 459 460 462 473 478 481 483 484 487 488 491 492 494 495 496 498 501 503 504 506 507 508 510 619 620 621 645 698 701 702 705 710 711 712 743 744 762 -4-> 31 32 73 79 80 81 83 84 109 111 112 118 139 140 174 175 176 181 183 184 186 190 205 273 277 281 301 313 317 319 320 322 433 454 482 485 486 489 490 493 497 502 505 511 512 513 618 622 643 644 699 700 703 704 706 709 713 715 716 742 745 761 763 764 765 830 834 -3-> 13 19 20 30 33 43 44 45 47 48 49 50 53 54 71 72 74 75 76 78 82 85 105 107 108 119 120 121 131 132 138 141 173 177 179 180 185 187 188 189 206 207 208 246 258 271 272 274 275 276 278 279 280 302 311 312 314 315 316 321 323 324 325 374 375 376 379 380 385 389 431 432 514 523 524 525 617 623 624 625 627 628 631 632 642 707 708 714 717 719 720 730 733 741 746 747 748 751 752 754 757 759 760 766 769 777 829 831 832 833 835 836 837 839 840 841 861 863 864 -2-> 5 7 8 9 11 12 14 17 18 21 23 24 25 29 34 37 42 46 51 52 55 56 61 67 68 70 77 86 89 90 103 104 106 122 127 128 130 133 137 142 154 157 170 171 172 178 209 211 212 241 242 243 244 245 247 248 251 252 257 259 260 261 263 264 266 269 270 303 304 307 308 310 326 370 373 377 378 381 383 384 386 387 388 390 410 430 515 516 518 521 522 526 530 531 532 534 610 613 615 616 626 629 630 633 641 718 721 722 727 728 729 731 732 734 735 736 739 740 749 750 753 755 756 758 767 768 770 773 774 775 776 778 787 788 790 827 828 838 842 857 859 860 862 865 -1-> 3 4 6 10 15 16 22 26 27 28 35 36 38 41 57 59 60 62 63 64 66 69 87 88 91 92 102 123 124 125 126 129 134 135 136 143 144 151 152 153 155 156 158 165 167 168 169 210 213 233 234 239 240 249 250 253 255 256 262 265 267 268 305 306 309 327 328 354 357 359 360 361 367 368 369 371 372 382 391 392 402 406 409 411 412 421 426 429 517 519 520 527 528 529 533 535 536 609 611 612 614 634 638 639 640 723 724 725 726 737 738 771 772 779 780 782 783 784 786 789 791 792 797 826 843 844 845 846 847 848 854 855 856 858 866 867 868 885 887 888 890 891 892 894 897 907 908 909 911 912 0-> 2 39 40 58 65 93 101 145 149 150 159 160 163 164 166 214 231 232 235 236 238 254 329 331 332 333 353 355 356 358 362 363 364 366 393 401 403 404 405 407 408 413 414 419 420 422 423 424 425 427 428 537 541 607 608 635 636 637 781 785 793 795 796 798 811 812 814 823 824 825 849 850 853 869 877 883 884 886 889 893 895 896 898 903 904 906 910 913 915 916 919 920 1-> 1 94 97 98 99 100 146 147 148 161 162 215 216 230 237 330 334 337 338 349 350 351 352 365 394 397 399 400 415 416 418 538 539 540 542 606 794 799 800 801 806 809 810 813 815 816 822 851 852 870 874 875 876 878 881 882 899 900 902 905 914 917 918 921 947 948 971 972 978 987 988 991 992 994 997 2-> 95 96 217 229 335 336 339 340 345 347 348 395 396 398 417 543 544 602 603 604 605 802 805 807 808 817 821 871 872 873 879 880 901 922 942 946 949 950 953 954 957 970 973 977 979 980 981 983 984 986 989 990 993 995 996 998 999 1000 3->218 223 224 225 227 228 341 342 343 344 346 545 547 548 549 550 601 803 804 818 819 820 923 924 925 929 938 941 943 944 945 951 952 955 956 958 962 963 964 969 974 975 976 982 985 4->219 220 222 226 546 551 552 557 558 561 563 564 577 578 599 600 926 927 928 930 931 932 937 939 940 959 960 961 965 967 968 5->221 553 555 556 559 560 562 565 569 571 572 574 575 576 579 580 582 595 596 598 933 935 936 966 6->554 566 567 568 570 573 581 583 584 585 587 588 590 593 594 597 934 7->586 589 591 592 #### 92 Zeroes #### Crosses zero 59 times
Factor
USING: formatting grouping io kernel math math.extras
math.ranges math.statistics prettyprint sequences ;
! Take the cumulative sum of the mobius sequence to avoid
! summing lower terms over and over.
: mertens-upto ( n -- seq ) [1,b] [ mobius ] map cum-sum ;
"The first 199 terms of the Mertens sequence:" print
199 mertens-upto " " prefix 20 group
[ [ "%3s" printf ] each nl ] each nl
"In the first 1,000 terms of the Mertens sequence there are:"
print 1000 mertens-upto
[ [ zero? ] count bl pprint bl "zeros." print ]
[
2 <clumps> [ first2 [ 0 = not ] [ zero? ] bi* and ] count bl
pprint bl "zero crossings." print
] bi
- Output:
The first 199 terms of the Mertens sequence: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 In the first 1,000 terms of the Mertens sequence there are: 92 zeros. 59 zero crossings.
Forth
: AMOUNT 1000 ;
variable mertens AMOUNT cells allot
: M 1- cells mertens + ; \ 1-indexed array
: make-mertens
1 1 M !
2 begin dup AMOUNT <= while
1 over M !
2 begin over over >= while
over over / M @
2 pick M @ swap -
2 pick M !
1+ repeat
drop
1+ repeat
drop
;
: print-row
begin dup while
swap dup M @ 3 .r 1+
swap 1-
repeat
drop
;
: print-table ." "
1 9 print-row cr
begin dup 100 < while 10 print-row cr repeat
drop
;
: find-zero-cross
0 0
1 begin dup AMOUNT <= while
dup M @ 0= if
swap 1+ swap
dup 1- M @ 0<> if rot 1+ -rot then
then
1+
repeat
drop
;
make-mertens
." The first 99 Mertens numbers are:" cr print-table
find-zero-cross
." M(N) is zero " . ." times." cr
." M(N) crosses zero " . ." times." cr
bye
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
Fortran
program Mertens
implicit none
integer M(1000), n, k, zero, cross
C Generate Mertens numbers
M(1) = 1
do 10 n=2, 1000
M(n) = 1
do 10 k=2, n
M(n) = M(n) - M(n/k)
10 continue
C Print table
write (*,"('The first 99 Mertens numbers are:')")
write (*,"(' ')",advance='no')
k = 9
do 20 n=1, 99
write (*,'(I3)',advance='no') M(n)
k = k-1
if (k .EQ. 0) then
k=10
write (*,*)
end if
20 continue
C Calculate zeroes and crossings
zero = 0
cross = 0
do 30 n=2, 1000
if (M(n) .EQ. 0) then
zero = zero + 1
if (M(n-1) .NE. 0) cross = cross+1
end if
30 continue
40 format("M(N) is zero ",I2," times.")
write (*,40) zero
50 format("M(N) crosses zero ",I2," times.")
write (*,50) cross
end program
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
FreeBASIC
function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function
dim as integer M( 1 to 1000 ), n, col, k, psum
dim as integer num_zeroes = 0, num_cross = 0
dim as string outstr
M(1) = 1
for n = 2 to 1000
psum = 0
for k = 2 to n
psum += M(int(n/k))
next k
M(n) = 1 - psum
if M(n) = 0 then
num_zeroes += 1
if M(n-1)<>0 then
num_cross += 1
end if
end if
next n
print using "There are ### zeroes in the range 1 to 1000."; num_zeroes
print using "There are ### crossings in the range 1 to 1000."; num_cross
print "The first 100 Mertens numbers are: "
for n=1 to 100
outstr += padto(3, M(n))+" "
if n mod 10 = 0 then
print outstr
outstr = ""
end if
next n
- Output:
There are 92 zeroes in the range 1 to 1000. There are 59 crossings in the range 1 to 1000. The first 100 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1
FutureBasic
void local fn MertensFunction
long mertens(1000), n, k, crossesTotal = 0, zerosTotal = 0
mertens(1) = 1
for n = 2 to 1000
mertens(n) = 1
for k = 2 to n
mertens(n) = mertens(n) - mertens(n/k)
next
next
printf @"First 99 Mertens numbers:\n \b"
for n = 1 to 99
printf @"%3ld \b", mertens(n)
if ( n mod 10 == 9 ) then print
next
for n = 1 to 1000
if ( mertens(n) == 0 )
zerosTotal++
if mertens(n-1) != 0 then crossesTotal++
end if
next
print
printf @"mertens(n) array is zero %ld times.", zerosTotal
printf @"mertens(n) array crosses zero %ld times.", crossesTotal
end fn
fn MertensFunction
HandleEvents
- Output:
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 mertens(n) array is zero 92 times. mertens(n) array crosses zero 59 times.
Go
package main
import "fmt"
func mertens(to int) ([]int, int, int) {
if to < 1 {
to = 1
}
merts := make([]int, to+1)
primes := []int{2}
var sum, zeros, crosses int
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 {
sum++
} else {
sum--
}
}
merts[i] = sum
if sum == 0 {
zeros++
if i > 1 && merts[i-1] != 0 {
crosses++
}
}
}
return merts, zeros, crosses
}
func main() {
merts, zeros, crosses := mertens(1000)
fmt.Println("Mertens 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", merts[i])
}
fmt.Println("\n\nEquals zero", zeros, "times between 1 and 1000")
fmt.Println("\nCrosses zero", crosses, "times between 1 and 1000")
}
- Output:
Mertens sequence - First 199 terms: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 Equals zero 92 times between 1 and 1000 Crosses zero 59 times between 1 and 1000
Haskell
import Data.List.Split (chunksOf)
import qualified Data.MemoCombinators as Memo
import Math.NumberTheory.Primes (unPrime, factorise)
import Text.Printf (printf)
moebius :: Integer -> Int
moebius = product . fmap m . factorise
where
m (p, e)
| unPrime p == 0 = 0
| e == 1 = -1
| otherwise = 0
mertens :: Integer -> Int
mertens = Memo.integral (\n -> sum $ fmap moebius [1..n])
countZeros :: [Integer] -> Int
countZeros = length . filter ((==0) . mertens)
crossesZero :: [Integer] -> Int
crossesZero = length . go . fmap mertens
where
go (x:y:xs)
| y == 0 && x /= 0 = y : go (y:xs)
| otherwise = go (y:xs)
go _ = []
main :: IO ()
main = do
printf "The first 99 terms for M(1..99):\n\n "
mapM_ (printf "%3d" . mertens) [1..9] >> printf "\n"
mapM_ (\row -> mapM_ (printf "%3d" . mertens) row >> printf "\n") $ chunksOf 10 [10..99]
printf "\nM(n) is zero %d times for 1 <= n <= 1000.\n" $ countZeros [1..1000]
printf "M(n) crosses zero %d times for 1 <= n <= 1000.\n" $ crossesZero [1..1000]
- Output:
The first 99 terms for M(1..99): 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(n) is zero 92 times for 1 <= n <= 1000. M(n) crosses zero 59 times for 1 <= n <= 1000.
J
mu =: 0:`(1 - 2 * 2|#@{.)@.(1: = */@{:)@(2&p:)"0
M =: +/@([: mu 1:+i.)
m1000 =: (M"0) 1+i.1000
zero =: +/ m1000 = 0
cross =: +/ (-.*.1:|]) m1000 ~: 0
echo 'The first 99 Merten numbers are'
echo 10 10$ __, 99{.m1000
echo 'M(N) is zero ',(":zero),' times.'
echo 'M(N) crosses zero ',(":cross),' times.'
exit''
- Output:
The first 99 Merten numbers are __ 1 0 _1 _1 _2 _1 _2 _2 _2 _1 _2 _2 _3 _2 _1 _1 _2 _2 _3 _3 _2 _1 _2 _2 _2 _1 _1 _1 _2 _3 _4 _4 _3 _2 _1 _1 _2 _1 0 0 _1 _2 _3 _3 _3 _2 _3 _3 _3 _3 _2 _2 _3 _3 _2 _2 _1 0 _1 _1 _2 _1 _1 _1 0 _1 _2 _2 _1 _2 _3 _3 _4 _3 _3 _3 _2 _3 _4 _4 _4 _3 _4 _4 _3 _2 _1 _1 _2 _2 _1 _1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 0 times.
Java
public class MertensFunction {
public static void main(String[] args) {
System.out.printf("First 199 terms of the merten function are as follows:%n ");
for ( int n = 1 ; n < 200 ; n++ ) {
System.out.printf("%2d ", mertenFunction(n));
if ( (n+1) % 20 == 0 ) {
System.out.printf("%n");
}
}
for ( int exponent = 3 ; exponent<= 8 ; exponent++ ) {
int zeroCount = 0;
int zeroCrossingCount = 0;
int positiveCount = 0;
int negativeCount = 0;
int mSum = 0;
int mMin = Integer.MAX_VALUE;
int mMinIndex = 0;
int mMax = Integer.MIN_VALUE;
int mMaxIndex = 0;
int nMax = (int) Math.pow(10, exponent);
for ( int n = 1 ; n <= nMax ; n++ ) {
int m = mertenFunction(n);
mSum += m;
if ( m < mMin ) {
mMin = m;
mMinIndex = n;
}
if ( m > mMax ) {
mMax = m;
mMaxIndex = n;
}
if ( m > 0 ) {
positiveCount++;
}
if ( m < 0 ) {
negativeCount++;
}
if ( m == 0 ) {
zeroCount++;
}
if ( m == 0 && mertenFunction(n - 1) != 0 ) {
zeroCrossingCount++;
}
}
System.out.printf("%nFor M(x) with x from 1 to %,d%n", nMax);
System.out.printf("The maximum of M(x) is M(%,d) = %,d.%n", mMaxIndex, mMax);
System.out.printf("The minimum of M(x) is M(%,d) = %,d.%n", mMinIndex, mMin);
System.out.printf("The sum of M(x) is %,d.%n", mSum);
System.out.printf("The count of positive M(x) is %,d, count of negative M(x) is %,d.%n", positiveCount, negativeCount);
System.out.printf("M(x) has %,d zeroes in the interval.%n", zeroCount);
System.out.printf("M(x) has %,d crossings in the interval.%n", zeroCrossingCount);
}
}
private static int MU_MAX = 100_000_000;
private static int[] MU = null;
private static int[] MERTEN = null;
// Compute mobius and merten function via sieve
private static int mertenFunction(int n) {
if ( MERTEN != null ) {
return MERTEN[n];
}
// Populate array
MU = new int[MU_MAX+1];
MERTEN = new int[MU_MAX+1];
MERTEN[1] = 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;
}
}
}
int sum = 1;
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;
}
sum += MU[i];
MERTEN[i] = sum;
}
return MERTEN[n];
}
}
- Output:
First 199 terms of the merten function are as follows: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 For M(x) with x from 1 to 1,000 The maximum of M(x) is M(586) = 7. The minimum of M(x) is M(665) = -12. The sum of M(x) is -1,572. The count of positive M(x) is 254, count of negative M(x) is 654. M(x) has 92 zeroes in the interval. M(x) has 59 crossings in the interval. For M(x) with x from 1 to 10,000 The maximum of M(x) is M(8,511) = 35. The minimum of M(x) is M(9,861) = -43. The sum of M(x) is -20,409. The count of positive M(x) is 3,965, count of negative M(x) is 5,629. M(x) has 406 zeroes in the interval. M(x) has 256 crossings in the interval. For M(x) with x from 1 to 100,000 The maximum of M(x) is M(48,433) = 96. The minimum of M(x) is M(96,014) = -132. The sum of M(x) is -516,879. The count of positive M(x) is 47,830, count of negative M(x) is 50,621. M(x) has 1,549 zeroes in the interval. M(x) has 949 crossings in the interval. For M(x) with x from 1 to 1,000,000 The maximum of M(x) is M(992,998) = 311. The minimum of M(x) is M(926,265) = -368. The sum of M(x) is -14,244,200. The count of positive M(x) is 472,963, count of negative M(x) is 521,676. M(x) has 5,361 zeroes in the interval. M(x) has 3,269 crossings in the interval. For M(x) with x from 1 to 10,000,000 The maximum of M(x) is M(9,993,034) = 1,143. The minimum of M(x) is M(7,109,110) = -1,078. The sum of M(x) is -194,680,528. The count of positive M(x) is 4,938,188, count of negative M(x) is 5,049,266. M(x) has 12,546 zeroes in the interval. M(x) has 7,646 crossings in the interval. For M(x) with x from 1 to 100,000,000 The maximum of M(x) is M(92,418,127) = 3,290. The minimum of M(x) is M(76,015,339) = -3,448. The sum of M(x) is -608,757,258. The count of positive M(x) is 54,659,906, count of negative M(x) is 45,298,186. M(x) has 41,908 zeroes in the interval. M(x) has 25,525 crossings in the interval.
jq
Adapted from C
Works with gojq, the Go implementation of jq
This entry will use the strategy exemplified in the entry for C and some others, that is, it will begin by defining a function that constructs an array of a specified number of Merten numbers, and use that function to solve the other tasks, which, however, will be solved independently for the sake of modularity and to illustrate efficient approaches to the problems considered separately. It would be trivial but uninteresting to merge the answers for efficiency.
Preliminaries
def sum(s): reduce s as $x (null; . + $x);
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# input: an array
# output: number of crossings at $value
def count_crossings($value):
. as $a
| reduce range(0; length) as $i ({};
if $a[$i] == $value
then if $i == 0 or .prev != $value then .count += 1 else . end
else .
end
| .prev = $a[$i] )
| .count;
Mertens Numbers
# Input: $max >= 1
# Output: an array of size $max with $max mertenNumbers beginning with 1
def mertensNumbers:
. as $max
| reduce range(2; $max + 1) as $n ( [1];
.[$n-1]=1
| reduce range(2; $n+1) as $k (.;
.[$n-1] -= .[($n / $k) | floor - 1] ));
The Tasks
# Task 0:
def mertens_number:
mertensNumbers[.-1];
def task1:
"The first \(.) Mertens numbers are:",
(mertensNumbers | nwise(10) | map(lpad(2)) | join(" ") );
def task2:
. as $n
| sum(mertensNumbers[] | select(.==0) | 1)
| "M(n) is zero \(.) times for 1 <= n <= \($n)\n";
def task3:
. as $n
| mertensNumbers
| count_crossings(0)
| "M(n) crosses zero \(.) times for 1 <= n <= \($n).\n" ;
(99|task1),
"",
(1000 | (task2, task3))
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(n) is zero 92 times for 1 <= n <= 1000 M(n) crosses zero 59 times for 1 <= n <= 1000.
Julia
The OEIS A002321 reference suggests the Mertens function has a negative bias, which it does below 1 million, but this bias seems to switch to a positive bias by 1 billion. There may simply be large swings in the bias overall, which get larger and longer as the sequence continues.
using Primes, Formatting
function moebius(n::Integer)
@assert n > 0
m(p, e) = p == 0 ? 0 : e == 1 ? -1 : 0
return reduce(*, m(p, e) for (p, e) in factor(n) if p ≥ 0; init=1)
end
μ(n) = moebius(n)
mertens(x) = sum(n -> μ(n), 1:x)
M(x) = mertens(x)
print("First 99 terms of the Mertens function for positive integers:\n ")
for n in 1:99
print(lpad(M(n), 3), n % 10 == 9 ? "\n" : "")
end
function maximinM(N)
z, cros, lastM, maxi, maxM, mini, minM, sumM, pos, neg = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
for i in 1:N
m = μ(i) + lastM
if m == 0 && lastM != 0
cros += 1
end
sumM += m
lastM = m
if m > maxM
maxi = i
maxM = m
elseif m < minM
mini = i
minM = m
end
if m > 0
pos += 1
elseif m < 0
neg += 1
else
z += 1
end
end
println("\nFor M(x) with x from 1 to $(format(N, commas=true)):")
println("The maximum of M(x) is M($(format(maxi, commas=true)) = $maxM.")
println("The minimum of M(x) is M($(format(mini, commas=true))) = $minM.")
println("The sum of M(x) is $(format(sumM, commas=true)).")
println("The count of positive M(x) is $(format(pos, commas=true)), count of negative M(x) is $(format(neg, commas=true)).")
println("M(x) has $(format(z, commas=true)) zeroes in the interval.")
println("M(x) has $(format(cros, commas=true)) crossings in the interval.")
diff = pos - neg
if diff > 0
println("Positive M(x) exceed negative ones by $(format(diff, commas=true)).")
else
println("Negative M(x) exceed positive ones by $(format(-diff, commas=true)).")
end
end
foreach(maximinM, (1000, 1_000_000, 1_000_000_000))
- Output:
First 99 terms of the Mertens function for positive integers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 For M(x) with x from 1 to 1,000: The maximum of M(x) is M(586 = 7. The minimum of M(x) is M(665) = -12. The sum of M(x) is -1,572. The count of positive M(x) is 254, count of negative M(x) is 654. M(x) has 92 zeroes in the interval. M(x) has 59 crossings in the interval. Negative M(x) exceed positive ones by 400. For M(x) with x from 1 to 1,000,000: The maximum of M(x) is M(992,998 = 311. The minimum of M(x) is M(926,265) = -368. The sum of M(x) is -14,244,200. The count of positive M(x) is 472,963, count of negative M(x) is 521,676. M(x) has 5,361 zeroes in the interval. M(x) has 3,269 crossings in the interval. Negative M(x) exceed positive ones by 48,713. For M(x) with x from 1 to 1,000,000,000: The maximum of M(x) is M(903,087,703 = 10246. The minimum of M(x) is M(456,877,618) = -8565. The sum of M(x) is 510,495,361,261. The count of positive M(x) is 510,200,302, count of negative M(x) is 489,658,577. M(x) has 141,121 zeroes in the interval. M(x) has 85,652 crossings in the interval. Positive M(x) exceed negative ones by 20,541,725.
MAD
NORMAL MODE IS INTEGER
DIMENSION M(1000)
M(1) = 1
THROUGH GENMRT, FOR N=2, 1, N.G.1000
M(N) = 1
THROUGH GENMRT, FOR K=2, 1, K.G.N
GENMRT M(N) = M(N) - M(N/K)
PRINT COMMENT $ FIRST 99 MERTEN NUMBERS ARE$
VECTOR VALUES F9 = $S3,9(I2,S1)*$
VECTOR VALUES F10 = $10(I2,S1)*$
PRINT FORMAT F9, M(1), M(2), M(3), M(4), M(5), M(6),
0 M(7), M(8), M(9)
THROUGH SHOW, FOR N=10, 10, N.GE.100
SHOW PRINT FORMAT F10, M(N), M(N+1), M(N+2), M(N+3), M(N+4),
0 M(N+5), M(N+6), M(N+7), M(N+8), M(N+9), M(N+10)
ZERO = 0
CROSS = 0
THROUGH ZC, FOR N=1, 1, N.G.1000
WHENEVER M(N).E.0, ZERO = ZERO + 1
ZC WHENEVER M(N).E.0 .AND. M(N-1).NE.0, CROSS = CROSS + 1
VECTOR VALUES FZ = $13HM(N) IS ZERO ,I2,S1,5HTIMES*$
PRINT FORMAT FZ, ZERO
VECTOR VALUES FC = $18HM(N) CROSSES ZERO ,I2,S1,5HTIMES*$
PRINT FORMAT FC, CROSS
END OF PROGRAM
- Output:
FIRST 99 MERTEN NUMBERS ARE 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) IS ZERO 92 TIMES M(N) CROSSES ZERO 59 TIMES
Mathematica/Wolfram Language
ClearAll[Mertens]
Mertens[n_] := Total[MoebiusMu[Range[n]]]
Grid[Partition[Mertens /@ Range[99], UpTo[10]]]
Count[Mertens /@ Range[1000], 0]
SequenceCount[Mertens /@ Range[1000], {Except[0], 0}]
- Output:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 92 59
Modula-2
MODULE Mertens;
FROM InOut IMPORT WriteString, WriteInt, WriteCard, WriteLn;
CONST Max = 1000;
VAR n, k, x, y, zero, cross: CARDINAL;
M: ARRAY [1..Max] OF INTEGER;
BEGIN
M[1] := 1;
FOR n := 2 TO Max DO
M[n] := 1;
FOR k := 2 TO n DO
M[n] := M[n] - M[n DIV k];
END;
END;
WriteString("The first 99 Mertens numbers are:");
WriteLn();
FOR y := 0 TO 90 BY 10 DO
FOR x := 0 TO 9 DO
IF x+y=0 THEN WriteString(" ");
ELSE WriteInt(M[x+y], 3);
END;
END;
WriteLn();
END;
zero := 0;
cross := 0;
FOR n := 2 TO Max DO
IF M[n] = 0 THEN
zero := zero + 1;
IF M[n-1] # 0 THEN
cross := cross + 1;
END;
END;
END;
WriteString("M(n) is zero ");
WriteCard(zero,0);
WriteString(" times.");
WriteLn();
WriteString("M(n) crosses zero ");
WriteCard(cross,0);
WriteString(" times.");
WriteLn();
END Mertens.
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(n) is zero 92 times. M(n) crosses zero 59 times.
Nim
import sequtils, strformat
func mertensNumbers(max: int): seq[int] =
result = repeat(1, max + 1)
for n in 2..max:
for k in 2..n:
dec result[n], result[n div k]
const Max = 1000
let mertens = mertensNumbers(Max)
echo "First 199 Mertens numbers:"
const Count = 200
var column = 0
for i in 0..<Count:
if column > 0: stdout.write ' '
stdout.write if i == 0: " " else: &"{mertens[i]:>2}"
inc column
if column == 20:
stdout.write '\n'
column = 0
var zero, cross, previous = 0
for i in 1..Max:
let m = mertens[i]
if m == 0:
inc zero
if previous != 0:
inc cross
previous = m
echo ""
echo &"M(n) is zero {zero} times for 1 ⩽ n ⩽ {Max}."
echo &"M(n) crosses zero {cross} times for 1 ⩽ n ⩽ {Max}."
- Output:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 M(n) is zero 92 times for 1 ⩽ n ⩽ 1000. M(n) crosses zero 59 times for 1 ⩽ n ⩽ 1000.
Pascal
Nearly the same as Square-free_integers#Pascal
Instead here marking all multiples, starting at factor 2, of a prime by incrementing the factor count.
runtime ~log(n)*n
program Merten;
{$IFDEF FPC}
{$MODE DELPHI}
{$Optimization ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
const
BigLimit = 10*1000*1000*1000;//1e10
type
tSieveElement = Int8;
tpSieve = pInt8;
tMoebVal = array[-1..1] of Int64;
var
MertensValues : array[-40000..50500] of NativeInt;
primes : array of byte;
sieve : array of tSieveElement;
procedure CompactPrimes;
//searching for needed primes
//last primes are marked with -1
var
pSieve : tpSieve;
i,lmt,dp:NativeInt;
Begin
setlength(Primes,74500);//suffices for primes to calc square upto 1e12
//extract difference of primes
i := 2;
lmt := 0;
dp := 2;
pSieve :=@sieve[0];
repeat
IF pSieve[i]= 0 then
Begin
//mark for Moebius
pSieve[i]:= -1;
primes[lmt] := dp;
dp := 0;
inc(lmt);
end;
inc(dp);
inc(i);
until i*i >BigLimit;
setlength(Primes,lmt+1);
repeat
IF pSieve[i]= 0 then
//mark for Moebius
pSieve[i]:= -1;
inc(i);
until i >BigLimit;
end;
procedure SieveSquares;
//mark all powers >=2 of prime => all powers = 2 is sufficient
var
pSieve : tpSieve;
i,sq,k,prime : NativeInt;
Begin
pSieve := @sieve[0];
prime := 0;
For i := 0 to High(primes) do
Begin
prime := prime+primes[i];
sq := prime*prime;
k := sq;
if sq > BigLimit then
break;
repeat
pSieve[k] := 0;
inc(k,sq);
until k> BigLimit;
end;
end;
procedure initPrimes;
var
pSieve : tpSieve;
fakt,
sieveprime : NativeUint;
begin
pSieve := @sieve[0];
sieveprime := 2;
repeat
if pSieve[sieveprime]=0 then
begin
fakt := sieveprime+sieveprime;
while fakt <=BigLimit do
Begin
//count divisors
inc(pSieve[fakt]);
inc(fakt,sieveprime);
end;
end;
inc(sieveprime);
until sieveprime>BigLimit DIV 2;
//Möbius of 1
pSieve[1] := 1;
//convert to Moebius
For fakt := 2 to BigLimit do
Begin
sieveprime := pSieve[fakt];
IF sieveprime<>0 then
pSieve[fakt] := 1-(2*(sieveprime AND 1)) ;
end;
CompactPrimes;
SieveSquares;
end;
procedure OutMerten10(Lmt,ZeroCross:NativeInt;Const MoebVal:tMoebVal);
var
i,j: NativeInt;
Begin
Writeln(lmt:11,MoebVal[-1]:11,MoebVal[1]:11,MoebVal[-1]+MoebVal[1]:11,
MoebVal[-1]-MoebVal[1]:7,MoebVal[0]:11);
i:= low(MertensValues);
while MertensValues[i] = 0 do
inc(i);
j:= High(MertensValues);
while MertensValues[j] = 0 do
dec(j);
write('Merten min ',i:6,' max ',j:6,' zero''s ',MertensValues[0]:8);
writeln(' zeroCross ',ZeroCross);
writeln;
end;
procedure Count_x10;
var
MoebCount: tMoebVal;
pSieve : tpSieve;
i,lmt,Merten,Moebius,LastMert,ZeroCross: NativeInt;
begin
writeln('[1 to limit]');
Writeln('Limit Moeb. odd Moeb.even sqr-free Merten Zero''s');
pSieve := @sieve[0];
For i := -1 to 1 do
MoebCount[i]:=0;
ZeroCross := 0;
LastMert :=1;
Merten :=0;
lmt := 10;
i := 1;
repeat
while i <= lmt do
Begin
Moebius := pSieve[i];
inc(MoebCount[Moebius]);
inc(Merten,Moebius);
inc(MertensValues[Merten]);//MoebCount[1]-MoebCount[-1]]);
inc(ZeroCross,ORD( (Merten = 0) AND (LastMert <> 0)));
LastMert := Merten;
inc(i);
end;
OutMerten10(Lmt,ZeroCross,MoebCount);
IF lmt >= BigLimit then
BREAK;
lmt := lmt*10;
IF lmt >BigLimit then
lmt := BigLimit;
until false;
writeln;
end;
procedure OutMerten(lmt:NativeInt);
var
i,k,m : NativeInt;
Begin
iF lmt> BigLimit then
lmt := BigLimit;
writeln('Mertens numbers from 1 to ',lmt);
k := 9;
write('':3);
m := 0;
For i := 1 to lmt do
Begin
inc(m,sieve[i]);
write(m:3);
dec(k);
IF k = 0 then
Begin
writeln;
k := 10;
end;
end;
writeln;
end;
procedure OutMoebius(lmt:NativeInt);
var
i,k : NativeInt;
Begin
iF lmt> BigLimit then
lmt := BigLimit;
writeln('Möbius numbers from 1 to ',lmt);
k := 19;
write('':3);
For i := 1 to lmt do
Begin
write(sieve[i]:3);
dec(k);
IF k = 0 then
Begin
writeln;
k := 20;
end;
end;
writeln;
end;
Begin
setlength(sieve,BigLimit+1);
InitPrimes;
SieveSquares;
Count_x10;
OutMoebius(199);
OutMerten(99);
setlength(primes,0);
setlength(sieve,0);
end.
- Output:
[1 to limit] Limit Moeb. odd Moeb.even sqr-free Merten Zero's 10 4 3 7 1 3 Merten min -2 max 1 zero's 1 zeroCross 1 100 30 31 61 -1 39 Merten min -4 max 2 zero's 6 zeroCross 5 1000 303 305 608 -2 392 Merten min -12 max 7 zero's 92 zeroCross 59 10000 3053 3030 6083 23 3917 Merten min -43 max 35 zero's 406 zeroCross 256 100000 30421 30373 60794 48 39206 Merten min -132 max 96 zero's 1549 zeroCross 949 1000000 303857 304069 607926 -212 392074 Merten min -368 max 311 zero's 5361 zeroCross 3269 10000000 3039127 3040164 6079291 -1037 3920709 Merten min -1078 max 1143 zero's 12546 zeroCross 7646 100000000 30395383 30397311 60792694 -1928 39207306 Merten min -3448 max 3290 zero's 41908 zeroCross 25525 1000000000 303963673 303963451 607927124 222 392072876 Merten min -8565 max 10246 zero's 141121 zeroCross 85652 10000000000 3039652332 3039618610 6079270942 33722 3920729058 Merten min -35517 max 50286 zero's 431822 zeroCross 262605 Möbius numbers from 1 to 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 Mertens numbers from 1 to 99 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 real 3m54,249s = 234s //BigLimit = 100*1000*1000;takes 2.017s
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
}
sub progressive_sum {
my @sum = shift @_;
push @sum, $sum[-1] + $_ for @_;
@sum
}
my($upto, $show, @möebius) = (1000, 199, ());
push @möebius, μ($_) for 1..$upto;
my @mertens = progressive_sum @möebius;
say "Mertens sequence - First $show terms:\n" .
(' 'x4 . sprintf "@{['%4d' x $show]}", @mertens[0..$show-1]) =~ s/((.){80})/$1\n/gr .
sprintf("\nEquals zero %3d times between 1 and $upto", scalar grep { ! $_ } @mertens) .
sprintf "\nCrosses zero%3d times between 1 and $upto", scalar grep { ! $mertens[$_-1] and $mertens[$_] } 1 .. @mertens;
- Output:
Mertens sequence - First 199 terms: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 Equals zero 92 times between 1 and 1000 Crosses zero 59 times between 1 and 1000
Phix
with javascript_semantics requires("1.0.2") -- (skip arg added to join_by) sequence mcache = {1} function Mertens(integer n) for m=length(mcache)+1 to n do integer mm = 1 for k=2 to m do mm -= mcache[floor(m/k)] end for mcache &= mm end for return mcache[n] end function constant first = 99, perline = 10 --constant first = 199, perline = 20 -- matches C/Go/etc --constant first = 143, perline = 12 -- matches wp sequence s = {" ."}&apply(tagset(first),Mertens) printf(1,"First %d Mertens numbers:\n",first) puts(1,join_by(s,1,perline," ",fmt:="%3d",skip:=1)) integer prev = 1, zeroes = 0, crosses = 0 for n=2 to 1000 do integer m = Mertens(n) if m=0 then zeroes += 1 crosses += prev!=0 end if prev = m end for printf(1,"\nMertens[1..1000] equals zero %d times and crosses zero %d times\n",{zeroes,crosses})
- Output:
First 99 Mertens numbers: . 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 Mertens[1..1000] equals zero 92 times and crosses zero 59 times
PL/I
mertens: procedure options(main);
%replace MAX by 1000;
declare M(1:MAX) fixed binary(5);
declare (n, k) fixed binary(10);
declare (isZero, crossZero) fixed binary(8);
M(1) = 1;
do n = 2 to MAX;
M(n) = 1;
do k = 2 to n;
M(n) = M(n) - M(divide(n,k,10));
end;
end;
put skip list('The first 99 Mertens numbers are:');
put skip list(' ');
do n = 1 to 99;
put edit(M(n)) (F(3));
if mod(n,10) = 9 then put skip;
end;
isZero = 0;
crossZero = 0;
do n = 2 to MAX;
if M(n) = 0 then do;
isZero = isZero + 1;
if M(n-1) ^= 0 then
crossZero = crossZero + 1;
end;
end;
put skip list('Zeroes: ',isZero);
put skip list('Crossings:',crossZero);
end mertens;
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 Zeroes: 92 Crossings: 59
Prolog
:- dynamic mertens_number_cache/2.
mertens_number(1, 1):- !.
mertens_number(N, M):-
mertens_number_cache(N, M),
!.
mertens_number(N, M):-
N >= 2,
mertens_number(N, 2, M, 0),
assertz(mertens_number_cache(N, M)).
mertens_number(N, N, M, M):- !.
mertens_number(N, K, M, S):-
N1 is N // K,
mertens_number(N1, M1),
K1 is K + 1,
S1 is S - M1,
mertens_number(N, K1, M, S1).
print_mertens_numbers(Count):-
print_mertens_numbers(Count, 0).
print_mertens_numbers(Count, Count):-!.
print_mertens_numbers(Count, N):-
(N == 0 ->
write(' ')
;
mertens_number(N, M),
writef('%3r', [M])
),
N1 is N + 1,
Column is N1 mod 20,
(N > 0, Column == 0 ->
nl
;
true
),
print_mertens_numbers(Count, N1).
count_zeros(From, To, Z, C):-
count_zeros(From, To, Z, C, 0, 0, 0).
count_zeros(From, To, Z, C, Z, C, _):-
From > To,
!.
count_zeros(From, To, Z, C, Z1, C1, P):-
mertens_number(From, M),
(M == 0 -> Z2 is Z1 + 1 ; Z2 = Z1),
(M == 0, P \= 0 -> C2 is C1 + 1 ; C2 = C1),
Next is From + 1,
count_zeros(Next, To, Z, C, Z2, C2, M).
main:-
writeln('First 199 Mertens numbers:'),
print_mertens_numbers(200),
count_zeros(1, 1000, Z, C),
writef('M(n) is zero %t times for 1 <= n <= 1000.\n', [Z]),
writef('M(n) crosses zero %t times for 1 <= n <= 1000.\n', [C]).
- Output:
First 199 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 M(n) is zero 92 times for 1 <= n <= 1000. M(n) crosses zero 59 times for 1 <= n <= 1000.
PureBasic
Dim M.i(1000)
M(1)=1
For n=2 To 1000
psum=0
For k=2 To n : psum+M(Int(n/k)) : Next : M(n)=1-psum
If M(n)=0 : z+1 : If M(n-1)<>0 : c+1 : EndIf : EndIf
Next
OpenConsole("")
PrintN("First 99 Mertens numbers:") : Print(Space(4))
For n=1 To 99 : Print(RSet(Str(M(n)),4)) : If n%10=9 : PrintN("") : EndIf : Next
PrintN("M(N) is zero "+Str(z)+" times.") : PrintN("M(N) crosses zero "+Str(c)+" times.")
Input()
- Output:
First 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
Python
def mertens(count):
"""Generate Mertens numbers"""
m = [None, 1]
for n in range(2, count+1):
m.append(1)
for k in range(2, n+1):
m[n] -= m[n//k]
return m
ms = mertens(1000)
print("The first 99 Mertens numbers are:")
print(" ", end=' ')
col = 1
for n in ms[1:100]:
print("{:2d}".format(n), end=' ')
col += 1
if col == 10:
print()
col = 0
zeroes = sum(x==0 for x in ms)
crosses = sum(a!=0 and b==0 for a,b in zip(ms, ms[1:]))
print("M(N) equals zero {} times.".format(zeroes))
print("M(N) crosses zero {} times.".format(crosses))
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) equals zero 92 times. M(N) crosses zero 59 times.
Quackery
mobius
is defined at Möbius function#Quackery.
[ ' [ 0 ]
swap 1+ times
[ dup -1 peek
i^ 1+ mobius
+ join ]
behead drop ] is mertens ( n --> [ )
[ say " "
99 times
[ dup i^ peek
dup dup
-1 > if sp
abs 10 < if sp
echo
i^ 1+ 10 mod
9 = if cr ]
drop ] is grid ( [ --> )
[ 0 swap
witheach
[ 0 = + ] ] is zeroes ( [ --> n )
[ 0 0
rot witheach
[ dup 0 =
rot 0 !=
and
rot + swap ]
drop ] is crossings ( [ --> n )
1000 mertens
say "First 99 terms:"
cr
dup grid
cr
dup zeroes echo say " zeroes and "
crossings echo say " crossings"
- Output:
First 99 terms: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 92 zeroes and 59 crossings
Raku
(formerly Perl 6)
Mertens number is not defined for n == 0. Raku arrays are indexed from 0 so store a blank value at position zero to keep x and M(x) 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 @mertens = lazy [\+] flat '', 1, (2..*).hyper.map: -> \n { μ(n) };
put "Mertens sequence - First 199 terms:\n",
@mertens[^200]».fmt('%3s').batch(20).join("\n"),
"\n\nEquals zero ", +@mertens[1..1000].grep( !* ),
' times between 1 and 1000', "\n\nCrosses zero ",
+@mertens[1..1000].kv.grep( {!$^v and @mertens[$^k]} ),
" times between 1 and 1000\n\nFirst Mertens equal to:";
for 10, 20, 30 … 100 -> $threshold {
printf "%4d: M(%d)\n", -$threshold, @mertens.first: * == -$threshold, :k;
printf "%4d: M(%d)\n", $threshold, @mertens.first: * == $threshold, :k;
}
- Output:
Mertens sequence - First 199 terms: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 Equals zero 92 times between 1 and 1000 Crosses zero 59 times between 1 and 1000 First Mertens equal to: -10: M(659) 10: M(1393) -20: M(2791) 20: M(3277) -30: M(9717) 30: M(8503) -40: M(9831) 40: M(11770) -50: M(24018) 50: M(19119) -60: M(24105) 60: M(31841) -70: M(24170) 70: M(31962) -80: M(42789) 80: M(48202) -90: M(59026) 90: M(48405) -100: M(59426) 100: M(114717)
REXX
The Mertens function is named after Franz Mertens.
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 and/or Mertens value of for zero (which can be changed easily).
The above "feature" was added to make the grid to be aligned with other solutions.
/*REXX pgm computes & shows a value grid of the Mertens function for a range of integers*/
parse arg LO HI grp eqZ xZ . /*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 /* " " " " " " */
if eqZ=='' | eqZ=="," then eqZ= 1000 /* " " " " " " */
if xZ=='' | xZ=="," then xZ= 1000 /* " " " " " " */
call genP /*generate primes up to max √ HIHI */
call Franz LO, HI
if eqZ>0 then call Franz 1, -eqZ
if xZ>0 then call Franz -1, xZ
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Franz: parse arg a 1 oa,b 1 ob; @Mertens= ' The Mertens sequence from '
a= abs(a); b= abs(b); grid= oa>=0 & ob>=0 /*semaphore used to show a grid title. */
if grid then say center(@Mertens LO " ──► " HI" ", max(50, grp*3), '═') /*show title*/
else say
zeros= 0 /*# of 0's found for Mertens function.*/
Xzero= 0 /*number of times that zero was crossed*/
$=; prev= /*$ holds output grid of GRP numbers. */
do j=a to b; _= Mertens(j) /*process some numbers from LO ──► HI.*/
if _==0 then zeros= zeros + 1 /*Is Zero? Then bump the zeros counter*/
if _==0 then if prev\==0 then Xzero= Xzero+1 /*prev ¬=0? " " " Xzero " */
prev= _
if grid then $= $ right(_, 2) /*build grid if A & B are non─negative.*/
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*/
if oa<0 then say @Mertens a " to " b ' has crossed zero ' Xzero " times."
if ob<0 then say @Mertens a " to " b ' has ' zeros " zeros."
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Mertens: procedure expose @. !!. M.; parse arg n; if M.n\==. then return M.n
if n<1 then return '∙'; m= 0 /*handle special cases of non─positive#*/
do k=1 for n; m= m + mobius(k) /*sum the MU's up to N. */
end /*k*/ /* [↑] mobius function uses memoization*/
M.n= m; return m /*return the sum of all the MU's. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
mobius: procedure expose @. !!.; parse arg x 1 ox /*get integer to be tested for mu */
if !!.x\==. then return !!.x /*X computed before? Return that value*/
if x<1 then return '∙'; mu= 0 /*handle special case of non-positive #*/
do k=1; p= @.k; if p>x then leave /* (P) > X? Then we're done.*/
if p*p>x then do; mu= mu+1; leave; end /* (P**2) > X? Bump # and leave*/
if x//p==0 then do; mu= mu+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*/ /*MU (below) is almost always small, <9*/
!!.ox= -1 ** mu; return !!.ox /*raise -1 to the mu power, memoize it.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13 /*initialize some low primes; # primes.*/
!!.=.; M.=!!.; #= 6; sq.#= @.6**2 /* " 2 arrays for memoization. */
do j=@.#+4 by 2 to max(HI, eqZ, xZ); parse var j '' -1 _ /*odd Ps from now on*/
if _==5 then iterate; if j//3==0 then iterate; if j//7==0 then iterate /*÷ 5 3 7*/
do k=7 while sq.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. */
#= #+1; @.#=j; sq.j= j*j /*bump P count; P──►@.; compute J**2*/
end /*j*/; return /*calculate the squares of some primes.*/
- 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 Mertens sequence from 0 ──► 199 ══════════ ∙ 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 The Mertens sequence from 1 to 1000 has 92 zeros. The Mertens sequence from 1 to 1000 has crossed zero 59 times.
Ruby
require 'prime'
def μ(n)
return 1 if self == 1
pd = n.prime_division
return 0 unless pd.map(&:last).all?(1)
pd.size.even? ? 1 : -1
end
def M(n)
(1..n).sum{|n| μ(n)}
end
([" "] + (1..199).map{|n|"%2s" % M(n)}).each_slice(20){|line| puts line.join(" ") }
ar = (1..1000).map{|n| M(n)}
puts "\nThe Mertens function is zero #{ar.count(0)} times in the range (1..1000);"
puts "it crosses zero #{ar.each_cons(2).count{|m1, m2| m1 != 0 && m2 == 0}} times."
- Output:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 The Mertens function is zero 92 times in the range (1..1000); it crosses zero 59 times.
SETL
program mertens;
m := [1] * 1000;
loop for n in [1..#m] do
m(n) -:= 0 +/[m(n div k) : k in [2..n]];
end loop;
print("The first 99 Mertens numbers:");
putchar(" ");
loop for n in [1..99] do
putchar(lpad(str m(n), 3));
if n mod 10=9 then print; end if;
end loop;
zero := #[n : n in [1..#m] | m(n) = 0];
cross := #[n : n in [1..#m] | m(n) = 0 and m(n-1) /= 0];
print("M(N) is zero " + str zero + " times.");
print("M(N) crosses zero " + str cross + " times.");
end program;
- Output:
The first 99 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
Sidef
Built-in:
say mertens(123456789) #=> 1170
say mertens(1234567890) #=> 9163
Algorithm for computing M(n) in sublinear time:
func mertens(n) is cached {
var lookup_size = (2 * n.iroot(3)**2)
var mertens_lookup = [0]
for k in (1..lookup_size) {
mertens_lookup[k] = (mertens_lookup[k-1] + k.moebius)
}
static cache = Hash()
func (n) {
if (n <= lookup_size) {
return mertens_lookup[n]
}
if (cache.has(n)) {
return cache{n}
}
var M = 1
var s = n.isqrt
for k in (2 .. floor(n/(s+1))) {
M -= __FUNC__(floor(n/k))
}
for k in (1..s) {
M -= (mertens_lookup[k] * (floor(n/k) - floor(n/(k+1))))
}
cache{n} = M
}(n)
}
Task:
with (200) {|n|
say "Mertens function in the range 1..#{n}:"
(1..n).map { mertens(_) }.slices(20).each {|line|
say line.map{ "%2s" % _ }.join(' ')
}
}
with (1000) {|n|
say "\nIn the range 1..#{n}, there are:"
say (1..n->count_by { mertens(_)==0 }, " zeros")
say (1..n->count_by { mertens(_)==0 && mertens(_-1)!=0 }, " zero crossings")
}
- Output:
Mertens function in the range 1..200: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 -8 In the range 1..1000, there are: 92 zeros 59 zero crossings
Swift
import Foundation
func mertensNumbers(max: Int) -> [Int] {
var mertens = Array(repeating: 1, count: max + 1)
for n in 2...max {
for k in 2...n {
mertens[n] -= mertens[n / k]
}
}
return mertens
}
let max = 1000
let mertens = mertensNumbers(max: max)
let count = 200
let columns = 20
print("First \(count - 1) Mertens numbers:")
for i in 0..<count {
if i % columns > 0 {
print(" ", terminator: "")
}
print(i == 0 ? " " : String(format: "%2d", mertens[i]), terminator: "")
if (i + 1) % columns == 0 {
print()
}
}
var zero = 0, cross = 0, previous = 0
for i in 1...max {
let m = mertens[i]
if m == 0 {
zero += 1
if previous != 0 {
cross += 1
}
}
previous = m
}
print("M(n) is zero \(zero) times for 1 <= n <= \(max).")
print("M(n) crosses zero \(cross) times for 1 <= n <= \(max).")
- Output:
First 199 Mertens numbers: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 M(n) is zero 92 times for 1 <= n <= 1000. M(n) crosses zero 59 times for 1 <= n <= 1000.
V (Vlang)
fn mertens(t int) ([]int, int, int) {
mut to:=t
if to < 1 {
to = 1
}
mut merts := []int{len:to+1}
mut primes := [2]
mut sum := 0
mut zeros := 0
mut crosses := 0
for i := 1; i <= to; i++ {
mut j := i
mut cp := 0 // counts prime factors
mut spf := false // true if there is a square prime factor
for p in 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 << i
}
if !spf {
if cp%2 == 0 {
sum++
} else {
sum--
}
}
merts[i] = sum
if sum == 0 {
zeros++
if i > 1 && merts[i-1] != 0 {
crosses++
}
}
}
return merts, zeros, crosses
}
fn main() {
merts, zeros, crosses := mertens(1000)
println("Mertens sequence - First 199 terms:")
for i := 0; i < 200; i++ {
if i == 0 {
print(" ")
continue
}
if i%20 == 0 {
println('')
}
print(" ${merts[i]:2}")
}
println("\n\nEquals zero $zeros times between 1 and 1000")
println("\nCrosses zero $crosses times between 1 and 1000")
}
- Output:
Mertens sequence - First 199 terms: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 Equals zero 92 times between 1 and 1000 Crosses zero 59 times between 1 and 1000
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
}
var M = Fn.new { |x| (1..x).reduce { |sum, n| sum + mu.call(n) } }
System.print("The first 199 Mertens 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, M.call(i*20 + j))) ")
}
}
System.print()
}
// use the recurrence relationship for the last 2 parts rather than calling M directly
var count = 0
var mertens = M.call(1)
for (i in 2..1000) {
mertens = mertens + mu.call(i)
if (mertens == 0) count = count + 1
}
System.print("\nThe Mertens function is zero %(count) times in the range [1, 1000].")
count = 0
var prev = M.call(1)
for (i in 2..1000) {
var next = prev + mu.call(i)
if (next == 0 && prev != 0) count = count + 1
prev = next
}
System.print("\nThe Mertens function crosses zero %(count) times in the range [1, 1000].")
- Output:
The first 199 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 The Mertens function is zero 92 times in the range [1, 1000]. The Mertens function crosses zero 59 times in the range [1, 1000].
XPL0
integer M ( 1+1000 );
integer K, Zero, Cross, N;
begin \compute values of the Mertens function
\Generate Mertens numbers
M( 1 ) := 1;
for N := 2 to 1000 do begin
M( N ) := 1;
for K := 2 to N do M( N ) := M( N ) - M( N / K )
end;
\Print table
Text(0, "The first 99 Mertens numbers are:^m^j");
Text(0, " " );
K := 9;
for N := 1 to 99 do begin
Format(3, 0);
RlOut(0, float(M(N)));
K := K - 1;
if K = 0 then begin
K := 10;
CrLf(0);
end
end;
\Calculate zeroes and crossings
Zero := 0;
Cross := 0;
for N :=2 to 1000 do begin
if M( N ) = 0 then begin
Zero := Zero + 1;
if M( N - 1 ) # 0 then Cross := Cross + 1
end
end;
Text(0, "M(N) is zero "); IntOut(0, Zero); Text(0, " times.^m^j" );
Text(0, "M(N) crosses zero "); IntOut(0, Cross); Text(0, " times.^m^j" );
end
- Output:
The first 99 Mertens numbers are: 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 M(N) is zero 92 times. M(N) crosses zero 59 times.
zkl
fcn mertensW(n){
[1..].tweak(fcn(n,pm){
pm.incN(mobius(n));
pm.value
}.fp1(Ref(0)))
}
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;
}
mertensW().walk(199)
.pump(Console.println, T(Void.Read,19,False),
fcn{ vm.arglist.pump(String,"%3d".fmt) });
println("\nIn the first 1,000 terms of the Mertens sequence there are:");
otm:=mertensW().pump(1_000,List);
otm.reduce(fcn(s,m){ s + (m==0) },0) : println(_," zeros");
otm.reduce(fcn(p,m,rs){ rs.incN(m==0 and p!=0); m }.fp2( s:=Ref(0) ));
println(s.value," zero crossings");
- Output:
1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3 -3 -2 -1 -2 -2 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 -2 -1 0 0 -1 -2 -3 -3 -3 -2 -3 -3 -3 -3 -2 -2 -3 -3 -2 -2 -1 0 -1 -1 -2 -1 -1 -1 0 -1 -2 -2 -1 -2 -3 -3 -4 -3 -3 -3 -2 -3 -4 -4 -4 -3 -4 -4 -3 -2 -1 -1 -2 -2 -1 -1 0 1 2 2 1 1 1 1 0 -1 -2 -2 -3 -2 -3 -3 -4 -5 -4 -4 -5 -6 -5 -5 -5 -4 -3 -3 -3 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -1 -1 -1 -2 -3 -4 -4 -3 -2 -1 -1 0 1 1 1 0 0 -1 -1 -1 -2 -1 -1 -2 -1 0 0 1 1 0 0 -1 0 -1 -1 -1 -2 -2 -2 -3 -4 -4 -4 -3 -2 -3 -3 -4 -5 -4 -4 -3 -4 -3 -3 -3 -4 -5 -5 -6 -5 -6 -6 -7 -7 -8 In the first 1,000 terms of the Mertens sequence there are: 92 zeros 59 zero crossings
- Programming Tasks
- Prime Numbers
- 11l
- 360 Assembly
- 8080 Assembly
- 8086 Assembly
- Action!
- Action! Tool Kit
- ALGOL 68
- ALGOL W
- APL
- Arturo
- AutoHotkey
- BASIC
- BASIC256
- Run BASIC
- True BASIC
- XBasic
- Yabasic
- Bash
- BCPL
- C
- C++
- CLU
- COBOL
- Cowgol
- Delphi
- System.SysUtils
- Draco
- Dyalect
- EasyLang
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- FutureBasic
- Go
- Haskell
- J
- Java
- Jq
- Julia
- MAD
- Mathematica
- Wolfram Language
- Modula-2
- Nim
- Pascal
- Perl
- Phix
- PL/I
- Prolog
- PureBasic
- Python
- Quackery
- Raku
- REXX
- Ruby
- SETL
- Sidef
- Swift
- V (Vlang)
- Wren
- Wren-fmt
- Wren-math
- XPL0
- Zkl