A160385 Number of nonzero digits in base-4 representation of n.

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

Offset: 0

Author

Frank Ruskey, Jun 05 2009

Keywords

• nonn
• base
• easy

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• F. T. Adams-Watters, F. Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009) 09.5.6

Programs

Haskell

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

Formula

Recurrence relation: a(0) = 0, a(4m) = a(m), a(4m+1) = a(4m+2) = a(4m+3) = 1+a(m).

Generating function: (1/(1-z)) * Sum_{m>=1} (z^(4^(m-1) - z^(4^m))/(1 - z^(4^m))).

Morphism: 0, j -> j,j+1,j+1,j+1; e.g., 0 -> 0111 -> 0111122212221222 -> ...