A260273 - OEIS

%I #54 Aug 10 2016 00:29:45

%S 1,3,5,8,11,15,17,20,23,27,31,33,36,39,44,51,56,61,65,68,71,76,81,84,

%T 87,91,95,99,104,111,115,120,125,129,132,135,140,145,148,151,157,165,

%U 168,171,175,179,186,190,194,199,204,209,216,223,227,232,241,246

%N Successively add the smallest nonzero binary number that is not a substring.

%C a(n) is at least Omega(n), at most O(n*log(n)).

%C The empirical approximation n*(log(n)/2 + exp(1)) is startlingly close to tight, compared with many increasing upper bounds.

%C A261644(n) = A062383(a(n)) - a(n). - _Reinhard Zumkeller_, Aug 30 2015

%H Alex Meiburg, <a href="/A260273/b260273.txt">Table of n, a(n) for n = 1..20000</a>

%F a(n+1) = a(n) + A261461(a(n)). - _Reinhard Zumkeller_, Aug 30 2015

%e Begin with a(1)=1, in binary, "1". This contains the string "1" but not "10", so we add 2. Thus a(2)=1+2=3. This also contains "1" but not "10", so we move to a(3)=3+2=5. This contains "1" and "10" but not "11", so we add 3. Thus a(4)=5+3=8. (See A261018 for the successive numbers that are added. - _N. J. A. Sloane_, Aug 17 2015)

%t sublistQ[L1_, L2_] := Module[{l1 = Length[L1], l2 = Length[L2], k}, If[l2 <= l1, For[k = 1, k <= l1 - l2 + 1, k++, If[L1[[k ;; k + l2 - 1]] == L2, Return[True]]]]; False];

%t a[1] = 1; a[n_] := a[n] = Module[{bb = IntegerDigits[a[n-1], 2], k}, For[k = 1, sublistQ[bb, IntegerDigits[k, 2]], k++]; a[n-1] + k]; Table[a[n], {n, 1, 60}] (* _Jean-François Alcover_, Apr 01 2016 *)

%t NestList[Function[k, k + FromDigits[#, 2] &@ SelectFirst[IntegerDigits[Range[2^8], 2], Length@ SequencePosition[IntegerDigits[k, 2], #] == 0 &]], 1, 64] (* _Michael De Vlieger_, Apr 01 2016, Version 10.1 *)

%o (Java)

%o public static void main(String[] args) {

%o    int a=1;

%o    for(int iter=0;iter<100;iter++){

%o        System.out.print(a+", ");

%o        int inc;

%o        for(inc=1; contains(a,inc); inc++);

%o        a+=inc;

%o    }

%o }

%o static boolean contains(int a,int test){

%o    int mask=(Integer.highestOneBit(test)<<1)-1;

%o    while(a >= test){

%o        if((a & mask) == test) return true;

%o        a >>= 1;

%o    }

%o    return false;

%o }

%o (Haskell)

%o a260273 n = a260273_list !! (n-1)

%o a260273_list = iterate (\x -> x + a261461 x) 1

%o -- _Reinhard Zumkeller_, Aug 30 2015, Aug 17 2015

%o (Python)

%o A260273_list, a = [1], 1

%o for i in range(10**3):

%o     b, s = 1, format(a,'b')

%o     while format(b,'b') in s:

%o         b += 1

%o     a += b

%o     s = format(a,'b')

%o     A260273_list.append(a) # _Chai Wah Wu_, Aug 26 2015

%Y See A261922 and A261461 for the smallest missing number function; also A261923, A262279, A261281.

%Y Cf. A030308, A261015, A261016, A261017, A261019.

%Y See also A261396 (when a(n) just passes a power of 2), A261416 (the limiting behavior just past a power of 2).

%Y First differences are A261018.

%Y A262288 is the decimal analog.

%Y Cf. A261644, A062383.

%K nonn,base,easy,nice

%O 1,2

%A _Alex Meiburg_, Jul 22 2015