A118319 a(n) = (highest power of 2 dividing n)th integer among those positive integers not occurring in {a(1),a(2),a(3),...,a(n-1)}.

1, 3, 2, 7, 4, 6, 5, 15, 8, 10, 9, 14, 11, 13, 12, 31, 16, 18, 17, 22, 19, 21, 20, 30, 23, 25, 24, 29, 26, 28, 27, 63, 32, 34, 33, 38, 35, 37, 36, 46, 39, 41, 40, 45, 42, 44, 43, 62, 47, 49, 48, 53, 50, 52, 51, 61, 54, 56, 55, 60, 57, 59, 58, 127, 64, 66, 65, 70, 67, 69, 68, 78

Offset

1,2

Comments

Sequence is a permutation of the positive integers. a(2n-1) is the smallest positive integer not occurring earlier in the sequence.

It seems that A101925 is the odd bisection, A045412 is the sorted even bisection: a(2*n) = A045412(a(n)). - Andrey Zabolotskiy, Oct 09 2019

Links

Andrey Zabolotskiy, Table of n, a(n) for n = 1..8192

Index entries for sequences that are permutations of the natural numbers

Formula

a(2^m) = 2^(m+1) - 1; a(2^m+k) = a(k) + 2^m - 1 for 0 < k < 2^m. - Andrey Zabolotskiy, Oct 10 2019

Example

4 is the highest power of 2 dividing 12. Those positive integers not occurring among the first 11 terms of the sequence form the sequence 11, 12, 13, 14, 16,... Now 14 is the 4th of these integers, so a(12) = 14.

Maple

A118319 := proc(nmin) local a, anxt, i, n ; a := [1] ; while nops(a) < nmin do n := nops(a)+1 ; i := 2^A007814(n); anxt := 0 ; while i > 0 do anxt := anxt+1 ; while anxt in a do anxt := anxt+1 ; od ; i := i-1; od ; a := [op(a), anxt] ; od; a ; end: A118319(80) ; # R. J. Mathar, Sep 06 2007

Mathematica

a[1] := 1; a[n_] := a[n] =  Part[ Complement[ Range[2 n], Table[a[i], {i, n - 1}]],  2^IntegerExponent[n, 2]]; Array[a, 100] (* Birkas Gyorgy, Jul 09 2012 *)

Crossrefs

Cf. A108918 (inverse permutation), A006519, A045412, A101925.

Sequence in context: A303765 A255555 A191664 * A316385 A341911 A341916

Adjacent sequences: A118316 A118317 A118318 * A118320 A118321 A118322

Keyword

easy,nonn

Author

Leroy Quet, Apr 23 2006

Extensions

More terms from R. J. Mathar, Sep 06 2007

Status

approved