A026142 Lexicographically earliest permutation of the positive integers such that for n >= 2, |a(n)-n| = [(a(n)+1)/2].

1, 4, 2, 8, 3, 12, 14, 5, 6, 20, 7, 24, 26, 9, 10, 32, 11, 36, 38, 13, 42, 44, 15, 16, 50, 17, 18, 56, 19, 60, 62, 21, 22, 68, 23, 72, 74, 25, 78, 80, 27, 28, 86, 29, 30, 92, 31, 96, 98, 33, 34, 104, 35, 108, 110, 37, 114, 116, 39, 40, 122, 41, 126, 128, 43, 132

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

Old name: For n >= 2, let h=[ (n+1)/2 ], L=n-h, R=n+h; a(L)=n if a(L) not yet defined, else a(R)=n; thus |a(n)-n| = [ (a(n)+1)/2 ].

From Peter Munn, Jan 07 2022: (Start)

A value m occurs at an index n, n < m if and only if m has the form 3^i*4 or 3^i*(6k+2), k >= 1.

Proof:

For k >= 1, values of the form 2k+1 occur at index 2k+1 + [(2k+1+1)/2] = 3k+2 and not at index 2k+1 - [(2k+1+1)/2] = k, because a(k) can take the value 2k and 2k cannot occur earlier.

So, for k >= 1, values of the form 6k+4 occur at index 6k+4 + [(6k+4+1)/2] = 9k+6, and not at index 6k+4 - [(6k+4+1)/2] = 3k+2 because a(3k+2) takes the value 2k+1.

For k >= 1, values of the form 6k+2 occur at index 6k+2 - [(6k+2+1)/2] = 3k+1, because numbers of the form 3k+1 do not have the form m+[(m+1)/2] for any m > 0. (Note that for k = 0, 1 occurs at index 1 due to an explicit exemption from the definition's constraining rule.)

A value of the form 6k occurs at index 6k - [(6k+1)/2] = 3k if and only if 2k occurs at index k rather than occupying index 3k.

From the characterization above of cases 6k+4, 6k+2 and 6k we see the following: an even number 2j > 4 occurs before or after position 2j depending on the base 3 representation of j with its trailing zeros removed. (With respect to the statement being proved j = 3^i*2 or 3^i*(3k+1).)

(End)

Links

• Sean A. Irvine, Table of n, a(n) for n = 1..10000
• F. M. Dekking, Permutations of N generated by left-right filling algorithms, arXiv:2001.08915 [math.CO], 2020.
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A026136, A026224.

Programs

Mathematica

Block[{a, nn = 132}, a[1] = 1; Do[If[! IntegerQ[a[#1]], Set[a[#1], i], Set[a[#2], i]] & @@ {i - #, i + #} &@ Floor[(i + 1)/2], {i, nn}]; TakeWhile[Array[a[#] &, nn], IntegerQ]] (* Michael De Vlieger, Apr 17 2020 *)

Extensions

New name from Peter Munn, Jan 07 2022