login
A162363
Binary Keith numbers, excluding positive powers of 2.
2
1, 3, 143, 285, 569, 683, 1138, 1366, 2276, 154203, 308405, 616810, 678491, 1356981, 1480343, 2713962, 2960686, 2212558911, 4425117821, 8850235641, 17700471281
OFFSET
1,2
COMMENTS
This sequence uses the binary expansion of n rather than the decimal expansion used in the usual Keith numbers, A007629. A number n (having a t-bit binary representation) is in this sequence if n is a term in the t-step Fibonacci-like series beginning with the t bits of n. See the example below.
Let the bits of n be b(i) for i=1 to t. Then b(t+1) = sum_{i=1..t} b(i). Subsequent terms are b(t+k+1) = 2*b(t+k) - b(k) for k=1,2,3,.... (This is equivalent to, but faster than, the usual method of adding the previous t terms to find the next term.) Due to the growth rate of the numbers in the series, the term equal to n occurs on or before position 2t in the series.
Terms in this sequence fall into families having the same number of 1 bits. For instance, 143, 285, 569, 1138, and 2276 all have 5 bits set. Numbers in each family are either 2x or 2x-1, where x is the previous number in the family. The binary expansion of each number in family f begins with f-1 (in binary).
This sequence is infinite because for any odd prime (or base-2 pseudoprime, A001567) p=2k+1, we can create a family of numbers with 2^(2k)+1 bits set. The first number in that family is 2^c + c(2^c-2)/(4^p-1) + 1, where c=2^p-1. In binary, this number is a 1 followed by a repeating pattern of p zeros and p ones and terminated by 1, for a total of 2^p bits. For example, 2212558911 is 10000011111000001111100000111111 in binary.
EXAMPLE
In binary, 143 = (1,0,0,0,1,1,1,1). Subsequent terms are 5,9,18,36,72,143.
MAPLE
isA162363 := proc(n)
local L, t, a ;
if numtheory[factorset](n) = {2} then
return false;
end if;
L := ListTools[Reverse](convert(n, base, 2)) ;
t := nops(L) ;
while true do
a := add(op(-i, L), i=1..t) ;
L := [op(L), a] ;
if a > n then
return false;
elif a = n then
return true;
end if;
end do:
end proc:
for n from 1 do
if isA162363(n) then
printf("%d, \n", n);
end if;
end do: # R. J. Mathar, Jan 12 2016
MATHEMATICA
IsKeith2[n_Integer] := Module[{b, s}, b=IntegerDigits[n, 2]; s=Total[b]; If[s<=1, n==1, k=1; While[s=2*s-b[[k]]; s<n, k++ ]; s== n]]; Select[Range[3000], IsKeith2[ # ]&]
CROSSREFS
Sequence in context: A037121 A279923 A195937 * A102965 A278310 A195936
KEYWORD
base,nonn
AUTHOR
T. D. Noe, Jul 02 2009
EXTENSIONS
Corrected name T. D. Noe, Jul 11 2009
Typo in binary for 2212558911 corrected by Jaroslav Krizek, Dec 09 2015
STATUS
approved