A026142 - OEIS

%I #16 Jan 14 2022 15:31:42

%S 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,

%T 18,56,19,60,62,21,22,68,23,72,74,25,78,80,27,28,86,29,30,92,31,96,98,

%U 33,34,104,35,108,110,37,114,116,39,40,122,41,126,128,43,132

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

%C 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 ].

%C From _Peter Munn_, Jan 07 2022: (Start)

%C 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.

%C Proof:

%C 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.

%C 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.

%C 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.)

%C 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.

%C 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).)

%C (End)

%H Sean A. Irvine, <a href="/A026142/b026142.txt">Table of n, a(n) for n = 1..10000</a>

%H F. M. Dekking, <a href="https://arxiv.org/abs/2001.08915">Permutations of N generated by left-right filling algorithms</a>, arXiv:2001.08915 [math.CO], 2020.

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

%Y Cf. A026136, A026224.

%K nonn

%O 1,2

%A _Clark Kimberling_

%E New name from _Peter Munn_, Jan 07 2022