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

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, 18, 55, 57, 20, 61, 63, 22, 23, 69, 24, 73, 75, 26, 79, 81, 28, 29, 87, 30, 31, 93, 32, 97, 99, 34, 35, 105, 36, 37, 111, 38, 115, 117, 40, 41, 123

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

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) ].

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

From Peter Munn, Dec 30 2021: (Start)

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

Proof:

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.

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.

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.

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.

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

(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.
• Sean A. Irvine, Java program (github)
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A026142, A026224.

Programs

Mathematica

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

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

Python

import math
A026136 ={1:1}
for n in range(2,3000):
    h=math.floor(n/2)
    L=n-h
    R=n+h
    if not L in A026136 :
        A026136[L]=n
    else :
        A026136[R]=n
for n in range(1,2000):
    if n in A026136:
       print(str(n) + " "+ str(A026136[n]))
    else:
       break # R. J. Mathar, Aug 26 2019

Extensions

Edited by N. J. A. Sloane, Jan 31 2020

New name from Peter Munn, Dec 30 2021