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