#### Event Title

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