Finding Keith Numbers Beyond 10^ 26
Location
CSU 202
Start Date
25-4-2005 8:30 AM
End Date
25-4-2005 10:00 AM
Student's Major
Mathematics and Statistics
Student's College
Science, Engineering and Technology
Mentor's Name
Namyong Lee
Mentor's Department
Mathematics and Statistics
Mentor's College
Science, Engineering and Technology
Second Mentor's Name
Dean R. Kelley
Second Mentor's Department
Computer Information Science
Second Mentor's College
Science, Engineering and Technology
Description
A Keith number is an n-digit integer N with the following property: If a Fibonacci-like sequence (in which each term in the sequence is the sum of the n previous terms) is formed, with the first n terms being the decimal digits of the number N, then N itself occurs as a term in the sequence. For example, 197 is a Keith number since it generates the sequence
1, 9, 7, 17, 33, 57, 107,197 ... (3 digits Keith number)
The simple technique of finding the Keith number is a brute force technique. The fundamental problem with Keith numbers is that the computation time for discovering Keith numbers grows along with the number of digits in the number. For a number N with n digits there are approximately (10/ 3)n terms in the Fibonacci like sequence. Generating such a sequence would certainly take a long time.
Besides implementing an efficient algorithm to find the Keith numbers, the research will try to solve two mysteries.
1. It is still unknown whether there are an infinite number of Keith numbers as has been conjectured by Heuristic arguments. It appears that about 3 Keith numbers exist between each power of 10 but there is still no proof.
2. There is no Keith number for n = 10 so, Is n=10 the only number of digits for which there are no Keith numbers?
Finding Keith Numbers Beyond 10^ 26
CSU 202
A Keith number is an n-digit integer N with the following property: If a Fibonacci-like sequence (in which each term in the sequence is the sum of the n previous terms) is formed, with the first n terms being the decimal digits of the number N, then N itself occurs as a term in the sequence. For example, 197 is a Keith number since it generates the sequence
1, 9, 7, 17, 33, 57, 107,197 ... (3 digits Keith number)
The simple technique of finding the Keith number is a brute force technique. The fundamental problem with Keith numbers is that the computation time for discovering Keith numbers grows along with the number of digits in the number. For a number N with n digits there are approximately (10/ 3)n terms in the Fibonacci like sequence. Generating such a sequence would certainly take a long time.
Besides implementing an efficient algorithm to find the Keith numbers, the research will try to solve two mysteries.
1. It is still unknown whether there are an infinite number of Keith numbers as has been conjectured by Heuristic arguments. It appears that about 3 Keith numbers exist between each power of 10 but there is still no proof.
2. There is no Keith number for n = 10 so, Is n=10 the only number of digits for which there are no Keith numbers?
Recommended Citation
Shrestha, Sumit. "Finding Keith Numbers Beyond 10^ 26." Undergraduate Research Symposium, Mankato, MN, April 25, 2005.
https://cornerstone.lib.mnsu.edu/urs/2005/oral-session-B/5
