cp's OEIS Frontend

A163356 Inverse permutation to A163355, related to Hilbert's curve in N x N grid.

%I A163356 #18 Nov 22 2022 08:53:50
%S A163356 0,1,3,2,8,10,11,9,12,14,15,13,7,6,4,5,16,18,19,17,20,21,23,22,28,29,
%T A163356 31,30,27,25,24,26,48,50,51,49,52,53,55,54,60,61,63,62,59,57,56,58,47,
%U A163356 46,44,45,39,37,36,38,35,33,32,34,40,41,43,42,128,130,131,129,132,133
%N A163356 Inverse permutation to A163355, related to Hilbert's curve in N x N grid.
%H A163356 A. Karttunen, <a href="/A163356/b163356.txt">Table of n, a(n) for n = 0..65535</a>
%H A163356 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A163356 a(0) = 0, and provided that d=1, 2 or 3, then a((d*(4^i))+r) = (((2+(i mod 2))^d mod 5)-1) * [either A024036(i) - a(r), if d is 3, and A057300(a(r)) in other cases].
%F A163356 From _Antti Karttunen_, Apr 14 2018: (Start)
%F A163356 A059905(a(n)) = A059253(n).
%F A163356 A059906(a(n)) = A059252(n).
%F A163356 a(n) = A000695(A059253(n)) + 2*A000695(A059252(n)).
%F A163356 (End)
%o A163356 (MIT Scheme:)
%o A163356 (define (A163356 n) (if (zero? n) n (let* ((i (floor->exact (/ (A000523 n) 2))) (d (modulo (floor->exact (/ n (expt 4 i))) 4)) (r (modulo n (expt 4 i)))) (+ (* (-1+ (modulo (expt (+ 2 (modulo i 2)) d) 5)) (expt 4 i)) (cond ((= 3 d) (- (expt 4 i) 1 (A163356 r))) (else (A057300 (A163356 r))))))))
%o A163356 (Another, iterative version): (define (A163356v2 n) (let loop ((z 0) (n n) (i 0)) (let ((dd (modulo n 4))) (cond ((zero? n) z) ((= 0 dd) (loop z (floor->exact (/ n 4)) (+ i 2))) ((= 2 dd) (loop (+ (* 3 (expt 2 i)) (A057300 z)) (floor->exact (/ n 4)) (+ i 2))) ((= 1 dd) (loop (+ (expt 2 (+ i (floor->exact (/ (modulo i 4) 2)))) (A057300 z)) (floor->exact (/ n 4)) (+ i 2))) (else (loop (+ (expt 2 (+ i (- 1 (floor->exact (/ (modulo i 4) 2))))) (- (expt 2 i) z 1)) (floor->exact (/ n 4)) (+ i 2)))))))
%o A163356 (PARI)
%o A163356 A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
%o A163356 A163356(n) = if(!n,n,my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d,f-1-A163356(r),A057300(A163356(r)))); \\ _Antti Karttunen_, Apr 14 2018
%Y A163356 Inverse: A163355.
%Y A163356 Second and third "powers": A163906, A163916. See also A059252-A059253.
%Y A163356 In range [A000302(n-1)..A024036(n)] of this permutation, the number of cycles is given by A163910, number of fixed points seems to be given by A147600(n-1) (fixed points themselves: A163901). Max. cycle sizes is given by A163911 and LCM's of all cycle sizes by A163912.
%Y A163356 Cf. A059252, A059253, A059905, A059906.
%Y A163356 Cf. also A302844, A302846, A302781.
%K A163356 nonn
%O A163356 0,3
%A A163356 _Antti Karttunen_, Jul 29 2009
%E A163356 Links to further derived sequences and a nicer Scheme function & formula added by _Antti Karttunen_, Sep 21 2009