Möbius function: Difference between revisions

=={{header|ALGOL 68}}==

{{Trans|C}}

# show the first 199 values of the moebius function #

INT sq root = 1 000;

IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI

OD

{{out}}

<pre>

=={{header|Arturo}}==

 

if n=0 -> return ""

if n=1 -> return 1

 

loop split.every:20 map 0..199 => mobius 'a ->

 

{{out}}

 

=={{header|AutoHotkey}}==

result .= SubStr(" " Möbius(A_Index), -1) . (Mod(A_Index, 10) ? " " : "`n")

MsgBox, 262144, , % result

ans.push(Format("{:d}", n))

return ans

{{out}}

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

 

=={{header|AWK}}==

# syntax: GAWK -f MOBIUS_FUNCTION.AWK

# converted from Java

return(MU[n])

}

{{out}}

<pre>

=={{header|BASIC256}}==

{{trans|FreeBASIC}}

if n = 1 then return 1

for d = 2 to int(sqr(n))

end if

next i

{{out}}

<pre>

=={{header|C}}==

{{trans|Java}}

#include <stdio.h>

#include <stdlib.h>

free(mu);

return 0;

{{out}}

<pre>First 199 terms of the m÷bius function are as follows:

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

{{trans|Java}}

#include <iostream>

#include <vector>

 

return 0;

{{out}}

<pre>First 199 terms of the m÷bius function are as follows:

=={{header|D}}==

{{trans|C++}}

import std.stdio;

 

}

}

{{out}}

<pre>First 199 terms of the m├╢bius function are as follows:

=={{header|F_Sharp|F#}}==

This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]]

// Möbius function. Nigel Galloway: January 31st., 2021

let fN g=let n=primes32()

let mobius=seq{yield 1; yield! Seq.initInfinite((+)2>>fN)}

mobius|>Seq.take 500|>Seq.chunkBySize 25|>Seq.iter(fun n->Array.iter(printf "%3d") n;printfn "")

{{out}}

<pre>

The <code>mobius</code> word exists in the <code>math.extras</code> vocabulary. See the implementation [https://docs.factorcode.org/content/word-mobius%2Cmath.extras.html here].

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

 

"First 199 terms of the Möbius sequence:" print

199 [1,b] [ mobius ] map " " prefix 20 group

{{out}}

<pre>

=={{header|Fortran}}==

{{Trans|C}}

program moebius

use iso_fortran_env, only: output_unit

end do

end program moebius

 

{{out}}

 

=={{header|FreeBASIC}}==

if n = 1 then return 1

for d as uinteger = 2 to int(sqr(n))

outstr = ""

end if

{{out}}

<pre>

 

=={{header|FutureBasic}}==

BOOL result = YES

long i

next

 

{{output}}

<pre>

 

=={{header|Go}}==

 

import "fmt"

fmt.Printf(" % d", mobs[i])

}

 

{{out}}

 

=={{header|GW-BASIC}}==

20 FOR U = 1 TO 10

30 N = 10*T + U

170 M = -M

180 N = N/F

 

=={{header|Haskell}}==

import Data.List.Split (chunksOf)

import Data.Vector.Unboxed (toList)

putStrLn ("μ(n) for 1 ≤ n ≤ " ++ show n ++ ":\n") >>

putStrLn (showMoebiusBlock cols $ moebiusBlock n)

 

{{out}}

Implementation:

 

 

Explanation: _ q: n gives the list of exponents of prime factors of n. (This is an empty list for the number 1, is 2 0 2 for the number 100 and is 3 1 1 for the number 120.)

Task example:

 

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

 

=={{header|Java}}==

public class MöbiusFunction {

 

 

}

 

{{out}}

====Using a Sieve====

'''Adapted from [[#C|C]]'''

# Output: an array of size $n + 1 such that the nth-mobius number is .[$n]

# i.e. $n|mobius_array[-1]

 

# For one-off computations:

'''The Task'''

def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;

n;

| join(" ") ) ;

 

{{out}}

<pre>

Note that the following solution to the task at hand (computing a range of Mobius numbers is inefficient as it does not cache the primes array.

'''Preliminaries'''

# relative to the primes in the array "previous":

def relatively_prime(previous):

else . as $in

| pf( [ primes( (1+$in) | sqrt | floor) ] )

'''Mu'''

. as $n

| 2

else 0

end

'''The Task'''

def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;

n;

| join(" ") ) ;

 

{{out}}

As above.

 

=={{header|Julia}}==

 

# modified from reinermartin's PR at https://github.com/JuliaMath/Primes.jl/pull/70/files

print(lpad(μ(n), 3), n % 20 == 19 ? "\n" : "")

end

<pre>

First 199 terms of the Möbius sequence:

=={{header|Kotlin}}==

{{trans|Java}}

 

fun main() {

}

return MU!![n]

{{out}}

<pre>First 199 terms of the möbius function are as follows:

=={{header|Lua}}==

{{trans|C}}

local tbl = {}

for i=1, size do

print()

end

{{out}}

<pre>First 199 terms of the mobius function are as follows:

 

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

{{out}}

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

Uses the prime decomposition method from https://rosettacode.org/wiki/Prime_decomposition#Nim

 

 

func getStep(n: int): int {.inline.} =

if i mod 20 == 0:

echo "" # print newline

{{out}}

<pre>The first 199 möbius numbers are:

 

=={{header|Perl}}==

use strict;

use warnings;

 

say "Möbius sequence - First $upto terms:\n" .

{{out}}

<pre>Möbius sequence - First 199 terms:

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">Moebius</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">199</span> <span style="color: #008080;">do</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">Moebius</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

 

# Python Program to evaluate

# Mobius def M(N) = 1 if N = 1

if i % 20 == 0: print()

# This code is contributed by

{{out}}

<pre>Mobius numbers from 1..99:

The idea is based on efficient program to print all prime factors of a given number. The interesting thing is, we do not need inner while loop here because if a number divides more than once, we can immediately return 0.

# Mobius def M(N) = 1 if N = 1

# M(N) = 0 if any prime factor

print(f"{mobius(i):>4}", end = '')

# This code is contributed by

{{out}}

<pre>Mobius numbers from 1..99:

Möbius number is not defined for n == 0. Raku arrays are indexed from 0 so store a blank value at position zero to keep n and μ(n) aligned.

 

 

sub μ (Int \n) {

# The Task

put "Möbius sequence - First 199 terms:\n",

{{out}}

<pre>Möbius sequence - First 199 terms:

 

The function to computer some prime numbers is a bit of an overkill, but the goal was to keep it general &nbsp;(in case of larger/higher ranges for a Möbius sequence).

parse arg LO HI grp . /*obtain optional arguments from the CL*/

if LO=='' | LO=="," then LO= 0 /*Not specified? Then use the default.*/

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

nP= nP+1; if nP<=HI then @.nP= j /*bump prime count; assign prime to @.*/

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

 

=={{header|Ring}}==

{{Trans|FreeBASIC}}

mobStr = " . "

 

next

return -1

Output:

<pre>

 

=={{header|Ruby}}==

 

def μ(n)

([" "] + (1..199).map{|n|"%2s" % μ(n)}).each_slice(20){|line| puts line.join(" ") }

 

{{out}}

<pre>

Built-in:

 

say moebius(54) #=> 0

 

Simple implementation:

var f = n.factor_exp.map { .tail }

f.any { _ > 1 } ? 0 : ((-1)**f.sum)

say line.map { '%2s' % _ }.join(' ')

})

{{out}}

<pre>

Tiny BASIC is not suited for printing tables, so this is limited to prompting for a single number and calculating its Mobius number.

 

INPUT N

IF N < 0 THEN LET N = -N

END

101 PRINT "1"

 

=={{header|Wren}}==

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

import "/math" for Int

 

}

System.print()

 

{{out}}

 

=={{header|XPL0}}==

int N, Cnt, F, K;

[Cnt:= 0;

if rem(N/20) = 19 then CrLf(0);

];

 

{{out}}

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

for i = 1 to 200

if mobius(i) >= 0 then outstr$ = outstr$ + " " : fi

next d

return -1

 

=={{header|zkl}}==

pf:=primeFactors(n);

sq:=pf.filter1('wrap(f){ (n % (f*f))==0 }); // False if square free

if(n!=m) acc.append(n/m); // opps, missed last factor

else acc;

.pump(Console.println, T(Void.Read,19,False),

{{out}}

<pre>