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

Links

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

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

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 *)

Prog

(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<<logint(n, 2)); \\ Kevin Ryde, Apr 14 2021
(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
(Python)
def A004761(n): return m+(1<<m.bit_length()-1) if (m:=n-2) else n-1 # Chai Wah Wu, Jul 26 2023

Crossrefs

Apart from initial terms, same as A004754.

Sequence in context: A175141 A072756 A325429 * A004754 A322014 A010450

Adjacent sequences: A004758 A004759 A004760 * A004762 A004763 A004764

Keyword

nonn,easy,base

Author

N. J. A. Sloane

Status

approved