The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)



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.


Table of n, a(n) for n=1..21.


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


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


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[ # ]&]


Sequence in context: A037121 A279923 A195937 * A102965 A278310 A195936

Adjacent sequences:  A162360 A162361 A162362 * A162364 A162365 A162366




T. D. Noe, Jul 02 2009


Corrected name T. D. Noe, Jul 11 2009

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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 17:20 EST 2020. Contains 332307 sequences. (Running on oeis4.)