A037809 Number of i such that d(i) <= d(i-1), where Sum_{i=0..m} d(i)*2^i is the base-2 representation of n.

0, 0, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 3, 2, 2, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 3, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 3, 4, 3, 3, 3, 4, 4, 4, 3, 4, 4, 4, 4, 5, 5, 5, 4, 5, 4, 4, 4, 5, 4, 4, 3, 4, 4, 4, 4, 5, 4, 4, 3, 4, 3, 3, 3, 4, 4, 4, 3

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• base

Examples

			The base-2 representation of n=4 is 100 with d(0)=0, d(1)=0, d(2)=1. Only d(1) <= d(0) is true, so a(4)=1. - _R. J. Mathar_, Oct 16 2015
		

Links

• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions

Crossrefs

Cf. A033265.

Programs

Maple

A037809 := proc(n)
    a := 0 ;
    dgs := convert(n,base,2);
    for i from 2 to nops(dgs) do
        if op(i,dgs)<=op(i-1,dgs) then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Oct 16 2015

Formula

From Ralf Stephan, Oct 05 2003: (Start)

G.f.: -x/(1-x) + 1/(1-x) * Sum_{k>=0} (t + t^3 + t^4)/(1 + t + t^2 + t^3), where t=x^2^k.

a(n) = A056973(n) + A000120(n) - 1.

a(n) = b(n) - 1, with b(0)=0, b(2n) = b(n) + [n even], b(2n+1) = b(n) + 1. (End)

Extensions

Sign in Name corrected by R. J. Mathar, Oct 16 2015