| Name:||Keith Number Search|
| Current status:||partially completed|
| Categories of work:||Other|
| Project description:||I have a python program the uses BRUTE FORCE method to find Keith Numbers but it is TOO slow. So I found this paper that describes a seemingly simple algorithm to speed up the search.
my current BRUTE FORCE function that determines if number is repfibdigit (Keith Number):
def is_repfibdigit( number_to_test):
n = map(int,str(number_to_test))
while number_to_test > n:
if (number_to_test == n) & (number_to_test>9):
The concept of repfigits was introduced in by Keith. Given a n digit number D, first generate the Fibonacci sequence which starts with the n digits and has each successive term the sum of the n previous terms. The number D is called a repfigit if D appears in the resulting sequence. For example, 197 is a repfigit, since 197 is in the Fibonacci sequence (1, 9, 7, 17, 33, 57, 107, 197, 361, ...).
14 is another example (1,4,5,9,14)
19 is another example (1,9,10,19)
28 is another example (2,8,10,18,28)
To speed up the search changes the Fibonacci sequence search to a linear Diophantine equation. Note that the terms in a Fibonacci sequence are a linear combination of the original terms. For instance the sequence starting with 2 terms a ,b is (a , b , a +b , a +2b , 2a +3b , 3a +5b , 5a +8b , ...). Now suppose we suspect there is a 2 digit repfigit 10a +b that appears as the fifth term in the Fibonacci sequence. This means that
2a +3b = 10a +b , so 8a -2b = 0. Solving this equation for integer solutions between 0 and 9 yields solutions (0,0), (1,4) and (2,8). Discarding the trivial solution, these correspond to the repfigits 14 and 28.
Thus, to find n digit repfigits, we first generate the symbolic equations for the n digit Fibonacci sequence and determine what terms could have repfigits. (There are about 8 such terms for each n .) Then we solve the resulting linear Diophantine equations, restricting the values to the range 0 to 9.
i need the above algorithm implemented in python.. should be simple for someone who undertstands basic math (my weakness)
| Other details:||This SHOULD be fairly straight forward. |
|-No files uploaded yet-|
| Buyer name:||Laird Foret
| Location:||AL United States