Check Keith Number in Java
Problem
A Keith number is one that reappears in a Fibonacci-like sequence seeded by its own digits, where each new term is the sum of the previous digit-count terms.
Given a number, determine whether it is a Keith number.
Java Program
import java.util.ArrayList;
import java.util.List;
public class KeithNumberCheck {
public static void main(String[] args) {
int n = 197;
String digitsStr = String.valueOf(n);
int digitCount = digitsStr.length();
List<Integer> sequence = new ArrayList<>();
for (char c : digitsStr.toCharArray()) {
sequence.add(c - '0'); // seed the sequence with each digit of n
}
int next = 0;
while (next < n) {
next = 0;
int size = sequence.size();
// sum the last `digitCount` terms already generated
for (int i = size - digitCount; i < size; i++) {
next += sequence.get(i);
}
sequence.add(next);
}
System.out.println(n + " is a Keith number: " + (next == n));
}
}Output
Core Logic
Seeding a growing sequence with the number's own digits, then repeatedly summing the last `digits` terms to generate the next one, reproduces the exact rule a Keith number has to satisfy — the number itself has to eventually reappear.
- 1
sequencestarts out holding each digit ofnindividually, in order — for197, that's[1, 9, 7]. - 2Each new term sums the last
digitCountentries already in the sequence, the same window size as the number of seed digits. - 3That new term is appended, and the loop repeats — generating
17, 33, 57, 107, 197for this example — until a term reaches or passesn. - 4The loop stops as soon as a generated term is no longer less than
n, and the final check is whether that term equalsnexactly.
197, the sequence grows as 1, 9, 7, 17, 33, 57, 107, 197 — the last term generated lands exactly on 197, confirming it's a Keith number.Key Point: The sequence only ever needs to grow until it reaches or exceeds n — since each term is roughly the sum of the last few, growth is fast enough that this rarely takes many steps, even for larger numbers.
Why: The sequence has to grow until a term reaches or passes n, and since consecutive terms grow at a similar rate to Fibonacci numbers, only a logarithmic number of terms need to be generated and stored.