A250072 Permutation of the nonnegative integers such that sum_{k=0..n} (-1)^(a(k)+1)*a(k) is nonnegative and as small as possible, for n=0,1,....

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

Offset

0,3

Comments

Odd terms are added, even terms are subtracted. At each step, the next term is chosen among numbers which did not yet occur, as to minimize this sum.

Links

Table of n, a(n) for n=0..68.

M. F. Hasler, in reply to E. Angelini, Minimizing Q, SeqFan list, Nov 11 2014.

Formula

a(2n) = 2n+1 for n > 0; a(2^n-1) = 3*2^(n-1)-2 are particularly large "early bird" values (records of a(n)-n), a(2^n-3) = 2^(n-1)-2 are particularly small values (records of n-a(n), and also the values such that all subsequent terms are larger).

Prog

(PARI) a(n, a=0, Q=0, u=[])={for(n=1, n, print1(a", "); u=setunion(u, Set(a)); Q-=(-1)^a*a; forstep(k=Q%2, Q, 2, setsearch(u, Q-k)&&next; a=Q-k; next(2)); forstep(k=1, 9e9, 2, setsearch(u, k)&&next; a=k; next(2)))}

Crossrefs

Cf. A250090.

Sequence in context: A272025 A262411 A280488 * A099120 A199620 A016553

Adjacent sequences: A250069 A250070 A250071 * A250073 A250074 A250075

Keyword

nonn

Author

M. F. Hasler and Eric Angelini, Nov 11 2014

Status

approved