cp's OEIS Frontend

A109451 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.

%I A109451 #22 May 05 2016 21:10:09
%S A109451 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 A109451 26,29,28,30,31,32,33,35,34,37,36,38,39,40,41,43,42,45,44,46,47,48,49,
%U A109451 51,50,53,52,54,55,56,57,59,58,61,60,62,63,64,65,67,66,69,68,70,71,72
%N A109451 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 A109451 This sequence is a permutation of the positive integers.
%H A109451 Peter Kagey, <a href="/A109451/b109451.txt">Table of n, a(n) for n = 1..10000</a>
%F A109451 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 A109451 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 A109451 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 A109451 Cands:= [$2..100]:
%p A109451 Ones:= map(t -> convert(convert(t,base,2),`+`), Cands):
%p A109451 A[1]:= 1: dc:= 1:
%p A109451 for n from 2 do
%p A109451    found:= false;
%p A109451    for k from 1 to nops(Cands) while not found do
%p A109451      if Ones[k] <> dc then
%p A109451         found:= true;
%p A109451         A[n]:= Cands[k];
%p A109451         dc:= Ones[k];
%p A109451         Cands:= subsop(k=NULL,Cands);
%p A109451         Ones:= subsop(k=NULL,Ones);
%p A109451      fi
%p A109451    od;
%p A109451    if not found then break fi;
%p A109451 od:
%p A109451 seq(A[i],i=1..n-1); # _Robert Israel_, May 03 2016
%t A109451 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 A109451 Cf. A000120.
%K A109451 nonn
%O A109451 1,2
%A A109451 _Leroy Quet_, Aug 27 2005
%E A109451 Extended by _Ray Chandler_, Aug 27 2005