%I #22 May 05 2016 21:10:09
%S 1,3,2,5,4,6,7,8,9,11,10,13,12,14,15,16,17,19,18,21,20,22,23,24,25,27,
%T 26,29,28,30,31,32,33,35,34,37,36,38,39,40,41,43,42,45,44,46,47,48,49,
%U 51,50,53,52,54,55,56,57,59,58,61,60,62,63,64,65,67,66,69,68,70,71,72
%N a(1)=1; a(n) = smallest positive integer not already present such that a(n-1) and a(n) have a different number of 1's in their binary expansions.
%C This sequence is a permutation of the positive integers.
%H Peter Kagey, <a href="/A109451/b109451.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = n+1 if n == 2 or 4 (mod 8), n-1 if n == 3 or 5 (mod 8), n otherwise. - _Peter Kagey_, May 03 2016
%F G.f.: x*(1 + 2*x - 2*x^2 + x^3 + x^4 + x^5)/((1 - x)^2*(1 + x + x^4 + x^5)). - _Ilya Gutkovskiy_, May 04 2016
%e Among the positive integers (10, 11,12, 13,...) not among the first 9 terms of the sequence, 10 (decimal) has 2 1's in its binary form (1010), the same number of 1's as 9 in binary (1001). 11 (decimal), however, has 3 ones in its binary form (1011), so a(10) = 11.
%p Cands:= [$2..100]:
%p Ones:= map(t -> convert(convert(t,base,2),`+`), Cands):
%p A[1]:= 1: dc:= 1:
%p for n from 2 do
%p found:= false;
%p for k from 1 to nops(Cands) while not found do
%p if Ones[k] <> dc then
%p found:= true;
%p A[n]:= Cands[k];
%p dc:= Ones[k];
%p Cands:= subsop(k=NULL,Cands);
%p Ones:= subsop(k=NULL,Ones);
%p fi
%p od;
%p if not found then break fi;
%p od:
%p seq(A[i],i=1..n-1); # _Robert Israel_, May 03 2016
%t a = {1}; Nest[AppendTo[a, SelectFirst[Range@ 120, And[! MemberQ[a, #], First@ DigitCount[#, 2] != First@ DigitCount[Last@ a, 2]] &]] &, a, 71] (* _Michael De Vlieger_, May 03 2016, Version 10 *)
%Y Cf. A000120.
%K nonn
%O 1,2
%A _Leroy Quet_, Aug 27 2005
%E Extended by _Ray Chandler_, Aug 27 2005