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

 

Logo


Hints
(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)
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.

LINKS

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

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

Adjacent sequences:  A162360 A162361 A162362 * A162364 A162365 A162366

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

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.)