Mertens function: Difference between revisions

:* [[Möbius function]]

<br><br>

 

=={{header|8080 Assembly}}==

org 100h

;;; Generate Mertens numbers

tms: db ' times.$'

;;; Numbers are stored page-aligned after program

 

{{out}}

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

section .bss

mm: resb MAX ; Mertens numbers

 

{{out}}

M(N) is zero 92 times.

M(N) crosses zero 59 times.</pre>

 

=={{header|ALGOL W}}==

{{Trans|Fortran}}

integer array M ( 1 :: 1000 );

integer k, zero, cross;

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." )

{{out}}

<pre>

=={{header|APL}}==

{{works with|Dyalog APL}}

step ← {⍵,-⍨/⌽1,⍵[⌊n÷1↓⍳n←1+≢⍵]}

m1000 ← step⍣999⊢,1

⎕←'M(N) is zero ',(⍕zero),' times.'

⎕←'M(N) crosses zero ',(⍕cross),' times.'

 

{{out}}

M(N) is zero 92 times.

M(N) crosses zero 59 times.</pre>

 

=={{header|BASIC}}==

a little over 1 hour on the 8086 (using GWBASIC).

 

20 M(1)=1

30 FOR N=2 TO 1000

170 PRINT "M(N) is zero";Z;"times."

180 PRINT "M(N) crosses zero";C;"times."

 

{{out}}

M(N) crosses zero 59 times.</pre>

 

MAX=1000

 

 

echo "M(N) is zero $zero times."

 

{{out}}

 

=={{header|BCPL}}==

 

manifest $( limit = 1000 $)

writef("M(N) is zero %N times.*N", eqz)

writef("M(N) crosses zero %N times.*N", crossz)

{{out}}

<pre>The first 99 Mertens numbers are:

 

=={{header|C}}==

#include <stdlib.h>

 

printf("M(n) crosses zero %d times for 1 <= n <= %d.\n", cross, max);

return 0;

 

{{out}}

 

=={{header|C++}}==

#include <iostream>

#include <vector>

std::cout << "M(n) crosses zero " << cross << " times for 1 <= n <= 1000.\n";

return 0;

 

{{out}}

M(n) crosses zero 59 times for 1 <= n <= 1000.

</pre>

 

=={{header|COBOL}}==

PROGRAM-ID. MERTENS.

 

SUBTRACT 1 FROM N GIVING K,

IF M(K) IS NOT EQUAL TO ZERO,

{{out}}

<pre>The first 99 Mertens numbers are:

 

=={{header|Cowgol}}==

 

const MAX := 1000;

 

print("M(n) is zero "); print_i8(zero); print(" times\n");

 

{{out}}

{{libheader| System.SysUtils}}

{{Trans|Go}}

program Mertens_function;

 

writeln(#10'Crosses zero ', m.crosses, ' times between 1 and 1000');

{$IFNDEF UNIX} readln; {$ENDIF}

 

=={{header|Dyalect}}==

{{trans|Swift}}

 

for n in 2..max {

for k in 2..n {

let columns = 20

print("First \(count - 1) Mertens numbers:")

for i in 0..<count {

if i % columns > 0 {

print(" ", terminator: "")

}

if (i + 1) % columns == 0 {

print()

previous = m

}

print("M(n) is zero \(zero) times for 1 <= n <= \(max).")

 

{{out}}

M(n) is zero 92 times for 1 <= n <= 1000.

M(n) crosses zero 59 times for 1 <= n <= 1000.</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

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)))

{{out}}

<pre>

=={{header|Factor}}==

{{works with|Factor|0.99 2020-01-23}}

math.ranges math.statistics prettyprint sequences ;

 

2 <clumps> [ first2 [ 0 = not ] [ zero? ] bi* and ] count bl

pprint bl "zero crossings." print

{{out}}

<pre>

 

=={{header|Forth}}==

 

variable mertens AMOUNT cells allot

." M(N) is zero " . ." times." cr

." M(N) crosses zero " . ." times." cr

 

{{out}}

 

=={{header|Fortran}}==

implicit none

integer M(1000), n, k, zero, cross

50 format("M(N) crosses zero ",I2," times.")

write (*,50) cross

 

{{out}}

 

=={{header|FreeBASIC}}==

return wspace(i-len(str(j)))+str(j)

end function

outstr = ""

end if

{{out}}

<pre>

-4 -3 -4 -4 -3 -2 -1 -1 -2 -2

-1 -1 0 1 2 2 1 1 1 1

</pre>

 

=={{header|Go}}==

 

import "fmt"

fmt.Println("\n\nEquals zero", zeros, "times between 1 and 1000")

fmt.Println("\nCrosses zero", crosses, "times between 1 and 1000")

 

{{out}}

Crosses zero 59 times between 1 and 1000

</pre>

=={{header|Haskell}}==

import qualified Data.MemoCombinators as Memo

import Math.NumberTheory.Primes (unPrime, factorise)

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]

{{out}}

<pre>The first 99 terms for M(1..99):

 

=={{header|J}}==

M =: +/@([: mu 1:+i.)

 

echo 'M(N) is zero ',(":zero),' times.'

echo 'M(N) crosses zero ',(":cross),' times.'

 

{{out}}

 

=={{header|Java}}==

public class MertensFunction {

 

 

}

 

{{out}}

 

'''Preliminaries'''

def sum(s): reduce s as $x (null; . + $x);

 

end

| .prev = $a[$i] )

'''Mertens Numbers'''

# Input: $max >= 1

# Output: an array of size $max with $max mertenNumbers beginning with 1

.[$n-1]=1

| reduce range(2; $n+1) as $k (.;

'''The Tasks'''

def mertens_number:

mertensNumbers[.-1];

(1000 | (task2, task3))

 

{{out}}

<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)

 

foreach(maximinM, (1000, 1_000_000, 1_000_000_000))

<pre>

First 99 terms of the Mertens function for positive integers:

 

=={{header|MAD}}==

DIMENSION M(1000)

PRINT FORMAT FC, CROSS

 

{{out}}

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Mertens[n_] := Total[MoebiusMu[Range[n]]]

Grid[Partition[Mertens /@ Range[99], UpTo[10]]]

Count[Mertens /@ Range[1000], 0]

{{out}}

<pre>1 0 -1 -1 -2 -1 -2 -2 -2 -1

92

59</pre>

 

=={{header|Nim}}==

{{trans|C}}

 

func mertensNumbers(max: int): seq[int] =

echo ""

echo &"M(n) is zero {zero} times for 1 ⩽ n ⩽ {Max}."

 

{{out}}

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}

setlength(primes,0);

setlength(sieve,0);

{{out}}

<pre>[1 to limit]

 

=={{header|Perl}}==

use strict;

use warnings;

(' '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) .

{{out}}

<pre>Mertens sequence - First 199 terms:

 

=={{header|Phix}}==

<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;">end</span> <span style="color: #008080;">for</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">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>

{{out}}

<pre>

 

Mertens[1..1000] equals zero 92 times and crosses zero 59 times

</pre>

 

=={{header|Prolog}}==

{{works with|SWI Prolog}}

 

mertens_number(1, 1):- !.

count_zeros(1, 1000, Z, C),

writef('M(n) is zero %t times for 1 <= n <= 1000.\n', [Z]),

 

{{out}}

 

=={{header|PureBasic}}==

 

M(1)=1

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.")

{{out}}

<pre>First 99 Mertens numbers:

 

=={{header|Python}}==

"""Generate Mertens numbers"""

m = [None, 1]

crosses = sum(a!=0 and b==0 for a,b in zip(ms, ms[1:]))

print("M(N) equals zero {} times.".format(zeroes))

 

{{out}}

M(N) equals zero 92 times.

M(N) crosses zero 59 times.</pre>

 

=={{header|Raku}}==

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.

 

 

sub μ (Int \n) {

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:

 

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.*/

call genP /*generate primes up to max √ HIHI */

call Franz LO, HI

if xZ>0 then call Franz -1, xZ

exit 0 /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

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*/

zeros= 0 /*# of 0's found for Mertens function.*/

Xzero= 0 /*number of times that zero was crossed*/

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*/

prev= _

if grid then $= $ right(_, 2) /*build grid if A & B are non─negative.*/

end /*j*/ /*for small grids, using wordCnt is OK.*/

 

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

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. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

x= x % p /* Divide by prime. */

if x//p==0 then return 0 /*X÷by P? Then return zero*/

end

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*k*/ /* [↓] a prime (J) has been found. */

{{out|output|text=&nbsp; when using the default inputs:}}

 

 

=={{header|Ruby}}==

 

def μ(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."

{{out}}

<pre> 1 0 -1 -1 -2 -1 -2 -2 -2 -1 -2 -2 -3 -2 -1 -1 -2 -2 -3

it crosses zero 59 times.

</pre>

 

=={{header|Sidef}}==

Built-in:

 

Algorithm for computing M(n) in sublinear time:

 

 

var lookup_size = (2 * n.iroot(3)**2)

cache{n} = M

}(n)

 

Task:

say "Mertens function in the range 1..#{n}:"

(1..n).map { mertens(_) }.slices(20).each {|line|

say (1..n->count_by { mertens(_)==0 }, " zeros")

say (1..n->count_by { mertens(_)==0 && mertens(_-1)!=0 }, " zero crossings")

{{out}}

<pre>

=={{header|Swift}}==

{{trans|C}}

 

func mertensNumbers(max: Int) -> [Int] {

}

print("M(n) is zero \(zero) times for 1 <= n <= \(max).")

 

{{out}}

M(n) is zero 92 times for 1 <= n <= 1000.

M(n) crosses zero 59 times for 1 <= n <= 1000.

</pre>

 

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

 

var isSquareFree = Fn.new { |n|

prev = next

}

 

{{out}}

 

The Mertens function crosses zero 59 times in the range [1, 1000].

</pre>

 

=={{header|zkl}}==

[1..].tweak(fcn(n,pm){

pm.incN(mobius(n));

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) });

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) ));

{{out}}

<pre>