cp's OEIS Frontend

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

%I A026136 #39 Oct 06 2022 07:54:40
%S A026136 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 A026136 18,55,57,20,61,63,22,23,69,24,73,75,26,79,81,28,29,87,30,31,93,32,97,
%U A026136 99,34,35,105,36,37,111,38,115,117,40,41,123
%N A026136 Lexicographically earliest permutation of the positive integers such that |a(n)-n| = [a(n)/2].
%C A026136 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 A026136 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 A026136 From _Peter Munn_, Dec 30 2021: (Start)
%C A026136 A value m occurs at an index n, n < m if and only if m has the form 3^i*(6k+2)+1.
%C A026136 Proof:
%C A026136 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 A026136 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 A026136 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 A026136 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 A026136 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 A026136 (End)
%H A026136 Sean A. Irvine, <a href="/A026136/b026136.txt">Table of n, a(n) for n = 1..10000</a>
%H A026136 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 A026136 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a026/A026136.java">Java program</a> (github)
%H A026136 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%t A026136 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 A026136 (Python)
%o A026136 import math
%o A026136 A026136 ={1:1}
%o A026136 for n in range(2,3000):
%o A026136     h=math.floor(n/2)
%o A026136     L=n-h
%o A026136     R=n+h
%o A026136     if not L in A026136 :
%o A026136         A026136[L]=n
%o A026136     else :
%o A026136         A026136[R]=n
%o A026136 for n in range(1,2000):
%o A026136     if n in A026136:
%o A026136        print(str(n) + " "+ str(A026136[n]))
%o A026136     else:
%o A026136        break # _R. J. Mathar_, Aug 26 2019
%o A026136 (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 A026136 Cf. A026142, A026224.
%K A026136 nonn
%O A026136 1,2
%A A026136 _Clark Kimberling_
%E A026136 Edited by _N. J. A. Sloane_, Jan 31 2020
%E A026136 New name from _Peter Munn_, Dec 30 2021