ISC Practicals and Theory - Keith Number

A Keith number is a number that shows up inside a series built from its own digits. You start the series with the digits of the number, then keep adding the last few terms to get the next one. If the series lands exactly on the number, it is a Keith number. This note gives the method, an ISC-style Java program written in the main method alone, sample runs and a dry run.

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 the digits of $N$ and in which every later term is the sum of the previous $d$ terms.

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

Example: 14 has 2 digits, so each term is the sum of the previous 2 terms.

$1, 4, 5, 9, 14, \ldots$

14 appears, so 14 is a Keith number.

Example: 197 has 3 digits, so each term is the sum of the previous 3 terms.

$1, 9, 7, 17, 33, 57, 107, 197, \ldots$

197 appears, so 197 is a Keith number.

Example: 15 gives $1, 5, 6, 11, 17, \ldots$. The series jumps from 11 to 17 and never equals 15, so 15 is not a Keith number.

Algorithm

1. Accept the number n. If n < 10, print an invalid-input message and stop, because a Keith number must have at least 2 digits.
2. Count the digits of n in d: copy n into x and, while x > 0, add 1 to d and drop the last digit with x = x / 10.
3. Create the array t of size d to hold the latest d terms of the series. Fill it with the digits of n, the last digit going in the last place (t[i] = x % 10, for i from d - 1 down to 0).
4. Set next = 0. While next < n:
   • set next to the sum of all the d terms in t;
   • slide the window one place to the left (t[i] = t[i + 1]) and put next in the last place t[d - 1].
5. When the loop stops, next is the first term that is not less than n. If next == n, the series hits n exactly, so n is a Keith number. Otherwise it is not.

Program

Everything is written inside main: the digit count, the array of terms and the while loop that generates the series.

import java.util.*;
public class Keith
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int n = sc.nextInt();                   // the number to be checked
        if (n < 10)
        {
            System.out.println("Invalid input: a Keith number must have at least 2 digits");
        }
        else
        {
            int d = 0;                          // number of digits in n
            int x = n;                          // working copy of n
            while (x > 0)
            {
                d++;
                x = x / 10;                     // drop the last digit
            }
            long t[] = new long[d];             // the latest d terms of the series
            x = n;
            for (int i = d - 1; i >= 0; i--)
            {
                t[i] = x % 10;                  // first d terms are the digits of n
                x = x / 10;
            }
            long next = 0;                      // the term being generated
            while (next < n)
            {
                next = 0;
                for (int i = 0; i < d; i++)
                    next = next + t[i];         // sum of the previous d terms
                for (int i = 0; i < d - 1; i++)
                    t[i] = t[i + 1];            // slide the window one place left
                t[d - 1] = next;                // newest term goes at the end
            }
            if (next == n)                      // n is Keith if the series hits n exactly
                System.out.println(n + " is a Keith number");
            else
                System.out.println(n + " is not a Keith number");
        }
    }
}

Variable description table

Sample input and output

Enter a number: 14
14 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: 14. Here d = 2 and t starts as the digits of 14.

The loop stops with next = 14, and next == n, so the program prints 14 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."