A166535 Positive integers whose binary representation does not contain a run of more than three consecutive 0's or 1's.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90

Offset: 1

Author

John W. Layman, Oct 16 2009

Keywords

• nonn

Comments

A179970 is a subsequence. - Reinhard Zumkeller, Aug 04 2010

There are A000073(n+2) terms with binary length n. - Rémy Sigrist, Sep 30 2022

Links

• R. Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000073, A063037, A000975.

Programs

Mathematica

Select[Range[100],Max[Length/@Split[IntegerDigits[#,2]]]<4&] (* Harvey P. Dale, Aug 01 2020 *)

PARI

tribonacci(n) = ([0,1,0; 0,0,1; 1,1,1]^n)[2,1]
a(n) = { if (n<=4, return (n), my (s=1); for (i=1, oo, my (f=tribonacci(i+2)); i
f (nRémy Sigrist, Sep 30 2022

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 >= 5 by c(i)=2c(i-1)+1 if i is congruent to 2 mod 4, else c(i)=2c(i-1)-1. I.e., {c(i)}={1,3,5,9,17,35,...} for i=5,6,7,... . Let a(n)=n for n=1,2,...,7. For n>7, choose k so that s(k) < n < s(k+1), where s(k) = Sum_{j=3..k} t(j) with t(j) being the j-th term of the tribonacci sequence A000073 (with initial terms t(0)=0, t(1)=0, t(2)=1). Then a(n) = c(k) + 2a(s(k)) - a(2s(k)+1). This has been verified for n up to 2400.

{i: A043276(i) <= 3}. - R. J. Mathar, Jun 04 2021