A079070 Number of numbers < n having in binary representation the same number of 0's as n.

0, 0, 1, 0, 1, 2, 2, 0, 1, 2, 3, 3, 4, 5, 3, 0, 1, 2, 4, 3, 5, 6, 6, 4, 7, 8, 7, 9, 8, 9, 4, 0, 1, 2, 5, 3, 6, 7, 10, 4, 8, 9, 11, 10, 12, 13, 10, 5, 11, 12, 14, 13, 15, 16, 11, 14, 17, 18, 12, 19, 13, 14, 5, 0, 1, 2, 6, 3, 7, 8, 15, 4, 9, 10, 16, 11, 17, 18, 20, 5, 12, 13, 19, 14, 20, 21, 21, 15

Offset: 1

Author

Reinhard Zumkeller, Dec 21 2002

Keywords

• nonn
• base
• look

Examples

			n = 12 -> '1100': A023416(12) = 2 therefore a(12) = #{4 ->'100', 9 ->'1001', 10 ->'1010'} = 3.
n = 13 -> '1101': A023416(13) = 1 therefore a(13) = #{2 ->'10', 5 ->'101', 6 ->'110', 11 ->'1011'} = 4.
		

Links

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

Crossrefs

Cf. A068076, A079071, A079072, A007088, A023416.

Programs

Haskell

import Data.List (elemIndices)
a079070 n = length $ elemIndices (a023416 n) $ map a023416 [1..n-1]
-- Reinhard Zumkeller, Jun 16 2011

Mathematica

dcn[n_]:=Count[Range[n-1],?(DigitCount[#,2,0]==DigitCount[ n,2,0]&)]; Array[dcn,90] (* _Harvey P. Dale, Jun 11 2011 *)

Formula

a(n) = #{m : m < n and A023416(m) = A023416(n)}.

a(2^k - 1) = k - 1; a(2^k) = 0; a(2^k + 1) = 1.