A139351 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 e(n).

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

Offset: 0

Author

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

Keywords

• nonn
• base
• easy

Comments

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

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

Examples

			For n = 43 = 2^0 + 2^1 + 2^3 + 2^5, e(43)=1, o(43)=3.
		

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.
• N. J. A. Sloane, Fortran program for this and related sequences.

Crossrefs

Cf. A000120, A030308, A059841, A139352, A139353, A139354, A139355, A039004, A139370, A139371, A139372, A139373.

Programs

Fortran

See Sloane link.

Haskell

import Data.List (unfoldr)
a139351 = sum . map (`mod` 2) .
   unfoldr (\x -> if x == 0 then Nothing else Just (x, x `div` 4))
-- Reinhard Zumkeller, Apr 22 2011

Maple

A139351 := proc(n)
    local a,bdgs,r;
    a := 0 ;
    bdgs := convert(n,base,2) ;
    for r from 1 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

terms = 99; s = (1/(1-z))*Sum[z^(4^m)/(1+z^(4^m)), {m, 0, Log[4, terms] // Ceiling}] + O[z]^terms; CoefficientList[s, z] (* Jean-François Alcover, Jul 21 2017 *)
a[0] = 0; a[n_] := a[n] = a[Floor[n/4]] + If[OddQ[Mod[n, 4]], 1, 0]; Array[a, 100, 0] (* Amiram Eldar, Jul 18 2023 *)

PARI

a(n)=if(n>3,a(n\4))+n%2 \\ Charles R Greathouse IV, Apr 21 2016

Formula

a(n) + A139352(n) = A000120(n).

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

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

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

Extensions

Typo in example fixed by Reinhard Zumkeller, Apr 22 2011