A139352 Let the binary expansion of n be n = Sum_{k} 2^{r_k}, let e(n) be the number of r_k's that are even, o(n) the number that are odd; sequence gives o(n).

0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2

Offset

0,11

Comments

e(n) + o(n) = A000120(n), the binary weight of n.

a(n) is also the number of 2's and 3's in the 4-ary representation of n. - Frank Ruskey, May 02 2009

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Franklin T. Adams-Watters and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009), Article 09.5.6.

Formula

G.f.: (1/(1-z))*Sum_{m>=0} (z^(2*4^m)/(1+(2*4^m))). - Frank Ruskey, May 03 2009

Recurrence relation: a(0)=0, a(4m) = a(4m+1) = a(m), a(4m+2) = a(4m+3) = 1+a(m). - Frank Ruskey, May 11 2009

a(n) = Sum_{k} A030308(n,k)*A000035(k). - Philippe Deléham, Oct 14 2011

Example

For n = 43 = 2^0 + 2^1 + 2^3 + 2^5, e(43)=1, o(43)=3. [Typo fixed by Reinhard Zumkeller, Apr 22 2011]

Maple

A139352 := proc(n)
    local a, bdgs, r;
    a := 0 ;
    bdgs := convert(n, base, 2) ;
    for r from 2 to nops(bdgs) by 2 do
        if op(r, bdgs) = 1 then
            a := a+1 ;
        end if;
    end do:
    a;
end proc: # R. J. Mathar, Jul 21 2016

Mathematica

a[n_] := Count[Position[Reverse@IntegerDigits[n, 2], 1]-1, {_?OddQ}];
Table[a[n], {n, 0, 99}] (* Jean-François Alcover, Mar 04 2023 *)
a[0] = 0; a[n_] := a[n] = a[Floor[n/4]] + If[Mod[n, 4] > 1, 1, 0]; Array[a, 100, 0] (* Amiram Eldar, Jul 18 2023 *)

Prog

See link in A139351 for Fortran program.
(Haskell)
import Data.List (unfoldr)
a139352 = sum . map ((`div` 2) . (`mod` 4)) .
   unfoldr (\x -> if x == 0 then Nothing else Just (x, x `div` 4))
-- Reinhard Zumkeller, Apr 22 2011
(PARI) a(n)=if(n>3, a(n\4))+n%4\2 \\ Charles R Greathouse IV, Apr 21 2016

Crossrefs

Cf. A000035, A000120, A030308, A039004, A139351, A139353, A139354, A139355, A139370, A139371, A139372, A139373.

Sequence in context: A231735 A016429 A131852 * A214039 A089679 A290320

Adjacent sequences: A139349 A139350 A139351 * A139353 A139354 A139355

Keyword

nonn,base,easy

Author

Nadia Heninger and N. J. A. Sloane, Jun 07 2008

Status

approved