OFFSET
1,2
COMMENTS
a(n) is at least Omega(n), at most O(n*log(n)).
The empirical approximation n*(log(n)/2 + exp(1)) is startlingly close to tight, compared with many increasing upper bounds.
LINKS
Alex Meiburg, Table of n, a(n) for n = 1..20000
FORMULA
a(n+1) = a(n) + A261461(a(n)). - Reinhard Zumkeller, Aug 30 2015
EXAMPLE
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)
MATHEMATICA
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];
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 *)
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 *)
PROG
(Java)
public static void main(String[] args) {
int a=1;
for(int iter=0; iter<100; iter++){
System.out.print(a+", ");
int inc;
for(inc=1; contains(a, inc); inc++);
a+=inc;
}
}
static boolean contains(int a, int test){
int mask=(Integer.highestOneBit(test)<<1)-1;
while(a >= test){
if((a & mask) == test) return true;
a >>= 1;
}
return false;
}
(Haskell)
a260273 n = a260273_list !! (n-1)
a260273_list = iterate (\x -> x + a261461 x) 1
-- Reinhard Zumkeller, Aug 30 2015, Aug 17 2015
(Python)
A260273_list, a = [1], 1
for i in range(10**3):
b, s = 1, format(a, 'b')
while format(b, 'b') in s:
b += 1
a += b
s = format(a, 'b')
A260273_list.append(a) # Chai Wah Wu, Aug 26 2015
CROSSREFS
KEYWORD
nonn,base,easy,nice
AUTHOR
Alex Meiburg, Jul 22 2015
STATUS
approved