0,3

Index entries for sequences that are permutations of the natural numbers

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

map(CatalanRankGlobal, map(RotateHandshakes, A014486));

RotateHandshakes := n -> pars2binexp(RotateHandshakesP(binexp2pars(n)));

RotateHandshakesP := h -> `if`((0 = nops(h)), h, [op(car(h)), cdr(h)]); # This does the trick! In Lisp: (defun RotateHandshakesP (h) (append (car h) (list (cdr h))))

car := proc(a) if 0 = nops(a) then ([]) else (op(1, a)): fi: end: # The name is from Lisp, takes the first element (head) of the list.

cdr := proc(a) if 0 = nops(a) then ([]) else (a[2..nops(a)]): fi: end: # As well. Takes the rest (the tail) of the list.

PeelNextBalSubSeq := proc(nn) local n, z, c; if(0 = nn) then RETURN(0); fi; n := nn; c := 0; z := 0; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN((z - 2^(floor_log_2(z)))/2); fi; od; end;

RestBalSubSeq := proc(nn) local n, z, c; n := nn; c := 0; while(1 = 1) do c := c + (-1)^n; n := floor(n/2); if(c >= 0) then break; fi; od; z := 0; c := -1; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN(z/2); fi; od; end;

pars2binexp := proc(p) local e, s, w, x; if(0 = nops(p)) then RETURN(0); fi; e := 0; for s in p do x := pars2binexp(s); w := floor_log_2(x); e := e * 2^(w+3) + 2^(w+2) + 2*x; od; RETURN(e); end;

binexp2pars := proc(n) option remember; `if`((0 = n), [], binexp2parsR(binrev(n))); end;

binexp2parsR := n -> [binexp2pars(PeelNextBalSubSeq(n)), op(binexp2pars(RestBalSubSeq(n)))];

# Procedure CatalanRankGlobal given in A057117, other missing ones in A038776.

(Scheme function implementing this automorphism on list-structures:) (define (RotateHandshakes a) (cond ((null? a) (list)) (else (append (car a) (list (cdr a))))))

(Destructive variant:) (define (RotateHandshakes! s) (cond ((not (pair? s))) ((not (pair? (car s))) (swap! s)) (else (robr! s) (RotateHandshakes! (cdr s)))) s)

(define (robr! s) (let ((ex-cdr (cdr s))) (set-cdr! s (caar s)) (set-car! (car s) ex-cdr) (swap! (car s)) (swap! s) s))

(define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))

Inverse of A057502 and the car/cdr-flipped conjugate of A069773, i.e. A057501(n) = A057163(A069773(A057163(n))).

Max cycle lengths: A057543. Cf. A057503, A057505, A057508, A057509, A057511, A057517, A057161, A069771, A069772.

Sequence in context: A130955 A129610 A130923 this_sequence A071655 A130964 A130929

Adjacent sequences: A057498 A057499 A057500 this_sequence A057502 A057503 A057504

nonn

Antti Karttunen Sep 03 2000