A004761 Numbers n whose binary expansion does not begin with 11.

0, 1, 2, 4, 5, 8, 9, 10, 11, 16, 17, 18, 19, 20, 21, 22, 23, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 128, 129

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• base

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Apart from initial terms, same as A004754.

Programs

Maple

f:= proc(n) option remember; if n::odd then procname(n-1)+1 else 2*procname(n/2+1) fi
end proc:
f(1):= 0: f(2):= 1:
map(f, [$1..100]); # Robert Israel, Mar 31 2017

Mathematica

Select[Range[0, 140], # <= 2 || Take[IntegerDigits[#, 2], 2] != {1, 1} &] (* Michael De Vlieger, Aug 03 2016 *)

PARI

is(n)=n^2==n || !binary(n)[2] \\ Charles R Greathouse IV, Mar 07 2013

PARI

a(n) = if(n<=2,n-1, n-=2; n + 1<Kevin Ryde, Apr 14 2021

Python

def A004761(n): return m+(1<Chai Wah Wu, Jul 26 2023

R

maxrow <- 8 # by choice
b01 <- 1
for(m in 0:maxrow){
  b01 <- c(b01,rep(1,2^(m+1))); b01[2^(m+1):(2^(m+1)+2^m-1)] <- 0
}
(a <- c(0,1,which(b01 == 0)))
# Yosu Yurramendi, Mar 30 2017

Formula

a(1)=0, a(2)=1 and for k>1: a(2*k-1) = a(2*k-2)+1, a(2*k) = 2*a(k+1). - Reinhard Zumkeller, Jan 09 2002, corrected by Robert Israel, Mar 31 2017

For n > 0, a(n) = 1/2 * (4n - 3 - A006257(n-1)). - Ralf Stephan, Sep 16 2003

a(1) = 0, a(2) = 1, a(2^m+k+2) = 2^(m+1)+k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Jul 30 2016

a(2^m+k) = A004760(2^m+k) - 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016

G.f. g(x) satisfies g(x) = 2*(1+x)*g(x^2)/x^2 - x^2*(1-x^2-x^3)/(1-x^2). - Robert Israel, Mar 31 2017