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

Comments

Equivalently, number of nonnegative terms in the first differences of the digits of the binary representation of n. - Paolo Xausa, Nov 19 2025

Links

Chris R. Rehmann, Table of n, a(n) for n = 1..10000

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

Ralf Stephan, Table of generating functions

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)

Example

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

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

Mathematica

A037809[n_] := Count[Differences[IntegerDigits[n, 2]], _?NonNegative];
Array[A037809, 100] (* Paolo Xausa, Nov 19 2025 *)

Prog

(MATLAB) n = 1:10000; a = arrayfun(@(m) sum(diff(dec2base(m, 2)-'0')>=0), n); % Chris R. Rehmann, Nov 17 2025

Crossrefs

Cf. A007088, A033265.

Cf. A037810, A037811, A037812, A037813, A037814, A037815, A037816, A037817.

Sequence in context: A046799 A348172 A319506 * A280534 A129451 A097195

Adjacent sequences: A037806 A037807 A037808 * A037810 A037811 A037812

Keyword

nonn,base,easy

Author

Clark Kimberling

Extensions

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

Status

approved