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,4

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)

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Wikipedia, Combinatorial number system

Formula

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

Example

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.

Mathematica

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

Prog

(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

Crossrefs

One less than A263017.

Cf. A067587, also A000120 for numerous references.

Sequence in context: A290537 A272569 A344788 * A138498 A276669 A307596

Adjacent sequences: A068073 A068074 A068075 * A068077 A068078 A068079

Keyword

nonn,look

Author

Dean Hickerson, Feb 16 2002

Extensions

Edited by John W. Layman, Feb 20 2002

Status

approved