This site is supported by donations to The OEIS Foundation.

# Keith sequence

A Keith sequence takes the ${\displaystyle {\mathcal {L}}}$ base ${\displaystyle b}$ digits of a positive integer ${\displaystyle n}$ and uses them to initialize a recurrence relation where each of the following terms is the sum of the previous ${\displaystyle {\mathcal {L}}}$ terms. For example, the Keith sequence for 197 in base 10 starts off with ${\displaystyle a_{1}=1}$, ${\displaystyle a_{2}=9}$, ${\displaystyle a_{3}=7}$; thereafter ${\displaystyle a_{m}=\sum _{i=m-3}^{m-1}a_{i}}$, (see A186830).

Technically, Keith sequences are infinite, but most people's interest peaks when ${\displaystyle n}$ is reached or gone past by. If ${\displaystyle n}$ occurs in ${\displaystyle a}$, then ${\displaystyle n}$ is called a Keith number. Binary Keith numbers are listed in A162724, decimal Keith numbers are in A007629.

Any Fibonacci number ${\displaystyle F_{n}>2}$ is a Keith number in base ${\displaystyle b=F_{n}-1}$. Since then ${\displaystyle F_{n}=b+1}$, the recurrence starts ${\displaystyle a_{1}=a_{2}=1}$ and is therefore the Fibonacci sequence A000045. Likewise ${\displaystyle b=F_{n}}$ is a Keith number as the recurrence is that of the Fibonacci numbers prefaced by 1, 0. Also, if ${\displaystyle n=kF_{n}<(F_{n})^{2}}$, then ${\displaystyle n}$ is a Keith number in base ${\displaystyle b=F_{n}}$ since the resulting recurrence consists of the Fibonacci numbers multiplied by ${\displaystyle k}$, prefaced by ${\displaystyle k}$, 0, e.g.,: in base 8, the number ${\displaystyle 56=7\times 8}$ 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, ${\displaystyle b}$ is a Keith number in its own base, thus A188201 gives the smallest base n Keith number greater than n.