Composite Magic Number

A Composite Magic number is a positive integer which is composite as well as a magic number.
Composite number: A composite number is a number that has more than two factors. For example: 10, factors are: 1, 2, 5, 10
Magic number: A magic number is a number in which the eventual sum of the digits is equal to 1. For example: 28=2+8=10=1+0=1

Accept two positive integers m and n, where m is less than n as user input. Display the number of Composite Magic integers that are in the range between m and n (both inclusive) and output them along with the frequency, in the format specified below.
Example 1:

Input  m=10
       n=100
Output:
THE COMPOSITE INTEGERS ARE:
10, 28, 46, 55, 64, 82, 91, 100
FREQUENCY OF COMPOSITE MAGIC INTEGERS IS: 8

Example 2:

Input  m=1200
       n=1300
Output:
THE COMPOSITE INTEGERS ARE:
1207, 1216, 1225, 1234, 1243, 1252, 1261, 1270, 1288
FREQUENCY OF COMPOSITE MAGIC INTEGERS IS: 9

Example 3:

Input  m=120
       n=99
Output:
INVALID INPUT

The above Composite Magic number problem was asked in the ISC Computer Practical Examination in the year 2014. The Java program for the Composite Magic number problem is as follows:

import java.util.*;
class CompositeMagic{
    public static boolean isPrime(int number){
        if(number < 2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            int limit = (int)Math.sqrt(number);
            for(int i=3; i <=limit; i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean isComposite(int n){
        return !isPrime(n);
    }
    public static boolean isMagicNumber(int n){
        int sum;
        do{
            sum=0;
            for(int temp=n; temp > 0; temp /=10){
                sum+=temp%10;
            }
            n=sum;
        }while(sum > 9);
        return sum==1;
    }
    public static void main(String args[]){
        int m, n;
        Scanner sc = new Scanner(System.in);
        System.out.print("m = ");
        m=sc.nextInt();
        System.out.print("n = ");
        n=sc.nextInt();
        if(m>=n) System.out.println("INVALID INPUT");
        else{
            System.out.println("THE COMPOSITE MAGIC INTEGERS ARE:");
            int frequency=0;
            String output="";
            for(int i=m; i<=n; i++){
                if(isMagicNumber(i) && isComposite(i)){
                    output+=i+", ";
                    frequency++;
                }
            }
            output=output.substring(0, output.length()-2);
            System.out.println(output);
            System.out.println("FREQUENCY OF COMPOSITE MAGIC INTEGERS IS: "+frequency);
        }
    }
}

The above program on Composite Magical number uses the isPrime3( ) function of my earlier blog post to check for primality. Students are advised to refer to the earlier blog post for details of the isPrime() method which checks for primality ( test for prime number) in an efficient manner. The function isMagicNumber() accepts an integer and returns a boolean value indicating whether or not the argument is prime.

Also note that we are using the isMagicNumber( ) and isComposite() function as follows:

if(isMagicNumber(i) && isComposite(i)){

instead of

if(isComposite(i) && isMagicNumber(i)){

to test for Magic number and composite number for efficiency. This is because in the average case testing for magic number will require fewer iteration whereas checking for prime number is an expensive operation. If test for magic number is before the test for prime number then the test for prime number will be invoked only when the magic number function return true.

The isMagicNumber() can be implemented withΒ  O(1), that is constant time complexity using digital roots using the relation n%9==1 as follows:

public static boolean isMagicNumber(int n){
        return ( n%9 )==1;
}

Note that the above isMagicNumberFunction() does not use any loop or library function and hence is highly efficient. For details of this method view my other post which deals exclusively with magic number. Using digital roots the solution of composite magic number problem would be as follows:

import java.util.*;
class CompositeMagic{
    public static boolean isPrime(int number){
        if(number < 2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            int limit = (int)Math.sqrt(number);
            for(int i=3; i <=limit; i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean isComposite(int n){
        return !isPrime(n);
    }
    public static boolean isMagicNumber(int n){
        return ( n%9 )==1;
    }
    public static void main(String args[]){
        int m, n;
        Scanner sc = new Scanner(System.in);
        System.out.print("m = ");
        m=sc.nextInt();
        System.out.print("n = ");
        n=sc.nextInt();
        if(m>=n) System.out.println("INVALID INPUT");
        else{
            System.out.println("THE COMPOSITE MAGIC INTEGERS ARE:");
            int frequency=0;
            String output="";
            for(int i=m; i<=n; i++){
                if(isMagicNumber(i) && isComposite(i)){
                    output+=i+", ";
                    frequency++;
                }
            }
            output=output.substring(0, output.length()-2);
            System.out.println(output);
            System.out.println("FREQUENCY OF COMPOSITE MAGIC INTEGERS IS: "+frequency);
        }
    }
}

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.