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.

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, 26, 29, 28, 30, 31, 32, 33, 35, 34, 37, 36, 38, 39, 40, 41, 43, 42, 45, 44, 46, 47, 48, 49, 51, 50, 53, 52, 54, 55, 56, 57, 59, 58, 61, 60, 62, 63, 64, 65, 67, 66, 69, 68, 70, 71, 72

Offset: 1

Author

Leroy Quet, Aug 27 2005

Keywords

• nonn

Comments

This sequence is a permutation of the positive integers.

Examples

			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.
		

Links

• Peter Kagey, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000120.

Programs

Maple

Cands:= [$2..100]:
Ones:= map(t -> convert(convert(t,base,2),`+`), Cands):
A[1]:= 1: dc:= 1:
for n from 2 do
   found:= false;
   for k from 1 to nops(Cands) while not found do
     if Ones[k] <> dc then
        found:= true;
        A[n]:= Cands[k];
        dc:= Ones[k];
        Cands:= subsop(k=NULL,Cands);
        Ones:= subsop(k=NULL,Ones);
     fi
   od;
   if not found then break fi;
od:
seq(A[i],i=1..n-1); # Robert Israel, May 03 2016

Mathematica

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 *)

Formula

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

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

Extensions

Extended by Ray Chandler, Aug 27 2005