login
A260273
Successively add the smallest nonzero binary number that is not a substring.
14
1, 3, 5, 8, 11, 15, 17, 20, 23, 27, 31, 33, 36, 39, 44, 51, 56, 61, 65, 68, 71, 76, 81, 84, 87, 91, 95, 99, 104, 111, 115, 120, 125, 129, 132, 135, 140, 145, 148, 151, 157, 165, 168, 171, 175, 179, 186, 190, 194, 199, 204, 209, 216, 223, 227, 232, 241, 246
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.
A261644(n) = A062383(a(n)) - a(n). - Reinhard Zumkeller, Aug 30 2015
LINKS
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
See A261922 and A261461 for the smallest missing number function; also A261923, A262279, A261281.
See also A261396 (when a(n) just passes a power of 2), A261416 (the limiting behavior just past a power of 2).
First differences are A261018.
A262288 is the decimal analog.
Sequence in context: A062484 A348450 A360628 * A022433 A284442 A335860
KEYWORD
nonn,base,easy,nice
AUTHOR
Alex Meiburg, Jul 22 2015
STATUS
approved