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,2

Comments

This sequence is a permutation of the positive integers.

Links

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

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

Example

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.

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

Crossrefs

Cf. A000120.

Sequence in context: A109712 A095049 A118209 * A160017 A266154 A266089

Adjacent sequences: A109448 A109449 A109450 * A109452 A109453 A109454

Keyword

nonn

Author

Leroy Quet, Aug 27 2005

Extensions

Extended by Ray Chandler, Aug 27 2005

Status

approved