This site is supported by donations to The OEIS Foundation.

Keith sequence

From OeisWiki
Jump to: navigation, search

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.