login
Numbers n whose binary expansion does not begin with 11.
10

%I #42 Jul 26 2023 21:28:37

%S 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,

%T 40,41,42,43,44,45,46,47,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,

%U 79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,128,129

%N Numbers n whose binary expansion does not begin with 11.

%H Robert Israel, <a href="/A004761/b004761.txt">Table of n, a(n) for n = 1..10000</a>

%F 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

%F For n > 0, a(n) = 1/2 * (4n - 3 - A006257(n-1)). - _Ralf Stephan_, Sep 16 2003

%F 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

%F a(2^m+k) = A004760(2^m+k) - 2^m, m >= 0, 0 <= k < 2^m. - _Yosu Yurramendi_, Aug 08 2016

%F 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

%p f:= proc(n) option remember; if n::odd then procname(n-1)+1 else 2*procname(n/2+1) fi

%p end proc:

%p f(1):= 0: f(2):= 1:

%p map(f, [$1..100]); # _Robert Israel_, Mar 31 2017

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

%o (PARI) is(n)=n^2==n || !binary(n)[2] \\ _Charles R Greathouse IV_, Mar 07 2013

%o (PARI) a(n) = if(n<=2,n-1, n-=2; n + 1<<logint(n,2)); \\ _Kevin Ryde_, Apr 14 2021

%o (R)

%o maxrow <- 8 # by choice

%o b01 <- 1

%o for(m in 0:maxrow){

%o b01 <- c(b01,rep(1,2^(m+1))); b01[2^(m+1):(2^(m+1)+2^m-1)] <- 0

%o }

%o (a <- c(0,1,which(b01 == 0)))

%o # _Yosu Yurramendi_, Mar 30 2017

%o (Python)

%o def A004761(n): return m+(1<<m.bit_length()-1) if (m:=n-2) else n-1 # _Chai Wah Wu_, Jul 26 2023

%Y Apart from initial terms, same as A004754.

%K nonn,easy,base

%O 1,3

%A _N. J. A. Sloane_