A053644 - OEIS

%I #102 Jul 28 2022 09:07:06

%S 0,1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,16,16,16,16,

%T 16,16,16,16,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,

%U 32,32,32,32,32,32,32,32,32,32,32,32,32,64,64,64,64,64,64,64,64,64,64,64

%N Most significant bit of n, msb(n); largest power of 2 less than or equal to n; write n in binary and change all but the first digit to zero.

%C Except for the initial term, 2^n appears 2^n times. - _Lekraj Beedassy_, May 26 2005

%C a(n) is the smallest k such that row k in triangle A265705 contains n. - _Reinhard Zumkeller_, Dec 17 2015

%C a(n) is the sum of totient function over powers of 2 <= n. - _Anthony Browne_, Jun 17 2016

%C Given positive n, reverse the bits of n and divide by 2^floor(log_2 n). Numerators are in A030101. Ignoring the initial 0, denominators are in this sequence. - _Alonso del Arte_, Feb 11 2020

%H Reinhard Zumkeller, <a href="/A053644/b053644.txt">Table of n, a(n) for n = 0..10000</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%F a(n) = a(floor(n / 2)) * 2.

%F a(n) = 2^A000523(n).

%F From n >= 1 onward, A053644(n) = A062383(n)/2.

%F a(0) = 0, a(1) = 1 and a(n+1) = a(n)*floor(n/a(n)). - _Benoit Cloitre_, Aug 17 2002

%F G.f.: 1/(1 - x) * (x + Sum_{k >= 1} 2^(k - 1)*x^2^k). - _Ralf Stephan_, Apr 18 2003

%F a(n) = (A003817(n) + 1)/2 = A091940(n) + 1. - _Reinhard Zumkeller_, Feb 15 2004

%F a(n) = Sum_{k = 1..n} (floor(2^k/k) - floor((2^k - 1)/k))*A000010(k). - _Anthony Browne_, Jun 17 2016

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

%p a:= n-> 2^ilog2(n):

%p seq(a(n), n=0..80);  # _Alois P. Heinz_, Dec 20 2016

%t A053644[n_] := 2^(Length[ IntegerDigits[n, 2]] - 1); A053644[0] = 0; Table[A053644[n], {n, 0, 74}] (* _Jean-François Alcover_, Dec 01 2011 *)

%t nv[n_] := Module[{c = 2^n}, Table[c, {c}]]; Join[{0}, Flatten[Array[nv, 7, 0]]] (* _Harvey P. Dale_, Jul 17 2012 *)

%o (Haskell)

%o a053644 n = if n <= 1 then n else 2 * a053644 (div n 2)

%o -- _Reinhard Zumkeller_, Aug 28 2014

%o a053644_list = 0 : concat (iterate (\zs -> map (* 2) (zs ++ zs)) [1])

%o -- _Reinhard Zumkeller_, Dec 08 2012, Oct 21 2011, Oct 17 2010

%o (PARI) a(n)=my(k=1);while(k<=n,k<<=1);k>>1 \\ _Charles R Greathouse IV_, May 27 2011

%o (PARI) a(n) = if(!n, 0, 2^exponent(n)) \\ _Iain Fox_, Dec 10 2018

%o (Python)

%o def a(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1) # _Indranil Ghosh_, May 25 2017

%o (Magma) [0] cat [2^Ilog2(n): n in [1..90]]; // _Vincenzo Librandi_, Dec 11 2018

%o (Scala) (0 to 127).map(Integer.highestOneBit(_)) // _Alonso del Arte_, Feb 26 2020

%o (Python)

%o def A053644(n): return 1<<n.bit_length()-1 if n else 0 # _Chai Wah Wu_, Jul 27 2022

%Y See A000035 for least significant bit(n).

%Y MASKTRANS transform of A055975 (prepended with 0), MASKTRANSi transform of A048678.

%Y Bisection of A065267, A065279, A065291, A072376.

%Y First differences of A063915. Cf. A076877, A073121.

%Y This is Guy Steele's sequence GS(5, 5) (see A135416).

%Y Equals for n >= 1 the first right hand column of A160464. - _Johannes W. Meijer_, May 24 2009

%Y Diagonal of A088370. - _Alois P. Heinz_, Oct 28 2011

%Y Cf. A265705, A000010.

%K nonn,nice,easy

%O 0,3

%A _Henry Bottomley_, Mar 22 2000