Keith Number Program in Java
Keith numbers are rare numbers with a Fibonacci like property. An n-digit number with value N is a Keith number if N is part of the Keith series generated. This series starts with the n digits of the number N. Then the subsequent numbers in the series are found by calculating the sum of preceding n numbers. If the number N appears in the series, it is called a Keith number. Keith numbers are also known as repfigit (repetitive Fibonacci-like digit) numbers. Keith numbers are very rare and computationally difficult to find. No optimized algorithm is known for finding Keith numbers. Only option is to do an exhaustive search.
For example consider the 3 digit number 742. Using the above rule, the first three numbers are 7, 4, 2. The next one is 7+4+2 (adding 3 previous numbers) = 13. The next one in series is 4+2+13 = 19. By applying this rule, following are numbers in the sequence,
7, 4, 2, 13, 19, 34, 66, 119, 219, 404, 742, 1365. The original number appears as the 11th item in the series. Hence the number 742 is a 3 digit Keith number.
Problem: Find whether a given number is a keith number using Java
The following Java program first extracts the individual digits in the number. It then computes the series using the sum of n previous numbers where n is the number of digits. If one of the numbers computed in the series is same as the input number, it is a keith number. The program stops if the value computed is bigger than the input number.
import java.util.Scanner;
// Java example - Find whether a number is a Keith number
public class KeithNumberChecker {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Please enter a number: ");
String input = scanner.nextLine();
// Keith numbers must be > 10
if (input.length() > 1 && isKeithNumber(input)) {
System.out.println(input + " is a Keith number!");
} else {
System.out.println(input + " is NOT a Keith number!");
}
scanner.close();
}
// Checks whether input number is a Keith number
public static boolean isKeithNumber(String input) {
int len = input.length();
// we keep only last n elements of the series
long[] series = new long[len];
for (int i = 0; i < len; i++) {
series[i] = Long.valueOf(input.substring(i, i + 1));
}
long next = 0;
long number = Long.valueOf(input);
while (next < number) {
next = 0;
for (int i = 0; i < len; i++) {
next += series[i];
if (i < len - 1) {
series[i] = series[i + 1]; // shift series to left
} else {
series[i] = next; // add new value to the series
}
}
if (next == number) {
return true;
}
}
return false;
}
}
Following is the sample output from the program,
java KeithNumberChecker Please enter a number: 197 197 is a Keith number!
Problem: Find all n-digit keith numbers using Java
The following Java program finds all n-digit keith numbers. It starts with the lowest n-digit number (10 raised to n) and checks all numbers till the largest n-digit number. For large numbers, this program can be very slow,
import java.util.Scanner;
// Java source code for Keith number generator
// Find all n-digit keith numbers in Java
public class FindKeithNumbersInJava {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("How many digits required in Keith number? ");
int len = scanner.nextInt();
if (len < 2) {
System.out.println("Keith numbers require minimum 2 digits");
} else {
long lowBound = (long) Math.pow(10, len - 1);
long upperBound = (long) Math.pow(10, len);
for (long l = lowBound; l < upperBound; l++) {
if (isKeithNumber(String.valueOf(l))) {
System.out.print(l + ", ");
}
}
}
scanner.close();
}
// Checks whether input number is a Keith number
public static boolean isKeithNumber(String input) {
int len = input.length();
// we keep only last n elements of the series
long[] series = new long[len];
for (int i = 0; i < len; i++) {
series[i] = Long.valueOf(input.substring(i, i + 1));
}
long next = 0;
long number = Long.valueOf(input);
while (next < number) {
next = 0;
for (int i = 0; i < len; i++) {
next += series[i];
if (i < len - 1) {
series[i] = series[i + 1]; // shift series to left
} else {
series[i] = next; // add new value to the series
}
}
if (next == number) {
return true;
}
}
return false;
}
}
Following is the sample output from the program,
java FindKeithNumbersInJava How many digits required in Keith number? 5 31331, 34285, 34348, 55604, 62662, 86935, 93993,
Problem: Find first n keith numbers using Java
The following java program finds first n Keith numbers. The program starts iteration from number 10 till n values are found. Please note that if you try to generate more than first 40 Keith numbers, the program may take a while to execute.
import java.util.Scanner;
// Find the first n keith numbers in Java
public class KeithNumberGenerator {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("How many keith numbers do you want? ");
int size = scanner.nextInt();
int counter = 0;
for (long l = 10; l < Long.MAX_VALUE; l++) {
if (isKeithNumber(String.valueOf(l))) {
System.out.print(l + ", ");
counter++;
if(counter==size) {
break;
}
}
}
scanner.close();
}
// Checks whether input number is a Keith number
public static boolean isKeithNumber(String input) {
int len = input.length();
// we keep only last n elements of the series
long[] series = new long[len];
for (int i = 0; i < len; i++) {
series[i] = Long.valueOf(input.substring(i, i + 1));
}
long next = 0;
long number = Long.valueOf(input);
while (next < number) {
next = 0;
for (int i = 0; i < len; i++) {
next += series[i];
if (i < len - 1) {
series[i] = series[i + 1]; // shift series to left
} else {
series[i] = next; // add new value to the series
}
}
if (next == number) {
return true;
}
}
return false;
}
}
Following is the sample output from the program,
java KeithNumberGenerator How many keith numbers do you want? 10 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537,