|
|
A063037
|
|
Numbers without 3 consecutive equal binary digits.
|
|
11
|
|
|
0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 18, 19, 20, 21, 22, 25, 26, 27, 36, 37, 38, 41, 42, 43, 44, 45, 50, 51, 52, 53, 54, 73, 74, 75, 76, 77, 82, 83, 84, 85, 86, 89, 90, 91, 100, 101, 102, 105, 106, 107, 108, 109, 146, 147, 148, 149, 150, 153, 154, 155, 164, 165, 166
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Also 0 together with the indices of the compositions that have no parts larger than 2. For the definition of the index of a composition see A298644.
For example, 105 is in the sequence since its binary form is 1101001 and the composition [2,1,1,2,1] has no parts larger than 2.
On the other hand, 132 is not in the sequence since its binary form is 10000100 and the composition [1,4,1,2] has a part larger than 2.
The command c(n) from the Maple program yields the composition having index n. (End)
The sequence contains A000045(n+1) positive terms with binary length n. - Rémy Sigrist, Sep 30 2022
|
|
LINKS
|
|
|
FORMULA
|
It appears (but has not yet been proved) that the terms of {a(n)} can be computed recursively as follows. Let {c(i)} be defined for i >= 4 by c(i) = 2c(i-1) + 1, if i is a multiple of 3, else c(i) = 2c(i-1) - 1, with c(4) = 1. I.e., {c(i)} = {1,1,3,5,9,19,37,73,147,...}, for i=4,5,6,... . Let a(1)=1, a(2)=2, a(3)=3. For n > 3, choose k so that F(k)-2 < n <= F(k+1)-2, where F(k) denotes the k-th Fibonacci number (A000045). Then a(n) = c(k) + 2a(F(k)-2) - a(2F(k)-n-3). This has been verified for n up to 1100. - John W. Layman, May 26 2009
|
|
EXAMPLE
|
The binary representation of 9 (1001) has no 3 consecutive equal digits.
|
|
MAPLE
|
isA063037 := proc(n)
local bdgs, rep, d, i ;
if n = 0 then
return true;
end if;
bdgs := convert(n, base, 2) ;
rep := 1;
d := op(1, bdgs) ;
for i from 2 to nops(bdgs) do
if op(i, bdgs) = op(i-1, bdgs) then
rep := rep+1 ;
else
rep :=1 ;
end if ;
if rep > 2 then
return false;
end if;
end do:
return true ;
end proc:
for n from 0 to 50 do
if isA063037(n) then
printf("%d, ", n) ;
end if;
# Second Maple program:
Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: A := {0}: for n to 250 do if `subset`(convert(c(n), set), {1, 2}) then A := `union`(A, {n}) else end if end do: A; # most of this Maple program is due to W. Edwin Clark. - Emeric Deutsch, Jan 27 2018
|
|
MATHEMATICA
|
Select[Range[0, 168], AllTrue[Length /@ Split@ IntegerDigits[#, 2], # < 3 &] &] (* Michael De Vlieger, Aug 20 2017 *)
|
|
PROG
|
(PARI) { n=0; for (m=0, 10^9, x=m; t=1; b=2; while (x>0, d=x-2*(x\2); x\=2; if (d==b, c++; if (c==3, t=x=0), b=d; c=1)); if (t, write("b063037.txt", n++, " ", m); if (n==1000, break)) ) } \\ Harry J. Smith, Aug 16 2009
(PARI) a(n) = { n--; if (n<=1, return (n), my (s=1); for (i=1, oo, my (f=fibonacci(i+1)); if (n<s+f, return (2^i-1-a(2*s-n)), s+=f))) } \\ Rémy Sigrist, Sep 30 2022
(Python)
from itertools import count, islice
def A063037_gen(startvalue=0): # generator of terms >= startvalue
return filter(lambda n: not ('000' in (s:=bin(n)[2:]) or '111' in s), count(max(0, startvalue)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|