A068076 Number of positive integers < n with the same number of 1's in their binary expansions as n.

0, 1, 0, 2, 1, 2, 0, 3, 3, 4, 1, 5, 2, 3, 0, 4, 6, 7, 4, 8, 5, 6, 1, 9, 7, 8, 2, 9, 3, 4, 0, 5, 10, 11, 10, 12, 11, 12, 5, 13, 13, 14, 6, 15, 7, 8, 1, 14, 16, 17, 9, 18, 10, 11, 2, 19, 12, 13, 3, 14, 4, 5, 0, 6, 15, 16, 20, 17, 21, 22, 15, 18, 23, 24, 16, 25, 17, 18, 6, 19, 26, 27, 19

Offset: 1

Author

Dean Hickerson, Feb 16 2002

Keywords

• nonn
• look

Comments

From Rémy Sigrist, Dec 23 2018: (Start)

This sequence is related to the combinatorial number system:

- if n = Sum_{k=1..h} 2^c_k with 0 <= c_1 < c_2 < ... < c_h,

- then a(n) = Sum_{k=1..h} binomial(c_k, k) (with binomial(n, r) = 0 if n < r).

(End)

Examples

			The binary expansion of 22 (10110) has 3 1's, as do those of the 6 smaller numbers 7, 11, 13, 14, 19 and 21, so a(22)=6.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Wikipedia, Combinatorial number system

Crossrefs

One less than A263017.

Cf. A067587, also A000120 for numerous references.

Programs

Mathematica

w[n_] := Plus@@IntegerDigits[n, 2]; a[n_] := Plus@@MapThread[Binomial, {Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]]-1, Range[w[n]]}]

PARI

a(n)=my(k=hammingweight(n));sum(i=1,n-1,hammingweight(i)==k) \\ Charles R Greathouse IV, Sep 24 2012

PARI

a(n) = my (v=0, k=0); for (c=0, oo, if (n==0, return (v), n%2, k++; if (c>=k, v+=c!/k!/(c-k)!)); n\=2) \\ Rémy Sigrist, Dec 23 2018

Python

def a(n):
    x=bin(n)[2:].count("1")
    return sum(1 for i in range(n) if bin(i)[2:].count("1")==x) # Indranil Ghosh, May 24 2017

Python

from math import comb
def A068076(n):
    c, k = 0, 1
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            c += comb(i,k)
            k += 1
    return c # Chai Wah Wu, Mar 01 2023

Formula

a(n) = A263017(n) - 1. - Antti Karttunen, May 22 2017

Extensions

Edited by John W. Layman, Feb 20 2002