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

Links

Table of n, a(n) for n=1..90.

Ralf Stephan, Some divide-and-conquer sequences ...

Ralf Stephan, Table of generating functions

Formula

From Ralf Stephan, Oct 05 2003: (Start)

G.f.: -1/(1-x) + 1/(1-x) * Sum_{k>=0} (t + t^3 + t^4)/(1 + t + t^2 + t^3), 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)

Example

The base-2 representation of n=4 is 100 with d(0)=0, d(1)=0, d(2)=1. There is one fall-or-equal from d(0) to d(1), so a(4)=1. - R. J. Mathar, Oct 16 2015

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

Crossrefs

Cf. A033265.

Sequence in context: A046799 A348172 A319506 * A280534 A129451 A097195

Adjacent sequences: A037806 A037807 A037808 * A037810 A037811 A037812

Keyword

nonn,base

Author

Clark Kimberling

Extensions

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

Status

approved