cp's OEIS Frontend

A039004 Numbers whose base-4 representation has the same number of 1's and 2's.

%I A039004 #56 Jul 21 2025 00:01:01
%S A039004 0,3,6,9,12,15,18,24,27,30,33,36,39,45,48,51,54,57,60,63,66,72,75,78,
%T A039004 90,96,99,102,105,108,111,114,120,123,126,129,132,135,141,144,147,150,
%U A039004 153,156,159,165,177,180,183,189,192,195,198,201,204,207,210,216,219
%N A039004 Numbers whose base-4 representation has the same number of 1's and 2's.
%C A039004 Numbers such that sum (-1)^k*b(k) = 0 where b(k)=k-th binary digit of n (see A065359). - _Benoit Cloitre_, Nov 18 2003
%C A039004 Conjecture: a(C(2n,n)-1) = 4^n - 1. (A000984 is C(2n,n)). - _Gerald McGarvey_, Nov 18 2007
%C A039004 From _Russell Jay Hendel_, Jun 23 2015: (Start)
%C A039004 We prove the McGarvey conjecture (A) a(e(n,n)-1) = 4^n-1, with e(n,m) = A034870(n,m) = binomial(2n,m), the even rows of Pascal's triangle. By the comment from Hendel in A034870, we have the function s(n,k) = #{n-digit, base-4 numbers with n-k more 1-digits than 2-digits}. As shown in A034870, (B) #s(n,k)= e(n,k) with # indicating cardinality, that is, e(n,k) = binomial(2n,k) gives the number of n-digit, base-4 numbers with n-k more 1-digits than 2-digits.
%C A039004 We now show that (B) implies (A). By definition, s(n,n) contains the e(n,n) = binomial(2n,n) numbers with an equal number of 1-digits and 2-digits. The biggest n-digit, base-4 number is 333...3 (n copies of 3). Since 333...33 has zero 1-digits and zero 2-digits it follows that 333...333 is a member of s(n,n) and hence it is the biggest member of s(n,n). But 333...333 (n copies of 3) in base 4 has value 4^n-1. Since A039004 starts with index 0 (that is, 0 is the 0th member of A039004), it immediately follows that 4^n-1 is the (e(n,n)-1)st member of A039004, proving the McGarvey conjecture. (End)
%C A039004 Also numbers whose alternating sum of binary expansion is 0, i.e., positions of zeros in A345927. These are numbers whose binary expansion has the same number of 1's at even positions as at odd positions. - _Gus Wiseman_, Jul 28 2021
%H A039004 Alois P. Heinz, <a href="/A039004/b039004.txt">Table of n, a(n) for n = 1..10000</a>
%F A039004 Conjecture: there is a constant c around 5 such that a(n) is asymptotic to c*n. - _Benoit Cloitre_, Nov 24 2002
%F A039004 That conjecture is false. The number of members of the sequence from 0 to 4^d-1 is binomial(2d,d) which by Stirling's formula is asymptotic to 4^d/sqrt(Pi*d). If Cloitre's conjecture were true we would have 4^d-1 asymptotic to c*4^d/sqrt(Pi*d), a contradiction. - _Robert Israel_, Jun 24 2015
%p A039004 N:= 1000: # to get all terms up to N, which should be divisible by 4
%p A039004 B:= Array(0..N-1):
%p A039004 d:= ceil(log[4](N));
%p A039004 S:= Array(0..N-1,[seq(op([0,1,-1,0]),i=1..N/4)]):
%p A039004 for i from 1 to d do
%p A039004   B:= B + S;
%p A039004   S:= Array(0..N-1,i-> S[floor(i/4)]);
%p A039004 od:
%p A039004 select(t -> B[t]=0, [$0..N-1]); # _Robert Israel_, Jun 24 2015
%t A039004 ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
%t A039004 Select[Range[0,100],ats[IntegerDigits[#,2]]==0&] (* _Gus Wiseman_, Jul 28 2021 *)
%o A039004 (PARI) for(n=0,219,if(sum(i=1,length(binary(n)),(-1)^i*component(binary(n),i))==0,print1(n,",")))
%o A039004 (Fortran) c See link in A139351.
%Y A039004 Cf. A139370, A139371, A139372, A139373.
%Y A039004 Cf. A139351, A139352, A139353, A139354, A139355.
%Y A039004 A subset of A001969 (evil numbers).
%Y A039004 A base-2 version is A031443 (digitally balanced numbers).
%Y A039004 Positions of 0's in A065359 and A345927.
%Y A039004 Positions of first appearances are A086893.
%Y A039004 The version for standard compositions is A344619.
%Y A039004 A000120 and A080791 count binary digits, with difference A145037.
%Y A039004 A003714 lists numbers with no successive binary indices.
%Y A039004 A011782 counts compositions.
%Y A039004 A030190 gives the binary expansion of each nonnegative integer.
%Y A039004 A070939 gives the length of an integer's binary expansion.
%Y A039004 A097805 counts compositions by alternating (or reverse-alternating) sum.
%Y A039004 A101211 lists run-lengths in binary expansion:
%Y A039004 - row-lengths: A069010
%Y A039004 - reverse: A227736
%Y A039004 - ones only: A245563
%Y A039004 A138364 counts compositions with alternating sum 0:
%Y A039004 - bisection: A001700/A088218
%Y A039004 - complement: A058622
%Y A039004 A328594 lists numbers whose binary expansion is aperiodic.
%Y A039004 A345197 counts compositions by length and alternating sum.
%Y A039004 Cf. A000302, A000346, A003242, A029837, A053738, A053754, A071321, A103919, A191232, A328596.
%K A039004 nonn,base,easy
%O A039004 1,2
%A A039004 _Olivier Gérard_