ISC Practicals and Theory - Automorphic Number

An automorphic number is a number whose square ends with the number itself. This program is written in the main method alone: it reads the number, counts its digits, finds the square and compares the last digits, all in one place.

Definition

A number $N$ with $k$ digits is an automorphic number if the last $k$ digits of $N^2$ are the same as $N$.

• $25$ has 2 digits and $25^2 = 625$. The last two digits of 625 are 25, so 25 is an automorphic number.
• $76^2 = 5776$ ends in 76, so 76 is automorphic. Also $5^2 = 25$ and $6^2 = 36$ end in 5 and 6.
• $12^2 = 144$ ends in 44, not 12, so 12 is not an automorphic number.

The last $k$ digits of a number are its remainder on division by $10^k$. So $N$ is automorphic when $N^2 \% 10^k = N$.

Algorithm

1. Accept the number n using Scanner. If n <= 0, display an invalid input message and stop.
2. Copy n to temp and count its digits: while temp > 0, add 1 to digits and do temp = temp / 10.
3. Find square = (long) n * n. The long type is used because the square of a large int does not fit in an int.
4. Start with mod = 1 and multiply it by 10 exactly digits times, so that mod becomes $10^{digits}$.
5. If square % mod == n, the last digits of the square are the number itself: display that n is an Automorphic number. Otherwise display that it is not.

Program

Everything is written inside main: the input, the digit count, the square, the power of 10 and the comparison.

import java.util.Scanner;
public class Automorphic
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);        // reads input from the keyboard
        System.out.print("Enter a number: ");
        int n = sc.nextInt();                       // the number to be checked
        if (n <= 0)
        {
            System.out.println("Invalid input. Enter a positive number.");
        }
        else
        {
            int temp = n, digits = 0;               // digits counts the digits of n
            while (temp > 0)
            {
                digits++;
                temp = temp / 10;                   // removes the last digit
            }
            long square = (long) n * n;             // long: the square of a large int does not fit in an int
            long mod = 1;
            for (int i = 1; i <= digits; i++)
            {
                mod = mod * 10;                     // mod becomes 10 raised to digits
            }
            if (square % mod == n)                  // last digits of the square equal n
                System.out.println(n + " is an Automorphic number as its square is " + square + ".");
            else
                System.out.println(n + " is not an Automorphic number as its square is " + square + ".");
        }
    }
}

Variable description table

Sample input and output

Enter a number: 76
76 is an Automorphic number as its square is 5776.

Enter a number: 25
25 is an Automorphic number as its square is 625.

Enter a number: 12
12 is not an Automorphic number as its square is 144.

Enter a number: 0
Invalid input. Enter a positive number.

Dry run

Take n = 76. The first loop counts the digits, so digits = 2. Then the for loop builds mod.

The loop stops as i becomes 3, which is more than digits. square is $76 \times 76 = 5776$, and 5776 % 100 is 76. This equals n, so the program prints that 76 is an Automorphic number as its square is 5776.

Variations

1. Automorphic numbers in a range "Accept two numbers m and n and display all the automorphic numbers between m and n."
2. Automorphic numbers up to a limit "Display all the automorphic numbers from 1 to 1000."
3. Using a method that returns boolean "Write a method that accepts an integer and returns true if it is an automorphic number, otherwise false."
4. Using recursive technique "Write a program to check whether a number is automorphic using a recursive method to count its digits."