ISC Computer Practical Examination 2008

A  Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding 1). The first few such numbers are 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985.

Smith numbers were named by Albert Wilansky of Lehigh University. He noticed the property in the phone
number (493-7775) of his brother-in-law Harold Smith:
4937775 = 3 × 5 × 5 × 65837, while 4 + 9 + 3 + 7 + 7 + 7 + 5 = 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42.

Examples:
1.  666
Prime factors are 2, 3, 3, and 37
Sum of the digits are (6+6+6) = 18
Sum of the digits of the factors (2+3+3+(3+7)) = 18
2.   4937775
Prime factors are 3, 5, 5, 65837
Sum of the digits are (4+9+3+7+7+7+5) = 42
Sum of the digits of the factors (3+5+5+(6+5+8+3+7)) = 42

Write a program to input a number and display whether the number is a Smith number or not.

Note: The above is not the verbatim copy of the question which was actually asked in the ISC Computer Science Practical Examination 2008.

Sample data:
Input             94          Output            SMITH Number
Input             102        Output            NOT SMITH Number
Input             666        Output            SMITH Number
Input             999        Output            NOT SMITH Number

The Java program to test for a Smith number is as follows:

class Smith{
    // Function to find the sum of digits of a positive integer
    public static int sumOfDigits( int n ){
        int sum=0;
        for( int temp = n ; temp > 0 ; temp /= 10 ){
            sum += temp % 10;
        }
        return sum;
    }
    // Function to test for primality
    public static boolean isPrime( int num ){
        int factorCount=0;
        if( num < 2 ) return false;
        else if( num == 2 ) return true;
        else if( num % 2 == 0 ) return false;
        else{
            int limit = ( int )Math.sqrt( num );
            for( int i=3; i<=limit; i+=2 ){
                if( num%i==0 ){
                    return false;
                }
            }
        }
        return true;
    }
    // Function to test for Smith number
    public static boolean isSmithNumber( int n ){
        if( isPrime( n ) ) return false;
        int temp = n, divisor, sumOfPrimeFactors = 0;
        while( temp % 2 == 0 ){
            temp = temp / 2;
            sumOfPrimeFactors += 2;
        }
        divisor = 3;
        while( temp !=1 ){
            while( temp % divisor == 0){
                temp = temp / divisor;
                sumOfPrimeFactors += sumOfDigits( divisor );
            } 
            if( temp == 1 ) break;
            do{
                divisor += 2;
            }while( !isPrime( divisor ) );
        }
        return sumOfPrimeFactors == sumOfDigits( n );
    }
    public static void main( String []args ){
        for( int i = 1; i <= 1000 ; i++){
            if( isSmithNumber( i ) ) System.out.println( i );
        }
    }
}

The above program would display all the Smith numbers in the range of 1 to 1000.

The function sumOfDigits( ) finds the sum of digits of the integer argument.

The function isPrime( ) return true if the argument is a prime number and false if the argument is not a prime number. I have already discussed the details of the function isPrime( ) in  a separate post. Please visit http://www.vinaysingh.info/prime-time/ for the details of isPrime( ) function.

The function isSmithNumber( ) essentially does prime factorization and also computes sum of digits of the prime factor using the sumOfDigit( ) function which is then compared with the sum of digits of original number to obtain the final result. Since 2 is the only even prime number we are dividing by 2 separately. Once the number is no longer divisible by 2 we start dividing by other prime numbers starting from 3. Also note that after three we increasing the variable divisor by 2 because even numbers other than 2 cannot be prime.

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.