login
a(n) = a(floor(n/2)) + a(floor(n/4)) + a(floor(n/8)) + ... starting with a(0)=0 and a(1)=1.
24

%I #18 Jul 01 2022 05:33:25

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

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

%U 16,16,16,16,16,16,16,16,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32

%N a(n) = a(floor(n/2)) + a(floor(n/4)) + a(floor(n/8)) + ... starting with a(0)=0 and a(1)=1.

%H Michael De Vlieger, <a href="/A072376/b072376.txt">Table of n, a(n) for n = 0..10000</a>

%F For n > 1: a(n) = msb(n)/2 = 2^floor(log_2(n)-1) = 2*a(floor(n/2)).

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

%t lim = 100; CoefficientList[Series[1/(2 - 2 x) (2 x - x^2 + Sum[ 2^(k - 1) x^2^k, {k, Floor@ Log2@ lim}]), {x, 0, lim}], x] (* _Michael De Vlieger_, Jan 26 2016 *)

%o (PARI) a(n)=if(n<2, return(n)); 2^logint(n\2,2) \\ _Charles R Greathouse IV_, Jan 26 2016

%o (Python)

%o def A072376(n): return n if n < 2 else 1 << n.bit_length()-2 # _Chai Wah Wu_, Jun 30 2022

%Y Cf. A011782, A022825, A053644, A062383.

%K easy,nonn

%O 0,5

%A _Henry Bottomley_, Jul 19 2002