A026136 - OEIS

%I #39 Oct 06 2022 07:54:40

%S 1,3,2,7,9,4,5,15,6,19,21,8,25,27,10,11,33,12,13,39,14,43,45,16,17,51,

%T 18,55,57,20,61,63,22,23,69,24,73,75,26,79,81,28,29,87,30,31,93,32,97,

%U 99,34,35,105,36,37,111,38,115,117,40,41,123

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

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

%C Also can be defined as follows. For n >= 2, let h=[ n/2 ], L=n-h, R=n+h; then a(R)=n if n even or a(L) already defined, else a(L)=n. For a proof that the two definitions are the same, see my paper "Permutations of N generated by left-right filling algorithms". - _Michel Dekking_, Jan 30 2020

%C From _Peter Munn_, Dec 30 2021: (Start)

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

%C Proof:

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

%C So, values of the form 6k+5 occur at index 6k+5 + [(6k+5)/2] = 9k+7, and not at index 6k+5 - [(6k+5)/2] = 3k+3 because a(3k+3) takes the value 2k+2.

%C Values of the form 6k+3 occur at index 6k+3 - [(6k+3)/2] = 3k+2, because numbers of the form 3k+2 do not have the form m+[m/2] for any m > 0.

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

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

%C (End)

%H Sean A. Irvine, <a href="/A026136/b026136.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 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a026/A026136.java">Java program</a> (github)

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

%t Block[{a, nn = 123}, a[1] = 1; Do[If[! IntegerQ[a[#1]], Set[a[#1], i], Set[a[#2], i]] & @@ {i - #, i + #} &@ Floor[i/2], {i, nn}]; TakeWhile[Array[a[#] &, nn], IntegerQ]] (* _Michael De Vlieger_, Apr 16 2020 *)

%o (Python)

%o import math

%o A026136 ={1:1}

%o for n in range(2,3000):

%o     h=math.floor(n/2)

%o     L=n-h

%o     R=n+h

%o     if not L in A026136 :

%o         A026136[L]=n

%o     else :

%o         A026136[R]=n

%o for n in range(1,2000):

%o     if n in A026136:

%o        print(str(n) + " "+ str(A026136[n]))

%o     else:

%o        break # _R. J. Mathar_, Aug 26 2019

%o (PARI) seq(n)={my(a=vector(n)); a[1]=1; for(i=2, 2*n, my(h=i\2); if(!a[i-h], a[i-h]=i, if(i+h<=n, a[i+h]=i))); a} \\ _Andrew Howroyd_, Oct 15 2019

%Y Cf. A026142, A026224.

%K nonn

%O 1,2

%A _Clark Kimberling_

%E Edited by _N. J. A. Sloane_, Jan 31 2020

%E New name from _Peter Munn_, Dec 30 2021