Mobius Function Program in Java and Python
Mobius function program with algorithm, explanation, Java class solution and simple Python solution for ISC students.
Question:
The Mobius function M(N) for a natural number N is defined as follows: M(N) = 1 if N = 1; M(N) = 0 if any prime factor of N occurs more than once; and M(N) = (-1)p if N is a product of p distinct prime factors. Design class MobiusFn with input, prime factor counting and display methods.
Algorithm:
Step 1: Start.
Step 2: Accept the number n and store it in the object variable.
Step 3: If n is 1, directly store Mobius value as 1.
Step 4: Otherwise call primeFac() to analyse the prime factors of n.
Step 5: Inside primeFac(), copy n into a working variable a so the original value remains unchanged.
Step 6: Initialize divisor i to 2, factor counter f to 0 and frequency counter c for each divisor.
Step 7: Repeat while a is greater than 1.
Step 8: For each divisor i, repeatedly divide a by i while a % i is 0, incrementing both c and f.
Step 9: If c becomes greater than 1 for any divisor, return 0 because a prime factor has repeated.
Step 10: Increment i and continue checking the next possible divisor.
Step 11: If no repeated prime factor is found, return f, the number of distinct prime factors.
Step 12: In display(), if primeFac() returns 0, print Mobius value 0; otherwise calculate (-1) raised to the returned factor count.
Step 13: Stop.
Explanation:
The program is object-based, so the input number is stored in the instance variable n. The constructor initializes this variable before input() reads the actual value.
The method primeFac() performs the main factor analysis. It uses a working copy a because repeated division changes the value being factorised.
For each possible divisor i, the inner loop divides a as long as i is a factor. The variable c counts how many times the same factor occurs, while f counts total prime-factor occurrences.
If c is greater than 1 for any divisor, the function returns 0 immediately because the Mobius value must be 0 when a prime factor repeats.
If there is no repeated prime factor, display() uses the count returned by primeFac(). An even count gives 1 and an odd count gives -1 through (-1)p.
The Mobius function depends on prime factorisation. The program must determine whether the number has repeated prime factors and how many distinct prime factors it has. If any prime factor divides the number more than once, the Mobius value becomes 0. If there are no repeated factors, the sign depends on whether the number of distinct prime factors is even or odd. This makes factor counting and repeated divisibility checks central to the solution. The program is therefore testing factor structure, not just divisibility by one number.
Java Program:
/**
* The class MobiusFn inputs a number and calculates the value of Mobius Function
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC Theory 1999
*/
import java.util.*;
class MobiusFn
{
int n;
MobiusFn()
{
n = 0;
}
void input()
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number : ");
n = sc.nextInt();
}
/* The function primefac() either returns '0' if prime factors are repeated
* or returns the no.of prime factors */
int primeFac()
{
int a=n, i=2, m=0, c=0, f=0;
while(a > 1) // loop to generate prime factors
{
c = 0; // variable to store frequency of every prime factor
while(a%i == 0) // if 'i' is a prime factor
{
c++; // counting frequency of 'i'
f++; // counting no of prime factors
a=a/i;
}
i++;
if(c > 1) // returning '0' if prime factors are repeated
return 0;
}
return f; // returning no. of prime factors
}
void display() // function to display value of mobius function
{
int mob,x;
if(n == 1) // condition 1
mob = 1;
else
{
x = primeFac();
if(x == 0) // condition 2
mob = 0;
else // condition 3
mob = (int)Math.pow(-1,x);
}
System.out.println("Value of Mobius Function : "+mob);
}
public static void main(String args[])
{
MobiusFn ob = new MobiusFn();
ob.input();
ob.display();
}
}Equivalent Python Program:
# Read the number and keep factor-checking logic inside helper functions.
def prime_fac(n):
a = n
i = 2
f = 0
# Test each possible divisor and count how many times it divides the number.
while a > 1:
c = 0
while a % i == 0:
c = c + 1
f = f + 1
a = a // i
# A repeated prime factor makes the Mobius value equal to 0.
if c > 1:
return 0
i = i + 1
return f
n = int(input("Enter a number: "))
if n == 1:
mob = 1
else:
x = prime_fac(n)
if x == 0:
mob = 0
elif x % 2 == 0:
mob = 1
else:
mob = -1
print("Value of Mobius Function:", mob)Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.