This site is supported by donations to The OEIS Foundation.
Keith sequence
A Keith sequence takes the base digits of a positive integer and uses them to initialize a recurrence relation where each of the following terms is the sum of the previous terms. For example, the Keith sequence for 197 in base 10 starts off with , , ; thereafter , (see A186830).
Technically, Keith sequences are infinite, but most people's interest peaks when is reached or gone past by. If occurs in , then is called a Keith number. Binary Keith numbers are listed in A162724, decimal Keith numbers are in A007629.
Any Fibonacci number is a Keith number in base . Since then , the recurrence starts and is therefore the Fibonacci sequence A000045. Likewise is a Keith number as the recurrence is that of the Fibonacci numbers prefaced by 1, 0. Also, if , then is a Keith number in base since the resulting recurrence consists of the Fibonacci numbers multiplied by , prefaced by , 0, e.g.,: in base 8, the number is a Keith number, since the recurrence is then 7, 0, 7, 7, 14, 21, 35, 56, ... (and we verify that dividing that by 7 we get 1, 0, 1, 1, 2, 3, 5, 8, etc.)
The following table lists Keith sequences for some small base 10 Keith numbers.
14 | 1, 4, 5, 9, 14, ... | A000285 |
19 | 1, 9, 10, 19, ... | A022099 |
28 | 2, 8, 10, 18, 28, ... | |
47 | 4, 7, 11, 18, 29, 47, ... | A000032 |
61 | 6, 1, 7, 8, 15, 23, 38, 61, ... | |
75 | 7, 5, 12, 17, 29, 46, 75, ... | |
197 | 1, 9, 7, 17, 33, 57, 107, 197, ... | A186830 |
742 | 7, 4, 2, 13, 19, 34, 66, 119, 219, 404, 742, ... |
The following table lists some small Keith numbers in other bases.
b | Keith numbers | |
A162724 | 2 | 2, 3, 4, 8, 16, 32, 64, 128, 143, 256, 285, 512, 569, 683, ... |
A188195 | 3 | 3, 5, 6, 7, 57, 102, 127, 206, 217, 677, 805, 840, ... |
A188196 | 4 | 5, 7, 10, 15, 18, 29, 47, 113, 163, 269, ... |
A187713 | 5 | 5, 9, 10, 11, 13, 15, 20, 22, 31, 40, 43, 53, 62, 71, 84, 93, 124, 154, 221, 483, ... |
A188197 | 6 | 8, 11, 16, 27, 37, 44, 74, 88, 111, 148, 185, 409, 526, ... |
A188198 | 7 | 8, 13, 16, 19, 24, 32, 40, 48, 57, 114, 125, 145, 171, 228, 285, 329, 342, 589, ... |
A188199 | 8 | 8, 11, 15, 16, 22, 24, 32, 37, 40, 48, 56, 59, 92, 123, 200, 251, 257, 400, 457, 893, ... |
A188200 | 9 | 17, 21, 25, 42, 67, 81, 96, 101, 149, 162, 173, 202, 243, 303, 324, 346, 404, 405, 486, 519, 567, 648, 692, 732, 857, ... |
A007629 | 10 | 14, 19, 28, 47, 61, 75, 197, 742, ... |
11 | 13, 21, 26, 31, 39, 45, 52, 65, 83, 90, 262, 529, 545, ... | |
12 | 13, 17, 23, 26, 34, 37, 39, 52, 57, 65, 74, 78, 91, 104, 111, 117, 130, 143, 173, 305, 346, 581, 610, 928, ... |
As mentioned above, is a Keith number in its own base, thus A188201 gives the smallest base n Keith number greater than n.