cp's OEIS Frontend

A162363 Binary Keith numbers, excluding positive powers of 2.

%I A162363 #9 Jan 12 2016 12:14:50
%S A162363 1,3,143,285,569,683,1138,1366,2276,154203,308405,616810,678491,
%T A162363 1356981,1480343,2713962,2960686,2212558911,4425117821,8850235641,
%U A162363 17700471281
%N A162363 Binary Keith numbers, excluding positive powers of 2.
%C A162363 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.
%C A162363 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.
%C A162363 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).
%C A162363 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.
%e A162363 In binary, 143 = (1,0,0,0,1,1,1,1). Subsequent terms are 5,9,18,36,72,143.
%p A162363 isA162363 := proc(n)
%p A162363     local L,t,a ;
%p A162363     if numtheory[factorset](n) = {2} then
%p A162363         return false;
%p A162363     end if;
%p A162363     L := ListTools[Reverse](convert(n,base,2)) ;
%p A162363     t :=  nops(L) ;
%p A162363     while true do
%p A162363         a := add(op(-i,L),i=1..t) ;
%p A162363         L := [op(L),a] ;
%p A162363         if a > n then
%p A162363             return false;
%p A162363         elif a = n then
%p A162363             return true;
%p A162363         end if;
%p A162363     end do:
%p A162363 end proc:
%p A162363 for n from 1 do
%p A162363     if isA162363(n) then
%p A162363         printf("%d,\n",n);
%p A162363     end if;
%p A162363 end do: # _R. J. Mathar_, Jan 12 2016
%t A162363 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[ # ]&]
%K A162363 base,nonn
%O A162363 1,2
%A A162363 _T. D. Noe_, Jul 02 2009
%E A162363 Corrected name _T. D. Noe_, Jul 11 2009
%E A162363 Typo in binary for 2212558911 corrected by _Jaroslav Krizek_, Dec 09 2015