cp's OEIS Frontend

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

%I A068076 #34 Mar 01 2023 19:39:34
%S A068076 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,
%T A068076 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,
%U A068076 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
%N A068076 Number of positive integers < n with the same number of 1's in their binary expansions as n.
%C A068076 From _Rémy Sigrist_, Dec 23 2018: (Start)
%C A068076 This sequence is related to the combinatorial number system:
%C A068076 - if n = Sum_{k=1..h} 2^c_k with 0 <= c_1 < c_2 < ... < c_h,
%C A068076 - then a(n) = Sum_{k=1..h} binomial(c_k, k) (with binomial(n, r) = 0 if n < r).
%C A068076 (End)
%H A068076 Charles R Greathouse IV, <a href="/A068076/b068076.txt">Table of n, a(n) for n = 1..10000</a>
%H A068076 Wikipedia, <a href="https://en.wikipedia.org/wiki/Combinatorial_number_system">Combinatorial number system</a>
%F A068076 a(n) = A263017(n) - 1. - _Antti Karttunen_, May 22 2017
%e A068076 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.
%t A068076 w[n_] := Plus@@IntegerDigits[n, 2]; a[n_] := Plus@@MapThread[Binomial, {Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]]-1, Range[w[n]]}]
%o A068076 (PARI) a(n)=my(k=hammingweight(n));sum(i=1,n-1,hammingweight(i)==k) \\ _Charles R Greathouse IV_, Sep 24 2012
%o A068076 (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
%o A068076 (Python)
%o A068076 def a(n):
%o A068076     x=bin(n)[2:].count("1")
%o A068076     return sum(1 for i in range(n) if bin(i)[2:].count("1")==x) # _Indranil Ghosh_, May 24 2017
%o A068076 (Python)
%o A068076 from math import comb
%o A068076 def A068076(n):
%o A068076     c, k = 0, 1
%o A068076     for i,j in enumerate(bin(n)[-1:1:-1]):
%o A068076         if j == '1':
%o A068076             c += comb(i,k)
%o A068076             k += 1
%o A068076     return c # _Chai Wah Wu_, Mar 01 2023
%Y A068076 One less than A263017.
%Y A068076 Cf. A067587, also A000120 for numerous references.
%K A068076 nonn,look
%O A068076 1,4
%A A068076 _Dean Hickerson_, Feb 16 2002
%E A068076 Edited by _John W. Layman_, Feb 20 2002