login
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.
1

%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