Tuesday 27 October 2015

MOBIUS function

The MOBIUS function M( N) for a natural number N is defined as follows:
M( N) = 1 if N = 1
= 0 if any prime factor of N is contained in N more than once
= ( -1)^ P if N is a product of p distinct prime factors
Example :
M( 78) = -1 ( for 78 = 2 * 3 * 13 M( 78) = ( -1)^ 3 = -1 )
M( 34) = 1 ( for 34 = 2 * 17 M( 34) = ( -1) ^2 = 1 )
M( 12) = 0 ( for 12 = 2 * 2 * 3 M( 12) = 0 for 2 appears two times)
M( 17) = -1 ( for 17 = 17 M( 17) = ( -1)^ 1 = -1 )
Write a program to input natural number N and output M( N).
import java.io.*;
class MobiusFn
{
BufferedReader ob = new BufferedReader(new InputStreamReader(System.in));
int n,a,p,c,q;
public MobiusFn()
{
a=2;
p=0;
c=0;
}
public void input() throws IOException
{
System.out.println("Enter a number ");
n=Integer.parseInt(ob.readLine());
}
public int primefac(int x)
{
if(x==1) return 1;
while(x>1)
{
c=0;
while(x%a==0)
{
c++;
p++;
System.out.println("Prime Fator is "+a);
x=x/a;
}
if(c>1) return 0;
a++;
}
q=(int)Math.pow(-1,p);
return q;
}
public void display()
{
int r=primefac(n);
if(r==0) System.out.println("Prime factor of N is contained in N more than once. Mobius function returns " + r );
else System.out.println("Mobius function returns value " + r);
}
public static void main(String arg[]) throws IOException
{
MobiusFn obj = new MobiusFn();
obj.input();
obj.display();
}
}

No comments:

Post a Comment