Find Keith Number in Java (Easy Programs)

In mathematics, there are countless interesting phenomena waiting to be discovered. One such concept is Keith numbers. A Keith number is a specific type of number in mathematics that has an interesting property related to its digits.

What is Keith Number?

A Keith number is an n-digit integer that appears in a special sequence called a "Keith sequence."

To be classified as a Keith number, the following conditions must be met:

Start with a sequence of n positive integers (digits).
The first n terms of the sequence are the digits of the Keith number itself.
The subsequent terms of the sequence are generated by adding the previous n terms.
The Keith number itself must appear in this sequence.

Here's an example of Keith Number:

Consider the Keith number 197. To determine if it's a Keith number:

Start with the sequence [1, 9, 7].

The next term in the sequence is the sum of the previous three terms: 1 + 9 + 7 = 17.

Continue generating terms: [1, 9, 7, 17, 33, 57, 107, ...]

As you can see, the number 197 appears in the sequence. Thus, 197 is a Keith number because it satisfies all the conditions.

Keith numbers are named after Michael Keith, who first described them in 1987. They are relatively rare, and finding them can be a fun mathematical challenge. Some well-known Keith numbers include 14, 19, 28, 47, and 197, but there are many more.

In this tutorial, we will learn to find Keith number in Java using programs and examples.

Concepts to Learn:

Keith Number Program in Java Using Brute Force Search Method

Here's how you can find Keith numbers in Java using the brute force search method:

Code

import java.util.ArrayList;
import java.util.List;

public class KeithNumberFinder {

    public static void main(String[] args) {
        int limit = 10000; // Adjust the limit as needed
        List<Integer> keithNumbers = findKeithNumbers(limit);

        System.out.println("Keith Numbers up to " + limit + ":");
        for (Integer keithNumber : keithNumbers) {
            System.out.print(keithNumber + " ");
        }
    }

    public static List<Integer> findKeithNumbers(int limit) {
        List<Integer> keithNumbers = new ArrayList<>();

        for (int i = 10; i <= limit; i++) {
            if (isKeithNumber(i)) {
                keithNumbers.add(i);
            }
        }

        return keithNumbers;
    }

    public static boolean isKeithNumber(int n) {
        List<Integer> digits = new ArrayList<>();
        int temp = n;

        while (temp > 0) {
            digits.add(0, temp % 10);
            temp /= 10;
        }

        int size = digits.size();
        List<Integer> sequence = new ArrayList<>(digits);
        int next = 0;

        while (next < n) {
            next = 0;

            for (int i = 0; i < size; i++) {
                next += sequence.get(i);
                sequence.set(i, next - digits.get(i));

                if (next != n && next <= 0) {
                    break;
                }
            }

            if (next == n) {
                return true;
            }
        }

        return false;
    }
}

Output

Keith Numbers up to 10000:
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 55604 62662 86935

Explanation

In this Java program, we find Keith numbers up to a specified limit using a brute force approach.

We iterate through numbers from 10 to the given limit and check if each number is a Keith number using the isKeithNumber function.
The isKeithNumber function checks if a number is a Keith number by repeatedly generating the next term in the Keith number sequence until it reaches the target number or goes beyond it.
If a number satisfies the Keith number condition, we add it to the list of Keith numbers.
Finally, we display the list of Keith numbers found within the specified limit.

Find Keith Number in Java Using Dynamic Programming

Here's how you can find Keith numbers in Java using the dynamic programming method:

Code

import java.util.ArrayList;
import java.util.List;

public class KeithNumberFinder {

    public static void main(String[] args) {
        int limit = 10000; // Adjust the limit as needed
        List<Integer> keithNumbers = findKeithNumbers(limit);

        System.out.println("Keith Numbers up to " + limit + ":");
        for (Integer keithNumber : keithNumbers) {
            System.out.print(keithNumber + " ");
        }
    }

    public static List<Integer> findKeithNumbers(int limit) {
        List<Integer> keithNumbers = new ArrayList<>();

        for (int i = 10; i <= limit; i++) {
            if (isKeithNumber(i)) {
                keithNumbers.add(i);
            }
        }

        return keithNumbers;
    }

    public static boolean isKeithNumber(int n) {
        List<Integer> digits = new ArrayList<>();
        int temp = n;

        while (temp > 0) {
            digits.add(0, temp % 10);
            temp /= 10;
        }

        int size = digits.size();
        int[] sequence = new int[size * 2];

        for (int i = 0; i < size; i++) {
            sequence[i] = digits.get(i);
        }

        int next = 0;
        int index = size;

        while (next < n) {
            next = 0;

            for (int i = 0; i < size; i++) {
                next += sequence[index - i - 1];
                sequence[index + i] = next;
            }

            if (next == n) {
                return true;
            }

            index++;
        }

        return false;
    }
}

Output

Keith Numbers up to 10000:
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 55604 62662 86935

Explanation

We iterate through numbers from 10 to the given limit and check if each number is a Keith number using the isKeithNumber function.
The isKeithNumber function checks if a number is a Keith number by dynamically generating the next term in the Keith number sequence.
We maintain an array sequence to store the terms of the sequence, and we update it as we calculate each term.
If a number satisfies the Keith number condition, we add it to the list of Keith numbers.
Finally, we display the list of Keith numbers found within the specified limit.

Learn Next:

Examples

Find Keith Number in Java (Easy Programs)

What is Keith Number?

Keith Number Program in Java Using Brute Force Search Method

Code

Output

Explanation

Find Keith Number in Java Using Dynamic Programming

Code

Output

Explanation