ISC Practicals and Theory - Keith Number (OOP)

A Keith number is a number that appears in a series made from its own digits: start with the digits, then add the last few terms to get each new term. This version writes the check as a class KeithNumber with a parameterised constructor and a separate method for every job.

Definition

A number $N$ with $d$ digits ($d \ge 2$) is a Keith number if it appears in the series whose first $d$ terms are its digits and each later term is the sum of the previous $d$ terms.

A Keith number must have at least 2 digits, so a number below 10 is not tested: the program prints an invalid-input message for it.

Example: 75 has 2 digits, so the series is $7, 5, 12, 17, 29, 46, 75$. It reaches 75, so 75 is a Keith number. For 15 the series is $1, 5, 6, 11, 17, \ldots$ and skips 15, so 15 is not.

Algorithm

1. main reads the number into num, creates KeithNumber ob = new KeithNumber(num) and calls ob.display().
2. The constructor stores num in the data member n, sets d = 0 and makes t a one-place long array (it is resized later).
3. display() prints the invalid message if n < 10; otherwise it calls isKeith().
4. isKeith() calls countDigits() to set d, then storeDigits() to fill the array t with the digits of n.
5. While next < n:
   • sumOfTerms() returns the sum of the d terms in t; this is the new next
   • shift(next) moves every term one place left and puts next at the end
6. When the loop ends, the method returns next == n.
7. display() prints the result.

The terms (t, next, s and term) are long. When n is close to 2147483647 the sum of d terms can be larger than the biggest int; with int it would wrap round to a negative number and the loop would never end.

Program

Each method does one job: countDigits() counts, storeDigits() fills the array, sumOfTerms() adds, shift() slides the window and isKeith() controls the series.

import java.util.*;

/**
 * Class KeithNumber (OOP version) checks whether a number is a Keith number.
 * The object is created with the number; each method does one job.
 */
public class KeithNumber
{
    int n;          // the number to be checked
    int d;          // number of digits in n
    long t[];       // the latest d terms of the Keith series (long: sums can exceed the biggest int)

    /**
     * Parameterised constructor: stores the number and prepares the array.
     * @param num the number to be checked
     */
    KeithNumber(int num)
    {
        n = num;
        d = 0;
        t = new long[1];    // resized once the digit count is known
    }

    /** Counts the digits of n and stores the count in d. */
    void countDigits()
    {
        int x = n;          // working copy of n
        d = 0;
        while (x > 0)
        {
            d++;
            x = x / 10;     // drop the last digit
        }
    }

    /** Stores the digits of n, left to right, as the first d terms in t[]. */
    void storeDigits()
    {
        t = new long[d];
        int x = n;          // working copy of n
        for (int i = d - 1; i >= 0; i--)
        {
            t[i] = x % 10;  // last digit goes to the last place
            x = x / 10;
        }
    }

    /**
     * Adds up the d terms currently held in t[].
     * @return the sum of the d terms
     */
    long sumOfTerms()
    {
        long s = 0;         // running sum
        for (int i = 0; i < d; i++)
            s = s + t[i];
        return s;
    }

    /**
     * Slides the window of terms one place to the left and adds the new term.
     * @param term the newly generated term of the series
     */
    void shift(long term)
    {
        for (int i = 0; i < d - 1; i++)
            t[i] = t[i + 1];    // the oldest term is dropped
        t[d - 1] = term;        // the new term goes at the end
    }

    /**
     * Generates the series until a term is not less than n.
     * @return true if the series reaches n exactly, otherwise false
     */
    boolean isKeith()
    {
        countDigits();
        storeDigits();
        long next = 0;          // the term being generated
        while (next < n)
        {
            next = sumOfTerms();
            shift(next);
        }
        return next == n;
    }

    /** Displays the result for the number. */
    void display()
    {
        if (n < 10)
            System.out.println("Invalid input: a Keith number must have at least 2 digits");
        else if (isKeith())
            System.out.println(n + " is a Keith number");
        else
            System.out.println(n + " is not a Keith number");
    }

    /** main method: reads the number, creates the object and calls display(). */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = sc.nextInt();
        KeithNumber ob = new KeithNumber(num);
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a number: 75
75 is a Keith number

Enter a number: 197
197 is a Keith number

Enter a number: 15
15 is not a Keith number

Enter a number: 7
Invalid input: a Keith number must have at least 2 digits

Dry run

Input: 75, so d = 2 and t = {7, 5}.

next == n (75 == 75), so isKeith() returns true and the program prints 75 is a Keith number.

Variations

1. Range of Keith numbers: "Display all Keith numbers between two given limits m and n."
2. Smith number: "Check whether a number is a Smith number."
3. Disarium number: "Check whether a number is a Disarium number."