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

 

<pre>First 99 Mertens numbers:

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

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

 

=={{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>

 

return m;

}

 

if (column > 0)

std::cout << ' ';

std::cout << " ";

else

++column;

if (column == 20) {

}

}

int zero = 0, cross = 0, previous = 0;

++zero;

if (previous != 0)

++cross;

}

}

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;

 

{{out}}

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

</pre>

 

=={{header|Cowgol}}==

 

const MAX := 1000;

 

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

 

{{out}}

M(n) is zero 92 times

M(n) crosses zero 59 times</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>

59 zero crossings.

</pre>

 

=={{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}}

M(x) has 41,908 zeroes in the interval.

M(x) has 25,525 crossings in the interval.

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

M(N) IS ZERO 92 TIMES

M(N) CROSSES ZERO 59 TIMES</pre>

 

=={{header|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.<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}}==

{{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}}

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

</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:}}

 

The Mertens sequence from 1 to 1000 has crossed 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>

92 zeros

59 zero crossings

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