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