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?

This document is currently not available here.

Share

COinS
 
Apr 25th, 8:30 AM Apr 25th, 10:00 AM

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