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,2

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

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

Mathematica

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

Prog

(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 (n<s+f, return (2^i-1-a(2*s-n-1)), s+=f))) } \\ Rémy Sigrist, Sep 30 2022

Crossrefs

Cf. A000073, A063037, A000975.

Sequence in context: A048339 A023783 A344022 * A247764 A302140 A039698

Adjacent sequences: A166532 A166533 A166534 * A166536 A166537 A166538

Keyword

nonn

Author

John W. Layman, Oct 16 2009

Status

approved