ISC Practicals and Theory - Smith Number

A Smith number is a composite number whose sum of digits is equal to the sum of the digits of all its prime factors, each factor counted as many times as it occurs. This program is written in the main method alone: it finds the prime factors, adds the digits of each, and compares the total with the digit sum of the number.

Definition

A Smith number is a composite number $N$ for which

sum of the digits of $N$ = sum of the digits of all the prime factors of $N$ (a repeated prime factor is counted each time it occurs).

• $22 = 2 \times 11$. Digit sum of $22$ is $2 + 2 = 4$. Digit sums of the factors: $2$ gives $2$ and $11$ gives $1 + 1 = 2$, total $4$. Both are $4$, so $22$ is a Smith number.
• $4937775 = 3 \times 5 \times 5 \times 65837$. Digit sum of the number is $4+9+3+7+7+7+5 = 42$. Digit sums of the factors: $3 + 5 + 5 + (6+5+8+3+7) = 3 + 5 + 5 + 29 = 42$. So it is a Smith number.
• $15 = 3 \times 5$. Digit sum of $15$ is $6$, but the factors give $3 + 5 = 8$. Not a Smith number.
• A prime number is never a Smith number, because a Smith number must be composite (a prime has only itself as its prime factor, so the two sums would always be equal and the test would mean nothing). $1$ is also not a Smith number as it is not composite.

Algorithm

1. Accept the number num. If num < 1, display Invalid input and stop.
2. Copy num into n and set total = 0 and count = 0.
3. For f from 2 up to n, while n % f == 0:
   • f is a prime factor: find the sum of its digits in s (using % 10 and / 10) and add it to total;
   • add 1 to count and divide n by f.
4. Find the digit sum of num itself in ds.
5. If num == 1, it is not a Smith number. If count == 1, the number has only one prime factor (itself), so it is prime and not a Smith number. Otherwise, if total == ds, it is a Smith number; if not, it is not.

Program

Everything is written inside main: the for loop with the while loop inside it finds the prime factors, and small while loops find the digit sums.

import java.util.Scanner;
public class Smith
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = sc.nextInt();                 // the number to be checked
        if (num < 1)
        {
            System.out.println("Invalid input");
        }
        else
        {
            int n = num;                        // copy of num that is divided by its factors
            int total = 0;                      // sum of the digits of all the prime factors
            int count = 0;                      // number of prime factors, repeated ones counted
            for (int f = 2; f <= n; f++)
            {
                while (n % f == 0)
                {
                    int x = f, s = 0;           // s is the digit sum of the factor f
                    while (x > 0)
                    {
                        s = s + x % 10;
                        x = x / 10;
                    }
                    total = total + s;
                    count++;
                    n = n / f;
                }
            }
            int y = num, ds = 0;                // ds is the digit sum of num
            while (y > 0)
            {
                ds = ds + y % 10;
                y = y / 10;
            }
            if (num == 1)
                System.out.println("1 is not a Smith number");
            else if (count == 1)
                System.out.println(num + " is a prime number, so it is not a Smith number");
            else if (total == ds)
                System.out.println(num + " is a Smith number");
            else
                System.out.println(num + " is not a Smith number");
        }
    }
}

Variable description table

Sample input and output

Enter a number: 22
22 is a Smith number

Enter a number: 15
15 is not a Smith number

Enter a number: 13
13 is a prime number, so it is not a Smith number

Enter a number: -5
Invalid input

Dry run

Input: num = 22. The factor loop starts with n = 22, total = 0, count = 0.

Now f becomes $12$, and f <= n is false, so the loop ends and total = 4. The digit sum of 22 is $2 + 2 = 4$, so ds = 4. Since count = 2 (not $1$) and the two sums are equal, the program shows that $22$ is a Smith number, as in the first sample run.

Variations

1. Range: "Display all Smith numbers between m and n."
2. Recursion: "Find the sum of the digits of a number using recursive technique and use it to check a Smith number."
3. Prime factors: "Display the prime factors of a number and the sum of their digits."
4. Niven number: "Check whether a number is divisible by the sum of its digits."