In this section, we will explore the concept of Keith numbers and develop Java programs to determine if a given number is a Keith number. Checking whether a number is a Keith number
What is Keith Number?
A positive number X with n digits is referred to as a Keith number or repfigit number. This classification arises from a unique number sequence that is generated using the digits of X. The sequence begins with the first n terms being the digits of X, while the subsequent terms are recursively calculated as the sum of the previous n terms. Examples of Keith numbers include 197, 19, 742, 1537, and so on.
Keith Number Example
Let’s determine if the number 742 is a Keith number or not.
First, we separate each digit of the number, which gives us 7, 4, and 2.
Next, we calculate the next term of the series by adding these digits together (7 + 4 + 2), resulting in 13.
The series now becomes 7, 4, 2, and 13.
To find the next term, we add the last three terms of the series (2 + 4 + 13), which gives us 19.
The series now becomes 7, 4, 2, 13, 19.
We continue this process, adding the last three terms each time, to generate the subsequent terms of the series.
Eventually, we reach the number 742 as a term of the series.
Since we have obtained the same number (742) as a term of the series, we can conclude that the given number, 742, is a Keith number.
By observing the previous example, we can note that to determine if a number is a Keith number, we need to calculate the terms of the series until we obtain the same number that we started with as a term of the series.
Let’s take another example.
Steps to Find Keith Number
To check if a given number (X) is a Keith number, follow these steps:
- Read or initialize the number (X).
- Separate each digit from the given number (X).
- Add all the n-digits together to obtain the next term of the series.
- Add the last n terms of the series to find the next term.
- Repeat step 4 until we obtain a term that is the same as the original number we started with.
Keith Number Java Program
The logic behind identifying Keith numbers is relatively straightforward. We compute a series by adding the sum of the n previous numbers, where n is the number of digits in the input number. If, at any point, one of the computed numbers in the series matches the input number, it is considered a Keith number. The program terminates if the computed value exceeds the input number.
KeithNumberExample1.java
import java.util.*; class KeithNumberExample { //user-defined function that checks if the given number is Keith or not static boolean isKeith(int x) { //List stores all the digits of the X ArrayList<Integer> terms=new ArrayList<Integer>(); //n denotes the number of digits int temp = x, n = 0; //executes until the condition becomes false while (temp > 0) { //determines the last digit of the number and add it to the List terms.add(temp%10); //removes the last digit temp = temp/10; //increments the number of digits (n) by 1 n++; } //reverse the List Collections.reverse(terms); int next_term = 0, i = n; //finds next term for the series //loop executes until the condition returns true while (next_term < x) { next_term = 0; //next term is the sum of previous n terms (it depends on number of digits the number has) for (int j=1; j<=n; j++) next_term = next_term + terms.get(i-j); terms.add(next_term); i++; } //when the control comes out of the while loop, there will be two conditions: //either next_term will be equal to x or greater than x //if equal, the given number is Keith, else not return (next_term == x); } //driver code public static void main(String[] args) { //calling the user-defined method inside the if statement and print the result accordingly if (isKeith(19)) System.out.println("Yes, the given number is a Keith number."); else System.out.println("No, the given number is not a Keith number."); if(isKeith(742)) System.out.println("Yes, the given number is a Keith number."); else System.out.println("No, the given number is not a Keith number."); if(isKeith(4578)) System.out.println("Yes, the given number is a Keith number."); else System.out.println("No, the given number is not a Keith number."); } }
Output:
Yes, the given number is a Keith number. Yes, the given number is a Keith number. No, the given number is not a Keith number.
We will now develop a Java program to discover all the Keith numbers that have the same number of digits.
KeithNumberExample2.java
import java.util.Scanner; public class KeithNumberExample1 { public static void main(String args[]) { Scanner sc= new Scanner(System.in); System.out.print("Enter the number of digits the series must have: "); //reads an integer as length of the number from the user int numlen = sc.nextInt(); //checks if the length of the number is greater than 2 or not if (numlen < 2) { //prints if the above condition returns false System.out.println("The number must have at least 2 digits."); } //executes if the above condition returns true else { //calculates the lower bound from where the series starts long lowBound = (long) Math.pow(10, numlen - 1); //calculates the upper bound from where the series ends long upperBound = (long) Math.pow(10, numlen); for (long l = lowBound; l < upperBound; l++) { if (isKeith(String.valueOf(l))) { //prints all the Keith number between given range System.out.print(l + ", "); } } } sc.close(); } //function that checks whether the given number is Keith or not public static boolean isKeith(String input) { int numlen = input.length(); //keep track only the last three terms long[] series = new long[numlen]; for (int i = 0; i < numlen; i++) { series[i] = Long.valueOf(input.substring(i, i + 1)); } long next_term = 0; long number = Long.valueOf(input); while (next_term < number) { next_term = 0; //calculates next term of the series for (int i = 0; i < numlen; i++) { next_term = next_term + series[i]; if (i < numlen - 1) { //shift series to the left series[i] = series[i + 1]; } else { //add new value to the series series[i] = next_term; } } //compares the next term of the series with the number and returns boolean value accordingly if (next_term == number) { return true; } } return false; } }
Output 1:
Enter the number of digits the series must have: 5 31331, 34285, 34348, 55604, 62662, 86935, 93993,
Output 2:
Enter the number of digits the series must have: 2 14, 19, 28, 47, 61, 75,
In a similar manner, we can identify Keith numbers with d digits. The table below provides a summary of d-digit Keith numbers.
d | d-digit Keith Numbers |
---|---|
2 | 14, 19, 28, 47, 61, 75 |
3 | 197, 742 |
4 | 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909 |
5 | 31331, 34285, 34348, 55604, 62662, 86935, 93993 |
6 | 120284, 129106, 147640, 156146, 174680, 183186, 298320, 355419, 694280, 925993 |
7 | 1084051, 7913837 |
8 | 11436171, 33445755, 44121607 |
9 | 129572008, 251133297 |
10 | (none) |
11 | 24769286411, 96189170155 |
12 | 171570159070, 202366307758, 239143607789, 296658839738 |
13 | 1934197506555, 8756963649152 |
14 | 43520999798747, 74596893730427, 97295849958669 |
15 | 120984833091531, 270585509032586, 754788753590897 |
16 | 3621344088074041, 3756915124022254, 4362827422508274 |
17 | 11812665388886672, 14508137312404344, 16402582054271374, 69953250322018194, 73583709853303061 |
18 | 119115440241433462, 166308721919462318, 301273478581322148 |
19 | 1362353777290081176, 3389041747878384662, 5710594497265802190, 5776750370944624064, 6195637556095764016 |
20 | 12763314479461384279, 27847652577905793413, 45419266414495601903 |
21 | 855191324330802397989 |
22 | 7657230882259548723593 |
23 | 26842994422637112523337, 36899277593852609997403, 61333853602129819189668 |
24 | 229146413136585558461227 |
25 | 9838678687915198599200604 |
To discover more insights about Keith Numbers in Java, make sure to follow tutorials.freshersnow.com.