Wednesday, February 22, 2012

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

3 comments:

Anonymous said...

sir, could you please give the solution of this question asked in 2002 ISC practical exam-

Write the program to do the following:
Read in an integer n (which can be at most 50). Then read in n integers one by one
and store them in an array data from index 0 to n-1. Now we want to rearrange the
integers in data in the following way :
Find the maximum value in data and put in the centre of the array (that is at (n/2);
find the next largest value and put it to its right; then the next largest and place it to
its left and so on alternating right and left until all integers in data are done. For
example, if the array is initially:
7, 3, 1, 6, 4, 2, 5 then after rearranging it becomes 1, 3, 5, 7, 6, 4, 2
However, since we have very little memory, you are not allowed to use any other array from data.

RASHI NIGAM said...

sir please tell this question...I will highly THANKFULL TO U....
=>program to encode a string using given set of rules.Eg.write a program that will replace every character in a srting with a character which is found next to that character in your keyboard(with few asumptions and other rules..)eg. replace q with w ,t with y ,]with a asume shift is off and caps lock is off....

Anonymous said...

Do that using recursion Boss D.K .