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

Author

Leroy Quet, Apr 23 2006

Keywords

• easy
• nonn

Comments

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

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

Examples

			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.
		

Links

• Andrey Zabolotskiy, Table of n, a(n) for n = 1..8192
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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

Programs

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
a := n -> n + 2^padic[ordp](n, 2) - add(convert(n, base, 2)): seq(a(n), n = 1..72); # Peter Luschny, Mar 08 2025

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

PARI

a(n) = n + 1<Kevin Ryde, Mar 02 2025

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

a(n) = n + A006519(n) - A000120(n). - Kevin Ryde, Mar 08 2025

Extensions

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