A162363 Binary Keith numbers, excluding positive powers of 2.

1, 3, 143, 285, 569, 683, 1138, 1366, 2276, 154203, 308405, 616810, 678491, 1356981, 1480343, 2713962, 2960686, 2212558911, 4425117821, 8850235641, 17700471281

Offset: 1

Author

T. D. Noe, Jul 02 2009

Keywords

• base
• nonn

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.

Examples

			In binary, 143 = (1,0,0,0,1,1,1,1). Subsequent terms are 5,9,18,36,72,143.
		

Programs

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
				

Extensions

Corrected name T. D. Noe, Jul 11 2009

Typo in binary for 2212558911 corrected by Jaroslav Krizek, Dec 09 2015